Array Sorting Algorithms

배열을 Sorting 하는 방법에는 

 

• Bubble Sort
• Selection Sort
• Insertion Sort

 

• Merge Sort
• Quick Sort

 

등이 있습니다.

 

Bubble, Insertion, Selection Sort는 상대적으로 단순한 정렬 방식이고, 

Merge, Quick Sort 는 위 Sorting 방법들보다 약간 복잡해요. 

 

우선, 이번 글에서는 각 Sorting 방법의 작동 원리부터 알아보도록 하겠습니다. 

 

 

1. Bubble Sort

Bubble Sort는, 앞에서부터 2개씩 element 를 잡아서 정렬하는 방법이에요.

1 ~ 5 까지의 숫자가 임의로 배열에 하나씩 있다고 해볼게요.  ( 앞으로 모든 예시는 오름차순을 목표로 정렬하는 것으로 가정할게요 )

 

[4, 3, 5, 2, 1]

 

1.       4 과 3 을 비교합니다. 오름차순으로 정렬하는 경우,   4 < 3 이 아니므로 두 element 를 교환합니다.

[4, 3, 5, 2, 1]
// 1.       4 과 3 을 비교합니다. 오름차순으로 정렬하는 경우,   4 < 3 이 아니므로 두 element 를 교환합니다.
[3, 4, 5, 2, 1]
// 2.       4 과 5 을 비교합니다.  4 < 5 이므로 교환하지 않습니다.
// 3.       5 와 2 를 비교합니다. 5 < 2 가 아니므로 교환합니다.
[3, 4, 2, 5, 1]
// 4.       5 와 1 를 비교합니다. 5 < 1 가 아니므로 교환합니다.
[3, 4, 2, 1, 5]

처음부터 끝까지 한번씩 비교 및 교환과정을 마쳤고, 그 결과 행렬의 마지막 element 가 배열 중 가장 큰 값으로 정해졌습니다.

 

 

 

그럼 다시 처음부터 같은 과정을 반복하겠습니다. 마지막 element 는 가장 큰 값으로 정해졌으니 단계가 한번은 줄어들겠죠 ?? 

[3, 4, 2, 1, 5]
// 1.       3 과 4 를 비교합니다. 3 < 4 이므로 넘어갑니다.
// 2.       4 와 2 를 비교합니다. 4 < 2 가 아니므로 교환합니다.
[3, 2, 4, 1, 5]
// 3.       4 와 1 을 비교합니다. 4 < 1 이 아니므로 교환합니다.
[3, 2, 1, 4, 5]

이제 4와 5 가 바르게 정렬되었습니다. 

 

이와 같은 과정을 끝날때까지 해주면 (array.count - 1 번 만큼 반복) Bubble sort 가 완료됩니다. 

 

 

 

행렬에 n 개의 element 가 있을 때, 정렬은 총 (n - 1 ) + (n - 2) + ... (2) + (1) 번 하게되고, 총 n(n-1) / 2 번의 연산을 하게 됩니다.

따라서 Buble Sort 는  O(n ^ 2 ) 을 갖습니다.

 

모든 단계 설명 및 Swift 로 구현한 코드는 아래 링크에 있습니다 (같은 블로그내 다른 글이에요 )

2021.10.08 - [Swift/DataStructure + Algorithm] - Bubble Sort With Swift

Bubble Sort With Swift

 

For 문을 이용한 bubble sort

func bubbleWithFor(arr: [Int]) -> [Int] {
    var newArr = arr
    var numOfRepeat = 0
    for _ in 0 ..< newArr.count - 1 {
        for j in 0 ..< newArr.count - numOfRepeat - 1{
            if (newArr[j] > newArr[j + 1]) {
                newArr.swapAt(j, j+1)
            }
        }
        numOfRepeat += 1
    }
    return newArr
}

Recursion 을 이용한 bubble sort (recommended..)

func bubbleWithRecursion(array: [Int], numOfRep: Int = 0, _ isCompleted: Bool = false) -> [Int] {
    
    if isCompleted { // when sorting is done
        return array 
    }
    
    var isDone = true // turn into false if sorting is not done
    var arr = array

    for i in 0 ..< arr.count - 1 - numOfRep {
        if (arr[i] > arr[i+1]) {
            arr.swapAt(i, i+1)
            isDone = false // when change occur is not done yet !
        }
    }
    
    return bubbleWithRecursion(array: arr, numOfRep: numOfRep + 1, isDone)
}

 

2. Selection Sort

Selection Sort 는, 배열 차례대로 하나하나 비교해가며 가장 작은 값을 찾은 후,  가장 낮은 인덱스에 있는 수와 바꾸는 방식을 반복하여 정렬을 진행합니다. 아래는 정렬할 array 의 예시입니다. 

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

 먼저 8 ( 0번째 index ) 을 기준으로 한 후 5와 비교합니다. 새로 비교할 수가 기준보다 작으므로 5 를 기준으로 삼습니다. 

5를 기준으로 2 와 비교합니다. 비교하는 수 2 가 기준보다 작으므로 2를 기준으로 삼습니다.

2 와 6 을 비교합니다. 기준이 더 작으므로 다음 수로 넘어갑니다.

2 와 9 를 비교합니다. 기준이 더 작으므로 다음 수로 넘어갑니다.

2 와 3 을 비교합니다. 기준이 더 작으므로 다음 수로 넘어갑니다.

2 와 1 을 비교합니다.  비교하는 수 1 이 기준보다 작으므로 1 을 기준으로 삼습니다.

1 와 4 을 비교합니다. 기준이 더 작으므로 다음 수로 넘어갑니다.

1 과 0 을 비교합니다. 비교하는 수 0 이 기준보다 작으므로 0 을 기준으로 삼습니다.

0 과 7 을 비교합니다. 기준이 더 작으므로 다음 수로 넘어갑니다.

끝까지 비교한 결과, 0 이 가장 작은 수가 되었습니다. 이제 0번째 index 에 있는 수와 0 을 교환합니다.

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

0 은 이제 정해졌으므로, 5 를 ( 1 번째 index ) 기준으로 다시 가장 작은 수를 차례대로 끝까지 찾아나갑니다.

찾은 후에는 그 수와 1번째 인덱스를 바꿔줍니다.

 

해당 과정을 모든 정렬이 끝날 때까지 해주면 됩니다.

Selection sort 도 Bubble Sort 와 같이 총 (n)(n-1) / 2 번의 과정이 필요함을 알 수 있습니다. 

따라서 Buble Sort 와 마찬가지로O (n ^ 2 )을 갖습니다.

 

배열을 SelectionSort 를 이용해서 정렬하는 과정을 상세히 서술, 그리고 Swift Code로 구현, 설명한 글입니다.

2021.10.08 - [Swift/DataStructure + Algorithm] - SelectionSort

SelectionSort

 

SelectionSort

func selectionSortWithFor(array: [Int]) -> [Int] {
    var pivotIndex = 0
    var arr = array

    for i in 0 ..< arr.count - 1 {
        pivotIndex = i
        for j in i ..< arr.count - 1 {
            if (arr[pivotIndex] > arr[j+1]) {
                pivotIndex = j
            }
        }
        arr.swapAt(i, pivotIndex)
    }
    return arr
}

 

 

Insertion Sort

 

Insertion Sort 는, sorting 하고자 하는 array 가 대부분 정렬 되어있다고 했을 때 특히 더 빠른 sorting method 에요.

 

SelectionSort 에서 사용한 array 를 약간 변형시켜 사용해보도록 할게요. 

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

 

먼저 0 을 하나의 행렬 처럼 생각합니다. [0]

우측에 있는 2 를 이 행렬에 정렬해서 넣는다면 0 의 뒤에 들어가겠네요.  [0, 2]

그리고 다시 우측에 있는 5 를 새로운 행렬에 정렬하여 넣습니다. [0, 2, 5]

같은 방법을 6에 대해 반복합니다. [0, 2, 5, 6]

같은 방법을 9에 대해 반복합니다. [0, 2, 5, 6, 9]

이제, 우측에 있는 1 을 새로운 행렬의 적당한 곳 ( 0 과 2 사이) 에 넣습니다. [0, 1, 2, 5, 6, 9]

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

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

다시, 우측에 있는 3을 적당한 곳에 넣습니다. (2 와 5 사이 ) 

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

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

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

위 과정을 처음부터 끝까지 반복한 결과를 써보겠습니다.  

 

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

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

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

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

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

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

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

 

[0]

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

 

[0, 2]

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

 

[0, 2, 5]

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

 

[0, 2, 5, 6]

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

 

[0, 2, 5, 6, 9]

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

 

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

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

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

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

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

 

InsertionSort 는 BubbleSort, Selection Sort 와는 약간 다른 형태를 띠네요. 처음 Insertion Sort 를 소개할 때,

"Insertion Sort 는, sorting 하고자 하는 array 가 대부분 정렬 되어있다고 했을 때 특히 더 빠른 sorting method 에요." 

라고 말씀드렸습니다. 실제로 대부분이 이미 정렬되어있는 경우 Insertion Sort 는 O ( n ) 까지 줄어들 수 있습니다. (보통의 경우 O(n^2))

 

Insertion Sort 을 Swift 로 구현한 코드 및 설명은 아래에 있습니다. 

 

2021.10.09 - [Swift/DataStructure + Algorithm] - Insertion Sort with Swift

 

 

 

 

func insertionSort(arr: [Int]) -> [Int] {
    if arr.count == 0 { return arr }
    
    var box : [Int] = [arr[0]]
    var toBeCompared : Int
    
    for i in 1 ..< arr.count {
        toBeCompared = arr[i]
        
        boxLoop: for boxIndex in 0 ..< box.count {
            
            if box[box.count - 1 - boxIndex] < toBeCompared {
                box.insert(toBeCompared, at: box.count - 1 - boxIndex + 1)
                break boxLoop
            }
            
            if boxIndex == box.count - 1 {
                box.insert(toBeCompared, at: 0)
            }
        }
    }
    
    return box
}

 

Merge Sort & Quick Sort

MergeSort, QuickSort 는 O(n log n) 의 Time Complexity 를 갖는 Sorting Algorithm 입니다. 위 세가지 sorting algorithms 이 평균적으로 O(n^2) 을 가졌던 것에 비하면 아주 괜찮은 Algorithm 이라고 볼 수 있어요.

 

Merge Sort, Quick Sort 에서는 'Divide & Conquer' 이라는 concept' 으로 진행됩니다. 쉽게 말하면, 나눈 후 처리한다는 것이죠.

먼저, Merge Sort 에 대하여 알아보겠습니다 

 

4. Merge Sort

간단히 말하면.. 나눈 후 Merge 하면서 Sort 하는 Algorithm 입니다....(죄송합니다 우선 조금 더 읽어주세요ㅠ) 

 

예를 들어 10개의 elements 가 있는 경우, 해당 array 를 sorting 하려면 위에서 썼던 방법들을 사용했을 때 O(n^2), 약 100 번의 과정이 소요된다고 가정해볼게요.

 

만약 array 를 반으로 나눈 후 sorting, 합칠때 다시 sorting 해주면 과정이 많이 줄어들 수 있습니다. 위와 같은 방식으로 한다면 5^2 이 두번, 그리고 합치는 경우에는 모든 element 들을 한번씩 비교하고 배치해야하니 10번 으로 잡으면 (25 + 25 + 10 ) 60번 이네요. 

 

이러한 방식으로 큰 덩어리를 작게 나누고, 나뉘어진 것들을 sorting 한 후 합치면서 정렬하는 방법을 Merge Sort 라고 합니다. 

 

 

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

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

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

1. 이 elements 반으로 나눕니다. 나눈 후 정렬하면 더 빠르게 할 수 있으니까요.

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

2. 더더 빠르게 하기 위해서 또다시 나눕니다.

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

3. 더더더 빠르게 하기 위해서 다시 한번 나눕니다.

 

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

4. 이제 나눌수가 없습니다. 지금부터 합치면서 정렬을 시작하겠습니다.

 

5. 각 상자에 있는 element 를 앞에서부터 2개씩, 보고 비교해서 작은 값을 앞에, 큰 값을 뒤에 둡니다. (2개 들어있는 상자 4 생성 )

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

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

6. 2개의 상자들 (2개의 elements 가 들어있는) 에서 각각의 element 들을 비교 후, 4 * 1 상자에 넣습니다. (4개 들어있는 상자 2 생성)

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

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

7. 위 과정을 반복합니다. (8 * 1 의 상자가 생겼고, 정렬이 완료되었습니다.) 

 

 

 

 

 

5, 6, 7 과정을 사실 똑같아요. 과정이 많이 축약되어 있는 것 같아 과정에 대해 추가로 설명드리겠습니다.

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

 [5,6] ~ [1, 3] 비교
1.   5 와 1 비교 ->  1 이 더 작으므로 1을 우선 배치  [1]
2.   5 와 3 비교 ->  3 이 더 작으므로 3을 그 후에 배치 [1, 3]
3.   5, 6 비교할 대상 없으므로 그 뒤에 배치 [1, 3, 5, 6]

[7,8], [2,4] 비교
1.   7 와 2 비교 ->  2 이 더 작으므로 2을 우선 배치  [2]
2.   7 와 4 비교 ->  4 이 더 작으므로 4을 그 후에 배치 [2, 4]
3.   7, 8 비교할 대상 없으므로 그 뒤에 배치 [2, 4, 7, 8]

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

Merge Sort 를 Swift 로 구현한 Code 및 설명은 아래에 있습니다.

2021.10.20 - [Swift/DataStructure + Algorithm] - MergeSort (with Swift)

 

mergeSort Code

 

func mergeSort1(_ array:[Int]) -> [Int]{

    if array.count > 1 {   // if array has more than 1 element, divide it.
        var firstHalfArray = [Int]()  // initiate empty Int array
        var lastHalfArray = [Int]()
        
        let half = array.count / 2

        for i in 0 ..< array.count {
            if i < half { // first half of array is going to be 'firstHalfArray'
                firstHalfArray.append(array[i])
            } else {      // last half of array
                lastHalfArray.append(array[i])
            }
        }
        return merge(mergeSort1(firstHalfArray), mergeSort1(lastHalfArray))
    } // if it has a only element, return self 
    return array
}



func merge(_ array1: [Int], _ array2: [Int]) -> [Int] { // merge only sorted!! array

    var resultArray = [Int]()
    var array1Index = 0
    var array2Index = 0

    while (array1.count > array1Index || array2.count > array2Index) {
    
        // validity check for both array1 and array2
        
        // if one of arrayIndexes is equal to the number of array it's using for,
        //  append the other array to the end of resultArray. then, return!
        
        if array1Index == array1.count {
            // need to merge remained arrays , not the whole part.
            for index2 in array2Index ..< array2.count {
                resultArray.append(array2[index2])
            }
            break
        }
        
        if array2Index == array2.count {
            for index1 in array1Index ..< array1.count {
                resultArray.append(array1[index1])
            }
            break
        }
        
        // compare elements one by one. If one(a) is smaller than or equal to the other(b), 
        //put first one(a) at the end of resultArray, and add 1 to the index of that array

	if array1[array1Index] <= array2[array2Index] {
            resultArray.append(array1[array1Index])
            array1Index += 1
        } else {
            resultArray.append(array2[array2Index])
            array2Index += 1
        }
    }

    return resultArray
}

 

 

 

5. 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 가 더 적당할 것입니다. 

 

 

QuickSort 를 Swift 로 구현한 코드 및 설명은 아래에 있습니다. 

2021.10.21 - [Swift/DataStructure + Algorithm] - Quick Sort with Swift

 

quickSort Code

 

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])

 

 

 

Summary

지금까지 Bubble, Selection, Insertion, Merge, Quick Sort 에 대해 알아보았습니다.

 

아래는 각 Algorithms 에 대한 Time Complexity, Space Complexity 에 대한 표입니다.

( Ω, Θ 은 우선 O 로 생각해주셔도 될 것 같아요)

Algorithm	Time Complexity			Space Complexity
	Best	Average	Worst	Worst
Bubble Sort	Ω(n)	Θ(n^2)	O(n^2)	O(1)
Selection Sort	Ω(n^2)	Θ(n^2)	O(n^2)	O(1)
Insertion Sort	Ω(n)	Θ(n^2)	O(n^2)	O(1)
Merge Sort	Ω(n log(n))	Θ(n log(n))	O(n log(n))	O(n)
Quick Sort	Ω(n log(n))	Θ(n log(n))	O(n^2)	O(log(n))

 

마지막으로 정리를 하자면,

1. Bubble, Selection, Insertion Sort 는 모두 Best 가 아닌 경우 O (n^2) 을 갖습니다. 

2. Bubble Sort, Insertion Sort 는 모두 이미 정렬이 완료된 상태에서 O(n) 을 갖습니다.

3. Merge, Quick Sort 는 어떠한 경우에서도 나머지 세개의 Algorithm 보다 Time Complexity 면에서 우세합니다. ((4) 경우 제외)

4. Quick Sort 는 Pivot point 가 가장 높거나 낮은 값으로 계속 잡히는 경우 (Worst) O(n^2) 을 갖습니다. 

5. 정렬이 되어있는지 아닌지 모르는 경우라면 Merge Sort 가 Quick 보다 Time Complexity 면에서 나을 것입니다. 

 

* array size or datasets 가 큰 경우 Merge sort 가 Quick sort 보다 효율적이고 빠르며, 

그 외의 경우 Quick sort 가 선호됩니다. ( 첫번째 출처에서 가져왔습니다 )

 

출처

https://www.geeksforgeeks.org/quick-sort-vs-merge-sort/ 

https://www.bigocheatsheet.com/