DevAlgorithm

[Algorithm] Quick sort

  1. 1. 알고리즘
  2. 2. Psuedocode
  3. 3. Implementation
  4. 4. 참조

한 평생 Bubble sort만 사용하다가 이대로 계속 무식하면 안되겠다 싶어서 찾아보았다.

Quick sort는 Charles Antony Richard Hoare 경에 의해 개발되었다.

알고리즘

  1. List 중 하나의 Element를 선택한다. 이를 Pivot 이라 부른다.
  2. Pivot을 기준으로 좌측에는 작은 Element들이 오도록, 우측에는 큰 Element들이 오도록 나눈다. 이 과정을 분할 (Divide)이라 한다.
  3. 분할한 두 개의 좌, 우측 List에 대해 재귀적으로 이 과정을 반복한다. List의 크기가 0 또는 1이 될 때까지 반복한다.

Psuedocode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void QuickSort (Element* list, const int left, const int right)
{
	if (left < right) {
		int i = left;
		int j = right + 1;
		pivot = list[left].getKey();
		do {
			do i++; while(list[i].getKey() < pivot);
			do j--; while(list[j].getKey() > pivot);
			if (i < j) {
				InterChange(list, i, j);
			}
		} while (i < j);
		InterChange(list, left, j);
		QuickSort(list, left, j - 1);
		QuickSort(list, j + 1, right);
	}
}

위의 Psuedocode는 pivot 지점을 list의 좌측 즉, 시작점인 left로 설정한다.

right는 우측 끝 값이며, j는 아래의 while문 처리를 위해 right + 1로 설정한다.

좌측 값이 pivot보다 작으면 무시하고 우측 값이 pivot보다 크면 무시하게끔 while문이 돌아간다.

좌측에서 발견한 pivot보다 큰 값과 우측에서 발견한 pivot보다 작은 값을 교환한다.

이를 i와 j의 위치가 역전될 때까지 반복한다.

이 때 j는 pivot보다 작은 값이 위치하게 되기 때문에 pivot과 자리를 바꾼다.

Implementation

Java로 구현하면 아래와 같이 된다. Psuedocode대로 구현하면 제대로 동작하지 않아 조금 수정하였다.

다시 구현하라고 하면 못할 것 같다…

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
46
47
48
49
50
51
52
53
public class QuickSort {
	public static void main(String[] args) {
	    int data[] = {66, 10, 34, -10, 200, 5, 2, 1, 1, 1, 5, 2, 3, -20, 5, 3, 65, -2};
	    
	    aSort(data, 0, data.length - 1);
	}
	public static void aSort(int[] data, int left, int right) {	
		if (left < right) {
			int fromLeft = left; // 좌측부터 우측으로 이동하는 offset
			int fromRight = right; // 우측부터 좌측으로 이동하는 offset
			int pivot = data[(left + right) / 2]; // 정렬의 기준이 되는 pivot. 여기서는 중앙값으로 정했다.
			while (fromLeft < fromRight) {
				while (data[fromLeft] < pivot) {
					fromLeft++; // pivot값의 좌측에 큰 값이 나올 때까지 이동
				}
				while (data[fromRight] > pivot) {
					fromRight--; // pivot값의 우측이 작은 값이 나올 때까지 이동
				}
				
				// 작은 값과 큰 값을 서로 교체.
				// 그 값들은 이제 제 자리를 찾았으니 다음 index로 넘어감
				if (fromLeft < fromRight) {
					swap(data, fromLeft, fromRight);
					fromLeft++;
					fromRight--;
				// 같은 값을 가진다면 swap동작 안함.
				} else if (fromLeft == fromRight) {
					fromLeft++;
					fromRight--;
				}
			}
			// fromRight offset이 fromLeft offset보다 왼쪽에 가 있는 상태에서...
			if (left < fromRight) {
				// pivot값보다 작은 쪽 그룹에 대해 QuickSort
				aSort(data, left, fromRight);	
			}
			if (fromLeft < right) {
				// pivot값보다 큰 쪽 그룹에 대해 QuickSort
				aSort(data, fromLeft, right);	
			}
		}		
	}
	public static void swap(int[]data, int left, int j) {
		int temp = data[left];
		data[left] = data[j];
		data[j] = temp;
	}
}

참조

Share