퀵정렬

  • 내부정렬 : 추가적인 리스트를 사용하지 않는 정렬(Quick Sort Algorithm: Hoare, 1962)
  • 퀵정렬

    Divide: 기준 원소를 정해서 좌우로 분할
    Conquer: 왼쪽/오른쪽 리스트를 각각 재귀적으로 정렬
    Obtain: 정렬된 리스트를 리턴

파이썬으로 퀵정렬

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def quicksort(S, low, high):
    if (high > low):
        pivotpoint = partition(S, low, high)
        quicksort(S, low, pivotpoint - 1)
        quicksort(S, pivotpoint + 1 , high)

def partition(S, low, high):
    pivotitem = S[low]
    j = low
    for i in range(low + 1, high + 1):
        if(S[i] < pivotitem):
            j += 1;
            S[i], S[j] = S[j], S[i] # swap 2 items
    pivotpoint = j
    S[low], S[pivotpoint] = S[pivotpoint], S[low] # swap 2 items
    return pivotpoint
  • 기준원소(pivotpoint)를 어떻게 정할까? : 편의상 첫 원소를 기준 원소로 정한다
  • 두 개의 인덱스(i, j)를 이용해서 비교하고 교환한다

자바스크립트로 퀵정렬 (기준 원소가 배열의 맨마지막 요소일 때)

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
function quickSort (arr, start, end) {
    if (start >= end) return;

    let index = partition(arr, start, end);
    quickSort(arr, start, index - 1);
    quickSort(arr, index + 1, end)

}

function partition (arr, start = 0, end = arr.length - 1) {
    let pivotIndex = start;
    let pivotValue = arr[end];
    for(let i = start; i < end; i++){
        if(arr[i] < pivotValue) {
            swap(arr, i, pivotIndex);
            pivotIndex++
        }
    }
    swap(arr, pivotIndex, end);
    return pivotIndex;
}

function swap (arr, a, b) {
    let temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}

참고영상 : Coding Challenge #143​: Quicksort Visualization

퀵정렬(분할 교환 정렬)

파이썬으로 퀵정렬 할 때 다른 방법으로 파티션 구하기

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def partition2 (S, low, high):
    pivotitem = S[low]
    i = low + 1
    j = high
    while (i <= j):
        while (S[i] < pivotitem):
            i += 1
        while (S[j] > pivotitem):
            j -= 1
        if (i < j):
            S[i], S[j] = S[j], S[i] # swap 2 items
        pivotpoint = j
        S[low], s[pivotpoint] = S[pivotpoint], S[low] # swap 2 items 
        return pivotpoint

자바스크립트로 퀵정렬 할 때 다른 방법으로 파티션 구하기

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function partition2 (array, start, end) {
    // 맨 마지막이나 맨 처음으로 설정했던 pivot값을 배열의 중간값으로 설정
	const pivotValue = array[ Math.floor((start + end) / 2) ];

    // 양 끝의 인덱스를 하나씩 늘리거나 하나씩 줄이면서
    // 피봇값보다 작은 값인 start와 피봇값보다 큰 값인end값을 구함
	while (start <= end) { 
		while (array[start] < pivotValue) start = start + 1;
		while (array[end] > pivotValue) end = end - 1;
        
        // start값이 end값보다 크단 뜻은 배열을 한번 다 돌았다는 뜻임
		if (start <= end) { 
            // 이 구문을 들어온다는 뜻은 배열을 돌면서 pivotValue보다 
            // 큰 값(array[start]값)과 작은 값(array[end]값)의 두 값을 교체해줌
			swap(array, start, end);
			start = start + 1;
			end = end - 1;
		}
	}
    // 이 과정이 끝나면 pivotValue보다 작은 값은 왼쪽에, 큰 값은 오른쪽으로 정렬되었단 뜻이므로 
    // 해당 인덱스 값을 리턴하여 다시 배열을 둘로 쪼갬
	return start; 
}