소팅 알고리즘 정리 (Bubble, Quick, Insert, Select, Heap)

본 글을 위 소팅 알고리즘을 한번 씩은 다뤄 본 사람들을 대상으로 기억을 되살리기 위해 적은 글이므로, 처음 보는 사람들은 좀 더 자세하게 포스팅된 글을 참고하기 바란다.

설명의 편의를 위해 모든 정렬은 오름차순을 기준으로 한다.

 

1. Bubble Sort (버블 소트)

구현하기가 가장 편해 정말 작은 input이 들어오거나, 효율성이 필요 없거나, 개발을 빠르게 해야 할 때 사용한다. 첫 번째와 두 번째 열을 비교하여 두 번째 열이 첫 번째 열 보다 작다면 두 열을 swap한다. 그 다음 두 번째 열과 세 번째 열을 비교하고, 그 다음은 세 번째, 네 번째를 비교하며 마찬가지 과정을 거친다. 이렇게 하면 가장 큰 값이 가장 마지막으로 이동되게 된다. 이젠 가장 뒷 열을 제외하고 나머지 열을 상대로 이런 과정을 반복하면 가장 뒤의 2열의 정렬이 완료된다. 이런 과정을 가장 첫 열까지 반복하게 되면 정렬된 결과를 볼 수 있다.

 

2. Selection Sort (선택 정렬)

버블 소트보다 조금 더 개선된 알고리즘이다. 버블 소트보다 효율성이 조금 더 좋은 정도이다. 가장 첫 열의 값을 기준으로 잡고, 나머지 열을 하나씩 순회하여 값을 체크하여 가장 작은 값을 첫 열의 값과 swap한다. 그리고 두 번째 열의 값을 기준으로 잡고 나머지 값들 중 가장 작은 값을 찾아 두 번째 열과 swap한다. 이런 과정을 n-1열까지 거치게 되면 정렬된 결과 값이 나온다.

 

2. Insertion Sort (삽입 정렬)

열을 하나씩 선택하여 그 열이 들어갈 위치에 삽입하는 방식을 사용하는 알고리즘으로, 위 두 알고리즘 보다는 효율이 더 좋다.

일단 두 번째 열을 선택하여 두 번째 열이 첫 번째 열 보다 작다면 첫 번째 자리에 끼워 넣는다. 이제 세 번째 열을 선택하여 앞선 두 열중 세 번째 열보다 큰 열이 있다면 그 앞의 자리로 끼워 넣는다. 이렇게 가장 마지막 열까지 비교하여 그 열의 값이 들어가야 할 위치에 차례차례 끼워 넣어주면 정렬이 된다.

5, 4, 3, 2, 1

을 오름차순으로 정렬한다고 할때 1회전 후의 결과는

4, 5, 3, 2, 1

이다.

 

3. Quick Sort (퀵 소트)

특정 기준점을 하나 잡고 그 기준점의 값보다 작은 값은 모두 왼쪽에, 큰 값은 모두 오른쪽으로 옮긴다. 그리고 두개로 나눠진 구간에서 한 번 더 기준점을 잡아서 더 작은 구간으로 나눈다. 이렇게 더 이상 쪼갤 수 없는 단계까지 나누다 보면 어느새 정렬이 이루어진다. Divide and Conquer 알고리즘의 대표적인 예로, 많은 경우에서 가장 우수한 효율을 보여준다. 재귀함수를 이용해서 구현한다.

 

3. Heap Sort (힙 소트)

힙이라는 자료 구조를 이용한 정렬. Min Heap을 기준으로 설명하면, 힙은 부모노드가 자식노드보다 항상 작도록 정리된 Complete binary tree이다. 자료를 하나씩 넣을 때 마다 부모 값, 자식 값과 비교하여 이 규칙을 유지한다. 힙이 구성되고 나면 가장 Root 노드가 가장 작은 값이 된다. Root 노드의 빈자리에 리프 노드의 맨 끝에 있는 값이 들어가게 된다. 규칙이 맞지 않으면 다시 힙을 정리 한다. 그럼 또 Root노드에 있는 값이 남은 값중 가장 작은 값이 된다. 이런 과정을 반복해서 정렬된 값을 출력한다. 설명은 복잡해 보이고 코드의 길이도 짧진 않다. 그러나 Quick Sort보다 더 높은 효율을 보여 줄 때도 있을 만큼 안정성 있는 알고리즘이다.

 

 

Name	Best	Average	Worst	Memory	Stable
Quicksort	nlogn	nlogn	n2	(Stack)logn	No
Merge sort	nlogn	nlogn	nlogn	O(n)	Yes
In-place MS	-	-	n(logn)2	1	Yes
Heapsort	nlogn	nlogn	n2	1	No
Intertion sort	n	n2	n2	1	Yes
Selection sort	n2	n2	n2	1	No