Sort Algorithm

Sort Algorithm

주어진 값들을 정렬하는 알고리즘

버블 Bubble

시간복잡도 O(n) ~ O(n^2)
공간복잡도 O(1)

 

가까운 두개 값을 비교하는걸 반복

for i in 0..<N
    for j in 1...N-i
        compare [j-1] and [j]

// 0,1 1,2 2,3 .. n-2,n-1 n-1,n
// 0,1 1,2 2,3 .. n-2,n-1
// ...
// 0,1

선택 Selection

시간복잡도 O(n^2)

공간복잡도 O(1)

 

최대값을 찾아 마지막에 넣고 반복

for i in 0..<N
    max(array[0..<N-i])
    switch (max, (N-i)-1)

삽입 Insertion

시간복잡도 O(n) ~ O(n^2)

공간복잡도 O(1)

 

정렬된 앞쪽 맞는자리에 삽입

for i in 0..<N
    insert i in array[0...i]

쉘 Shell

시간복잡도 O(n log n) ~ O(n (log n)^2)

공간복잡도 O(1)

 

갭을 두어 파트별로 삽입정렬 -> 갭을 바꾸어 정렬 -> 반복

for i in 4 to 1
    [array(0, i, 2i, 3i ...),
     array(0+1, i+1, 2i+1, ...),
     ...
     array(i-1, 2i-1, 3i-1, ...)].forEach
         Insertion sort

퀵 Quick

시간복잡도 O(n log n) ~ O(n^2)

공간복잡도 O(log n)

 

한 값을 기준으로 하여 크기차이를 가지고 왼쪽 오른쪽으로 나눈다.
기준이 되었던 값은 고정하고 나머지 왼쪽 오른쪽도 한 값을 기준으로 정렬을 반복한다.

quick (start, end)
    if end == start then return

    pivot = start + (end-start)/2
    array split by pivot

    if end - start <= 2 then return

    quick(start, pivot-1), quick(pivot+1, end)

병합 Merge

시간복잡도 O(n log n)

공간복잡도 O(n)

 

쪼개고 쪼개서 작은부분부터 합치며 정렬

array.split
splited.forEach
    sort

while splited.count != 1
    for i in 0...splited/2
        merge(splited[i], splited[i+1]) sort

힙 Heap

시간복잡도 O(n log n)

공간복잡도 O(1)

 

최대값 또는 최소값이 최상단에 오는 힙 구조를 만들어 하나씩 뺴며 정렬

array.heapify

for i in 0..<array.count
    heapified.pop()
    heapified.heapify