[Algorithm] 퀵 정렬 알고리즘 (Quick Sort Algorithm)

프로그래밍 문제를 풀면서 리스트 정렬을 해야 하는 경우가 많아서 쉬운 알고리즘 부터 공부를 하기 시작했다. 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 사이트를 방문하면 동영상으로 설명이 더 잘되어있다.

출처

  1. https://www.swexpertacademy.com
  2. http://zeddios.tistory.com/35

 

 

Leave a Comment