Post

[알고리즘] 정렬(Sort)

Posted
By juyeoon 12 min read


정렬(Sort)

  • 데이터를 정해진 기준에 따라 배치해 의미 있는 구조로 재설정하는 것

  1. 버블 정렬(Bubble sort)

    • 데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 방식

  2. 선택 정렬(Selection sort)

    • 대상에서 가장 크거나 작은 데이터를 찾아가 선택을 반복하면서 정렬하는 방식

  3. 삽입 정렬(Insertion sort)

    • 대상을 선택해 정렬된 영역에서 선택 데이터의 적절한 위치를 찾아 삽입하면서 정렬하는 방식

  4. 퀵 정렬(Quick sort)

    • pivot 값을 선정해 해당 값을 기준으로 정렬하는 방식

  5. [병합 정렬(Merge sort)]

    • 이미 정렬된 부분 집합들을 효율적으로 병합해 전체를 정렬하는 방식

  6. [기수 정렬(Radix sort)]

    • 데이터의 자릿수를 바탕으로 비교해 데이터를 정렬하는 방식


버블 정렬

  • 두 인접한 데이터의 크기를 비교해 정렬하는 방법

  • 시간 복잡도는 O(n2) ⇒ 속도가 느린 편

  • 구현 난이도는 낮은 편

  • 정렬 과정

    1. 비교 연산이 필요한 루프 범위 설정
    2. 인접한 데이터 값을 비교
    3. swap 조건(정렬 조건)에 부합하면 swap 연산을 수행
    4. 루프 범위가 끝날 때까지 2 ~ 3번 과정을 반복 ⇒ 1번째 루프를 수행하고 나면 가장 큰 데이터가 맨 뒤로 이동 (오름차순의 경우)
    5. 정렬된 데이터를 제외한 영역을 정렬 영역으로 재설정
      정렬되지 않은 영역 내에서만 루프를 실행
    6. 데이터 개수 - 1만큼 루프를 실행 (만약 한 루프의 전체 영역에서 swap이 한 번도 수행되지 않으면 정렬이 끝났다는 뜻으로 프로세스 종료 가능)


버블 정렬 Java 코드 

1
2
3
4
5
6
7
8
9
10
11
12
13

// 오름차순 정렬
void bubbleSort(int list[]) {
	int n = list.length;
	for (int i = n - 1; i > 0; i--) { // 데이터 개수 - 1 만큼 반복
		for (int j = 0; j < i; j++) { // [0]부터 [i]까지의 영역에서 확인
			if (list[j] > list[j + 1]) { // 앞의 데이터가 더 크면 swap(오름차순의 경우)
				int tmp = list[j];
				list[j] = list[j + 1];
				list[j + 1] = tmp;
			}
		}
	}
}


연습문제


선택 정렬

  • 대상 데이터에서 최대나 최소 데이터를 데이터가 나열된 순으로 찾아가며 선택하는 방법

  • 시간 복잡도는 O(n2) ⇒ 속도가 느린 편

  • 정렬 과정

    1. 남은 정렬 부분에서 최솟값 또는 최댓값을 찾음
    2. 남은 정렬 부분에서 가장 앞에 있는 데이터와 선택된 데이터를 swap
    3. 가장 앞에 있는 데이터를 제외한 범위로 남은 정렬 부분 범위 축소
    4. 남은 정령 부분이 없을 때까지 반복


선택 정렬 Java 코드 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

// 오름차순 정렬
void selectionSort(int list[]) {
	int n = list.length; // 데이터 개수
	for (int i = 0; i < n; i++) { // swap할 위치. 정렬 구역 설정
		int minIdx = i; // 최솟값 인덱스
		for (int j = i + 1; j < n; j++) { // 최솟값, 최솟값 인덱스 찾기
			if (list[minIdx] > list[j]) {
				minIdx = j;
			}
		}
		// swap 위치의 값과 최솟값 비교 후 정렬 조건에 맞으면 swap
		if (list[i] > list[minIdx]) {
			int tmp = list[i];
			list[i] = list[minIdx];
			list[minIdx] = tmp;
		}
	}
}


연습문제

BOJ 1427 : 소트인사이드 (Silver V)


삽입 정렬

  • 이미 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입시켜 정렬하는 방식

  • 시간 복잡도는 O(n2) ⇒ 속도가 느린 편

  • 구현 난이도는 낮은 편

  • 정렬 과정

    1. 현재 index에 있는 데이터를 선택
    2. 현재 선택한 데이터가 정렬된 데이터 범위에 삽입될 위치를 탐색
    3. 삽입 위치부터 index에 있는 위치까지 shift 연산 수행
    4. 삽입 위치에 현재 선택한 데이터를 삽입하고 index++
    5. 선택할 데이터가 없을 때까지 반복

  • 적절한 삽입 위치를 탐색하는 부분에서 이진 탐색 등 탐색 알고리즘 사용시 시간 복잡도를 줄일 수 있음


삽입 정렬 Java 코드 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

// 오름차순 정렬
void insertionSort(int list[]) {
	int n = list.length; // 데이터 개수
	for (int i = 1; i < n; i++) { // 두 번째 데이터부터 마지막 데이터까지 정렬
		int insertIdx = i; // 삽입 위치
		int insertValue = list[i]; // 삽입 값
		for (int j = i - 1; j >= 0; j--) { // 삽입 위치 찾기
			if (list[j] < list[i]) { // 정렬된 부분에서 더 작은 값을 찾으면
				insertIdx = j + 1; // 그 값 뒤가 삽입 위치
				break;
			}
			if (j == 0) { // 정렬된 부분의 첫 번째 값보다 작은 경우
				insertIdx = 0; // 맨 앞이 삽입 위치
			}
		}
		for (int j = i; j > insertIdx; j--) { // 삽입 위치부터 현재 위치까지 데이터 뒤로 밀기
			list[j] = list[j - 1];
		}
		list[insertIdx] = insertValue; // 삽입 위치에 값 넣기
	}
}


연습문제

BOJ 11399 : ATM (Silver IV)


퀵 정렬

  • 기준값(pivot)을 선정해 해당 값보다 작은 데이터와 큰 데이터로 분류하는 것을 반복해 정렬하는 방식

  • 평균적인 시간 복잡도는 O(nlogn) => pivot이 어떻게 선정되는지에 따라 시간 복잡도에 많은 영향을 미침

  • 정렬 과정

    1. pivot을 설정

    2. pivot을 기준으로 데이터를 2개의 집합으로 분리

      a. pivot이 가리키는 값과 데이터의 처음 값을 교환 (pivot이 맨 앞으로 올 수 있게)
      b. pivot을 제외한 데이터의 처음과 끝을 front와 back로 지정

      c. front가 가리키는 데이터(이하 front값)가 pivot이 가리키는 데이터(이하 pivot값)보다 클 때까지 => front를 오른쪽으로 이동
      d. back이 가리키는 데이터(이하 back값)가 pivot값보다 작을 때까지 => back을 왼쪽으로 이동

      e. front와 back이 정해지면 두 값을 비교 e-1. front가 back보다 작으면 => front값과 back값을 swap후 c~d 과정 반복 e-2. back이 front보다 작으면 => pivot값과 back값을 swap

      f. e 과정까지 끝나면 pivot을 기준으로 앞은 pivot값보다 작은 값들이, 뒤는 pivot값보다 큰 값들이 오게 됨

    3. 2개의 분리된 집합에 대하여 집합의 원소가 1개 이하가 될 때까지 1 ~ 3 과정을 반복

  • 데이터가 대부분 정렬되어 있는 경우 맨 앞쪽이나 맨 뒤쪽에 있는 수를 pivot으로 선택하면 불필요한 연산이 많아짐 => 배열의 중간 위치를 pivot으로 설정

    • 이 경우 pivot으로 설정한 값과 가장 왼쪽에 있는 값을 swap (front와 back을 쉽게 옮기기 위해서)

퀵 정렬 Java 코드 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

// 오름차순 정렬
void quickSort(int list[], int start, int end) {

	// 재귀 종료 규칙
	if (start >= end) { // 정렬할 원소가 1개 이하
		return;
	}

	// 가운데 값을 피벗으로 설정 후 맨 앞으로 가져오기
	int pivot = (start + end) / 2;
	swap(list, start, pivot);
	pivot = start;

	// 크기 비교를 위한 이동 포인터 설정
	int front = pivot + 1;
	int back = end;

	// 피벗 기준으로 정렬
	while (front <= back) { // front와 back이 엇갈릴 때까지
		while (front <= end && list[pivot] > list[front]) {
			front++;
		}
		while (back > start && list[pivot] < list[back]) {
			back--;
		}
		if (front < back) { // front와 back 값 교환
			swap(list, front, back);
			front++;
			back--;
		}
	}

	// front와 back이 엇갈리면 피벗과 back 위치 교환
	swap(list, back, pivot);

	// 재귀 호출
	quickSort(list, start, back - 1); // 피벗 기준 앞
	quickSort(list, back + 1, end); // 피벗 기준 뒤
}

static void swap(int list[], int i, int j) {
	int tmp = list[i];
	list[i] = list[j];
	list[j] = tmp;
}


연습문제

BOJ 11004 : K번째 수 (Silver V)


참고

Do it! 알고리즘 코딩 테스트: 자바 편


알고리즘, 정리
알고리즘 정렬 버블 정렬 선택 정렬 삽입 정렬 퀵 정렬 병합 정렬 기수 정렬