[알고리즘] - 정렬 알고리즘(삽입 정렬, 선택 정렬, 버블 정렬, 합병 정렬, 퀵 정렬, 힙 정렬)

1. 삽입 정렬 (Insertion Sort)

설명

이미 정렬이 된 부분과 되지 않는 부분을 나누면서 정렬한다.
배열의 앞의 요소부터 차례대로 이미 정렬이 된 부분과 비교하여, 적합한 위치를 찾아 삽입하는 알고리즘이다.
두번째 요소부터 왼쪽의 요소들(이미 정렬이 된 부분)과 비교하여 삽입 위치를 찾아야한다.
이미 정렬이 된 부분과 비교연산을 할때는, 왼쪽으로 옮겨가며 비교를 하여 삽입 위치를 찾는다.
 

예시

1. [5, 3, 8, 1, 2, 7] → 두번째 원소인 3과 왼쪽의 이미 정렬된 배열인 [5] 와 비교
     - 3과 5를 비교했을 때 5보다 작기 때문에 5를 한칸 뒤로 이동 : [3, 5]
 
2. [3, 5, 8, 1, 2, 7] → 세번째 원소인 8과 왼쪽의 이미 정렬된 배열인 [3, 5] 와 비교
     - 8과 5를 비교했을 때 5보다 크기 때문에 그대로 : [3, 5, 8]
 
3. [3, 5, 8, 1, 2, 7] → 네번째 원소인 1과 왼쪽의 이미 정렬된 배열인 [3, 5, 8]과 비교
     1) 1과 8을 비교했을 때 8보다 작기 때문에 8을 한칸 뒤로 이동 : [3, 5, 1, 8]
     2) 1과 5를 비교했을 때 5보다 작기 때문에 5를 한칸 뒤로 이동 : [3, 1, 5, 8]
     3) 1과 3을 비교했을 때 3보다 작기 때문에 3을 한칸 뒤로 이동 : [1, 3, 5, 8]
 
…
마지막 원소까지 반복 → [1, 2, 3, 5, 7, 8]
 
 

코드

private static void insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        for (int j = i-1; j >=0; j--) {
            if(arr[j] > arr[i]) {
                int tmp = arr[j];
                arr[j] = arr[i];
                arr[i] = tmp;
            } else {
                break;
            }
        }
    }
}

 
 

시간 복잡도

평균, 최악의 경우 : O(n^2)
최선의 경우 : 한번의 비교 연산을 한 후 이동이 없다면(즉, 모두 정렬 되어있다면) O(n)
 
평균 시간복잡도가 O(n^2)인 정렬들(삽입, 선택, 버블) 중에선 가장 빠르다.
대부분 정렬이 이미 되어 있다면 효율적이게 됨.
 
 

---

2. 선택 정렬 (Selection Sort)

설명

심플하지만 비효율적인 알고리즘
배열을 선형탐색하며 가장 작은 원소를 배열 맨 앞으로 보내 맨 앞에 있던 원소와 자리를 바꿈 → 남은 값들 중 제일 작은 원소를 찾은 뒤 두번째 위치에 보냄 → …(마지막까지 반복)
 

예시

1. [5, 3, 8, 1, 2, 7] → [1, 3, 8, 5, 2, 7] : 첫번째 원소 5와 최솟값 1을 교체
2. [1, 3, 8, 5, 2, 7] → [1, 2, 8, 5, 3, 7] : 두번째 원소 3과 최솟값 2를 교체
3. [1, 2, 8, 5, 3, 7] → [1, 2, 3, 5, 8, 7] : 세번째 원소 8과 최솟값 3을 교체
…
마지막 원소까지 반복 → [1, 2, 3, 5, 7, 8]
 
 

코드

private static void selectionSort(int[] arr) {
	for (int i = 0; i < arr.length-1; i++) {
		int minIdx = i;
		for (int j = i+1; j < arr.length; j++) {
			if(arr[minIdx] > arr[j]) {
				minIdx = j;
			}
		}
		int tmp = arr[i];
		arr[i] = arr[minIdx];
		arr[minIdx] = tmp;
	}
}

 
 

시간복잡도

최선, 평균, 최악의 시간복잡도 : O(n^2)
 
첫번째는 배열의 크기 (n-1)만큼 비교연산 하고, 다음은 (n-2)만큼, (n-3), …, 1 까지 비교연산을 한다.
즉 (n-1) + (n-2) + … + 2 + 1 = n(n-1)/2 이므로 O(n^2) 이다.
선택정렬은 구현하기에 단순하지만, 비효율적이라고 볼수 있다.
 

 

---

3. 버블 정렬 (Bubble Sort)

설명

배열의 앞 요소부터 차례대로 진행하며, 서로 인접한 두 요소를 비교하여 바꾸면서 정렬하는 알고리즘
오름차순으로 정렬한다고 할 때, 현재 요소가 다음 요소보다 크면 두 요소를 바꾼다.
 
 

예시

첫번째 탐색
1-1. [5, 3, 8, 1, 2, 7] → [3, 5, 8, 1, 2, 7] : 첫번째 요소 5 > 두번째 요소 3 이므로 두 요소를 바꾼다.
1-2. [3, 5, 8, 1, 2, 7] → [3, 5, 8, 1, 2, 7] : 두번째 요소 5 < 세번째 요소 8 이므로 그대로
1-3. [3, 5, 8, 1, 2, 7] → [3, 5, 1, 8, 2, 7] : 세번째 요소 8 > 네번째 요소 1 이므로 두 요소를 바꾼다.
…
마지막 요소까지 반복하면 [3, 5, 1, 2, 7, 8] : 여기까지가 한번의 탐색이다.
가장 맨 끝으로 가장 큰 값이 이동했으므로 맨 끝을 빼고 다음 탐색을 시작한다.
 
두번째 탐색
2-1. [3, 5, 1, 2, 7, 8] → [3, 5, 1, 2, 7, 8] : 첫번째 요소 3 < 두번째 요소 5 이므로 그대로
2-2. [3, 5, 1, 2, 7, 8] → [3, 1, 5, 2, 7, 8] : 두번째 요소 5 > 세번째 요소 1 이므로 두 요소를 바꾼다.
…
마지막 요소인 8을 빼고 7까지 반복하여 두번째 탐색을 끝낸다.
뒤에서 두번째까지 정렬을 완료했으므로 뒤에서 두개의 요소를 빼고 다음 탐색을 시작한다.
이런식으로 모든 요소를 정렬한다.
 
 

코드

private static void bubbleSort(int[] arr) {
	for (int i = arr.length-1; i >=0; i--) {
		for (int j = 0; j < i; j++) {
			if(arr[j] > arr[j+1]) {
				int tmp = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = tmp;
			}
		}
	}
}

 
 

시간 복잡도

최선, 평균, 최악 시간복잡도 : O(n^2)
 
비교 연산이 (n-1) + (n-2) + … + 2 + 1 = n(n-1)/2 이므로 시간복잡도가 O(n^2)가 된다.
 

---

4. 합병 정렬 (Merge Sort)

설명

병합 정렬이라고도 한다.
배열을 절반씩 나누어 각각 정렬한 후에 합친 후 다시 정렬하는 알고리즘이다. (분할 정복법 사용)
 
 

예시

배열을 절반씩 분할하는 Divide, 부분 배열을 정렬하면서(Conquer) 하나의 배열에 합병(Combine)합니다.
여기서 정렬하면서 합병하는 방법은 다음과 같습니다.
두 부분 배열이 있을 때, 예를 들어 위의 경우에서 [6,7]과 [5,8]을 합병할때는
두 배열의 값들을 처음부터 하나씩 비교하여 더 작은 값을 새로운 배열로 옮깁니다.
 
1. [6,7] 과 [5,8]의 첫번째 값인 6과 5중 5가 더 작기 때문에 새로운 배열로 옮깁니다. → [ 5 ]
2. [6,7] 과 [8] 의 6과 8중 6이 더 작기 때문에 새로운 배열로 옮깁니다. → [5, 6]
3. [7] 과 [8]의 7과 8중 7이 더 작기 때문에 새로운 배열로 옯깁니다. → [5, 6, 7]
4. [8]. 남은 값들을 모두 옮깁니다. → [5, 6, 7, 8]
 
실제 코드로 구현할 때는, 두 배열의 0번째 인덱스부터 비교한 후, 새로운 배열에 옮긴 부분 배열의 인덱스는 1씩 증가시켜주면 됩니다.
 
 

코드

private static void mergeSort(int[] arr, int[] result, int start, int end) {
	if(start < end) {
		int mid = (start + end) / 2;
		mergeSort(arr,result, start, mid);
		mergeSort(arr,result,  mid+1, end);

		int left = start, right = mid + 1;
		int idx = left;

		while(left<=mid || right<=end) {
			if(right > end || (left <= mid && arr[left] < arr[right])) {
				result[idx++] = arr[left++];
			} else {
				result[idx++] = arr[right++];
			}
		}

		for (int i = start; i <= end; i++) {
			arr[i] = result[i];
		}
	}
}

 
 

시간 복잡도

최선, 평균, 최악의 경우 모두 O(N * logN) 이다.
 
데이터 분포에 영향을 덜 받는 효율적인 방법이다.
정확히 절반씩 나누기 때문에 최악의 경우에도 O(NlogN)을 보장한다.
재귀 호출의 깊이가 n → n/2 → n/4 → … → 1 이므로 O(logN)이다.
여기에 각 합병 단계에서 최대 n번씩 비교 연산을 하기 때문에 n을 곱해줘서 O(N*logN)이다.

 

---

5. 퀵 정렬 (Quick Sort)

설명

퀵 정렬은 매우 빠른 정렬 알고리즘이며, 분할 정복법을 사용한다.
그러나 합병정렬과 달리 비균등하게 분할. 피벗(pivot)을 사용하여 두개의 리스트로 나누는 방법
 
피벗을 고른 후에 피벗보다 작은 원소들은 모두 피벗의 왼쪽으로 옮겨주고, 피벗보다 큰 요소들은 모두 피벗의 오른쪽으로 옮겨진다.
피벗의 왼쪽 리스트와 오른쪽 리스트 즉, 분할된 부분 리스트를 각각 재귀 호출하여 반복한다.
그때도 피벗을 정한 후에 두 개의 리스트로 나누는 것을 반복한다.
더 이상 분할이 안될때까지 반복
 
 

예시

1. [3, 7, 8, 1, 5, 9, 6, 2, 4]
1) 피벗은 첫번째 원소인 3.
2) 피벗을 기준으로 오른쪽으로 가면서 피벗값보다 큰 값을 탐색. 두번째 원소인 7이 큰 값임
3) 피벗을 기준으로 왼쪽으로 가면서 피벗값보다 작은 값 탐색. 여덟번째 원소인 2가 작은 값
4) 이 두 원소의 자리를 바꿈(swap) → [3, 2, 8, 1, 5, 9, 6, 7, 4]
 
2. [3, 2, 8, 1, 5, 9, 6, 7, 4]
1) 피벗은 첫번째 원소인 3.
2) 피벗을 기준으로 오른쪽으로 가면서 피벗값보다 큰 값을 탐색. 세번째 원소인 8이 큰 값임
3) 피벗을 기준으로 왼쪽으로 가면서 피벗값보다 작은 값 탐색. 네번째 원소인 1이 작은 값
4) 이 두 원소의 자리를 바꿈(swap) → [3, 2, 1, 8, 5, 9, 6, 7, 4]
 
3. [3, 2, 1, 8, 5, 9, 6, 7, 4]
1) 피벗은 첫번째 원소인 3.
2) 피벗을 기준으로 오른쪽으로 가면서 피벗값보다 큰 값을 탐색. 네번째 원소인 8이 큰 값임
3) 피벗을 기준으로 왼쪽으로 가면서 피벗값보다 작은 값 탐색. 세번째 원소인 1이 작은 값
4) 큰 값이 작은 값이 엇갈리면(큰 값의 인덱스<작은 값의 인덱스), 작은 값과 피벗을 바꿈(swap) → [1, 2, 3, 8, 5, 9, 6, 7, 4]
5) 피벗(3)을 기준으로 왼쪽과 오른쪽으로 2개의 리스트가 나누어짐. 왼쪽은 3보다 작은 수들, 오른쪽은 3보다 큰 수들이 된다. 이 두 개의 리스트를 재귀 호출하여 독립적으로 반복 수행
 
4. [1,2] 수행, [8, 5, 9, 6, 7, 4] 수행.
…
배열의 크기가 1이하가 될때까지 반복
 
 
 

코드

private static void quickSort(int[] arr, int pivot, int end) {
	if(pivot >= end) return;

	int left = pivot + 1, right = end;
	while(true) {
		while(left <= end && arr[pivot] >= arr[left]) {
			left++;
		}

		while(right > pivot && arr[pivot] <= arr[right]) {
			right--;
		}

		if (left > right) {
			int tmp = arr[right];
			arr[right] = arr[pivot];
			arr[pivot] = tmp;
			quickSort(arr, pivot, right-1);
			quickSort(arr, right+1, end);
			break;
		} else {
			int tmp = arr[left];
			arr[left] = arr[right];
			arr[right] = tmp;
		}
	}
}

 
 

시간 복잡도

최선, 평균의 경우 : O(N logN)
최악의 경우 : O(n^2)
 
재귀 호출의 깊이가 n/2 → n/4 → … → 1 이므로 O(logN)이고,
각 단계에서 전체 원소를 돌면서 비교해야하기 때문에, 평균 N번 비교로 O(N * logN)이다.
그러나 무작위로 선정된 한 원소를 사용하여 배열을 분할하고, 이 원소가 중간값에 가까운 값이 되리라는 보장이 없어서 치우치게 되면, 느리게 동작할 수 있다.
최악의 경우 배열이 계속해서 불균형하게 나누어질 경우 (이미 정렬된 리스트), 재귀 호출의 깊이가 N이 되기 때문에 O(N^2)이 된다.

 

---

6. 힙 정렬 (Heap Sort)

설명

힙은 완전 이진 트리를 기반으로 우선순위 큐를 위하여 만들어진 자료구조.
최댓값과 최솟값을 빠르게 추출할 수 있음
최대 힙은 내림차순 (트리의 루트노드가 가장 큰값), 최소 힙은 오름차순 정렬(루트노드가 가장 작은값)이다.
 
힙 정렬은 힙 생성 알고리즘 (Heapify)를 적용하여 힙 구조를 만드는 것이다.
Heapify는 부모노드와 자식노드의 크기를 비교하여 적절하게 서로 바꿔주는 것이다.
노드 개수만큼 힙 생성 알고리즘을 수행하여 힙 구조를 만든다.
 
 

시간 복잡도

최선, 평균, 최악의 경우 : O(N logN)
 
힙 트리의 전체 높이는 logN이므로 (완전이진트리) O(logN)이고,
전체 노드의 개수가 n개이므로 총 O(N * logN)이 걸림
 
 
 
 
 

---

 결론 

비효율적이나 구현은 쉬운 정렬 알고리즘 : 삽입 정렬, 선택 정렬, 버블 정렬
효율적이고 구현이 복잡한 정렬 알고리즘 : 합병 정렬, 퀵 정렬, 힙 정렬

	최선	평균	최악
삽입 정렬	N	N^2	N^2
선택 정렬	N^2	N^2	N^2
버블 정렬	N^2	N^2	N^2
합병 정렬	NlogN	NlogN	NlogN
퀵 정렬	NlogN	NlogN	N^2
힙 정렬	NlogN	NlogN	NlogN