Quick Sort with Swift

Quick Sort 

Quick Sort 는, Pivot 을 정해서 Pivot 에 따라 더 작은 값들,  더 큰 값 들을 나눈 후 나뉜 값들에 대해 

다시 Pivot 을 정한 후 더 작은 값들, 더 큰 값을 나누는 행위를 반복하면서 마지막에는 정렬된 array 를 합치며 Sorting 하는 방법이에요.

 

예시를 통해 과정을 설명드릴게요

1.0.  8 개의 element 가 array 에 있다고 가정해볼게요. 

[6, 5, 3, 1, 8, 7, 2, 4]

1.1.  Pivot 을 하나 정합니다. (가장 뒤에 있는 값으로 설정하겠습니다.)  4가 Pivot value 가 되었습니다 !

 

1.2.  array 에서 가장 앞에 있는 값 6 과 4를 비교합니다. 6 > 4 이므로, 6이 4의 뒤에 있으면 좋겠네요.

그렇게 하기 위해서는 2 가 자리를 바꿔주어야 합니다. 6이 들어갈 자리가 마지막에 필요하거든요.

 

따라서, 먼저 4 를 2 의 자리로 잠시 이동시킵니다. 4 자리가 비었으므로, 6 을 뒤쪽 끝 (4 자리) 로 위치시킵니다. 

이제 6 의 자리가 비었네요. 2 를 6 이 있던 자리로 이동시킵니다.

 

결국 순서 <6, 2, 4> 를 <2, 4, 6> 으로 바꿔주게 됩니다. (숫자 세개만 switch)

// [6, 5, 3, 1, 8, 7, 2, 4]
[2, 5, 3, 1, 8, 7, 4, 6]

1.3.  2 와 4 를 비교합니다. 2 < 4 이므로, 지금 옮겨진 자리에 그대로 있어도 됩니다.

1.4.  5 와 4 를 비교합니다. 5 > 4 이므로, 2번 과정과 마찬가지로, <5, 7, 4> 순서를 <7, 4, 5 > 로 바꿔줍니다. 

// [2, 5, 3, 1, 8, 7, 4, 6]
[2, 7, 3, 1, 8, 4, 5, 6]

1.5. 이제 7 과 4 를 비교합니다. 7 > 4 이므로, 세 숫자 <7, 8, 4> 의 배열을 <8, 4, 7> 로 바꿔줍니다. 

 

// [2, 7, 3, 1, 8, 4, 5, 6]
[2, 8, 3, 1, 4, 7, 5, 6]

1.7.  8 과 4 를 비교합니다. 8 > 4 이므로, 세 숫자 <8, 1, 4> 을 <1, 4, 8> 로 바꿔줍니다.

// [2, 8, 3, 1, 4, 7, 5, 6]
[2, 1, 3, 4, 8, 7, 5, 6]

1.8.  드디어 정렬이 한번 완료되었습니다.

이제 4의 좌측에는 4보다 작은 값들만, 4의 우측에는 4보다 큰 값들만 모였습니다! 

[2, 1, 3, 4, 8, 7, 5, 6]
[2, 1, 3], [4], [8, 7, 5, 6]

 

 

 

아직 끝난게 아닙니다. 하지만, [2,1,3] 과 [8,7,5,6] 을 sorting 한 결과 Pivot 값 4 는 위치가 정해진 걸 알 수 있습니다.

이제, [2, 1, 3] 과 [8, 7, 5, 6] 을 Sorting 해야하고 과정을 위와 동일합니다. 상세한 과정은 이미 설명이 된 것 같으니 간략하게 나머지 과정에 대해 서술하도록 하겠습니다.

 

2.1  [2, 1, 3] 에 대해서, Pivot 을 또 다시 우측 끝에 있는 값으로 잡고 Sort 작업을 실행합니다.

// [2, 1, 3]
[2, 1], [3]

Pivot 값이 가장 큰 값이었어서 다시 한번 진행이 필요합니다.

2.2  [2, 1] 이 남았으므로, [2, 1, 3] 에 대한 sorting 결과는 다음과 같습니다.

[1, 2], [3]

 

이제 [8, 7, 5, 6] 에 대해 다시 Sorting 해봅시다.

2.3  6 을 Pivot Point 로 잡고 sorting 을 진행합니다.

// [8, 7, 5, 6]
// [5, 7, 6, 8]
 [5, 6, 7, 8]

2.4  [5, 6, 7, 8] 이 결과로 도출되었고, 이는 

[5], [6], [7, 8]

로 나뉠 수 있습니다. 

 

이제는 드디어 모든 값이 1개 또는 2개의 elements 로 나뉘었습니다 !!

[1, 2], [3], [4], [5], [6], [7, 8]

이 상자들을 다시 한 데에 차례차례 합쳐주시면 sorting 된 array 가 구해집니다 !!

[1, 2, 3, 4, 5, 6, 7, 8]

 

 

Quick Sort 은 지금까지 알아보았던 5가지 Algorithm 중 가장 방법이 복잡해보이지만 Average case 에 대해서는 가장 빠릅니다.

이미 어느정도 Sorting 된 경우에 대해서는 많이 느리겠죠..? 이 경우에는 Insertion Sort 가 더 적당할 것입니다. 

 

 

 

 

 

 

 

 

아래는 Swift 로 정말 간단히 만들어본 quickSort 입니다. ( 전에 만든 mergeSort 와 비슷하게 만들어보았습니다. )

func quickSort(_ arr: [Int]) -> [Int] {
    if arr.count > 1 {
        let pivot = arr[arr.count - 1]
        let leftArr = arr.filter { $0 < pivot}
        let middleArr = arr.filter { $0 == pivot }
        let rightArr = arr.filter { $0 > pivot }
        
        return quickSort(leftArr) + middleArr + quickSort(rightArr)
    }
    return arr
}

quickSort([6, 5, 3, 1, 8, 7, 2, 4])

array 가 quickSort 의 parameter 로 들어오면 array 뒤쪽 마지막 값 (취향..어떤 값이든지 하나의 위치를 pivot 으로 설정했습니다.) 을 기준으로 더 작은 값들, 같은 값들, 큰 값들을 각각 leftArr, middleArr, rightArr 로 나누어줍니다. 

 

그 후 leftArr, rightArr 에 다시 quickSort function 을 적용시킨 후 세 Array (정렬된 배열) 을 차례로 나열해줍니다. 

 

Recursion 을 사용하였고, terminating 조건을 array 의 element 가 0개 또는 1 개 있을 때로 정해주었습니다. (pivot 값에 따라 leftArr, rightArr 중 하나는 값이 0개 들어있을 수 있기 때문이죠. 만약 처음부터 같은 값들만 있는 array 라면 둘다 값이 들어있지 않겠네요. ) 

 

따라서, quickSort 로부터 return 되는 array 는 비었거나, 요소가 하나이거나, 혹은 정렬된 여러 elements 를 가진 array 가 올 수밖에 없습니다.

 

각각의 array 를 leftArr, middleArr, rightArr 로 나누는 과정에 대한 Time Complexity 는 O(n),

여러개의 elements 를 가진 array 를 하나 또는 0 개의 element 로 갖게되기 까지의 과정에 대한 Time Complexity 는 O(log n) ,

두 과정이 서로 연결되어 있기 때문에 결국 Time Complexity 는 O ( n * log n ) 을 갖게 됩니다.