프로그래밍 문제를 풀면서 리스트 정렬을 해야 하는 경우가 많아서 쉬운 알고리즘 부터 공부를 하기 시작했다. Quick Sort가 이해하기 쉬운 알고리즘 중 하나 인듯하여서 SW Expert Academy에서 제공하는 코드를 보면서 공부를 해보았다 (출처 1). 아래 코드는 SW Expert Academy에서 제공하는 코드를 가져와 정말 살짝 변경하였다.
void quickSort(int list[], int begin, int back) { if (begin < back) { int pivot = begin; int i = begin; int j = back; int tmp = 0; while (i < j) { while (list[i] <= list[pivot] && i < back) { i++; } while (list[j] > list[pivot]) { j--; } if (i < j) { tmp = list[i]; list[i] = list[j]; list[j] = tmp; } } tmp = list[pivot]; list[pivot] = list[j]; list[j] = tmp; quickSort(list, begin, j - 1); quickSort(list, j+1, back); } }
위 코드를 실행하여 [3, 2, 1, 3, 7, 6, 5, 4, 2]를 정렬하는 순서를 아래 그림으로 정리해보았다.
그림 1. Quick Sort 예제 순서도
순서도
- Start: 먼저 Pivot이라고 해서 기준값을 정하고, i 와 j 포인터를 리스트 처음과 끝에 위치시킨다.
- Step1 (S1): i 포인터가 가리키는 값이 Pivot보다 클 때 까지 i를 오른쪽으로 이동한다. (i++를 해줌)
- S2: j 포인터가 가리키는 값이 Pivot보다 크면 j를 왼쪽으로 이동한다 (j–를 해줌). 위 예제의 경우 마지막 j 포인트가 가리키는 값이 pivot보다 작기 때문에 움직이지 않았다.
- S3: i와 j가 가리키는 값을 서로 변경한다.
- S4: i와 j의 위치가 서로 동일하거나 i가 j보다 왼쪽에 위치 할 때 까지 S2와 S3을 반복한다.
- S5: Pivot이 가리키는 값과 j가 가리키는 값을 서로 변경한다.
- S6: j-1 이전 리스트와 j+1 이후 리스트를 나누어서 S1~S5를 계속 반복한다.
- END: 순서가 정리된 것을 확인할 수 있다.
생각보다 단순한 알고리즘인데 이것을 이해하는데 거의 하루가 걸렸다. 그리고 여러 번 혼자서 다시 작성을 해보았지만, 아직도 한 번에 제대로 코딩을 하지 못하고 있다. 아래 출처 2에 따르면 Quick Sort의 경우 평균 실행 시간이 O(log N)이고 최악의 경우 O(N^2)만큼 걸린다고 한다. 개인적으로 공부를 하고 싶어서 해당 그림을 만들어보았다. 하지만, 출처 2 사이트를 방문하면 동영상으로 설명이 더 잘되어있다.
출처
- https://www.swexpertacademy.com
- http://zeddios.tistory.com/35