정렬 알고리즘

Selection Sort : 현재 배열중에 가장 작은 원소를 고른다. 

3 5 1 8 2 9 

가장 작은 원소와 현재 인덱스의 원소의 자리를 바꾼다. 

1 5 3 8 2 9 

가장 작은 원소는 이미 정렬된 것이므로, 그 다음원소부터 n-1번까지 확인하여 가장 작은 원소를 고른다. 

1  5 3 8 2 9        --------- 1을 제외하면 2가 가장 작은 원소이다. 

1 2 3 8 5 9          --------- 1, 2 까지는 정렬된 것이다. 

1 2 3 8 5 9         --------- 1, 2, 3 까지는 정렬되었다. 이 경우 3은 자리를 바꾸지 않아도 된다. 

1 2 3 5 8 9         --------- 5 8 9 중에 가장 작은 수는 5이므로 8과 5의 위치를 바꿨다. 

1 2 3 5 8 9       ---------- 9 를 제외한 나머지 모든 원소들이 정렬되어 있으므로 9 는 자연스럽게 정렬이 된다. 

def selection_sort(a):
    for i in range(len(a)-1): # 맨 마지막 원소는 자연스럽게 정렬이 되므로 n-1
        min_idx = i
        for j in range(i+1, len(a)):
            if a[j] < a[min_idx]:
                min_idx = j
        a[i], a[min_idx] = a[min_idx], a[i]

array = [4,2,8,1,9]

selection_sort(array)
print(array)

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

Bubble Sort

Quick Sort : pivot 값을 기준으로 pivot 보다 작은 값과 더 큰 값으로 반복적으로 분할하여 정렬해 나간다. 

시간 복잡도는 평균적으로 O(nlogn)

그러나 최악의 경우에는 O(n^2) -> 데이터들이 이미 정렬되어 있는 경우이다. 

Insertion Sort

Shell Sort

Heap Sort

Merge Sort : 전체 배열을 반으로 나눈다. 반으로 나눈것을 또 recursive하게 반으로 나눠서 배열의 길이가 1일때까지 나눈다. 

그후 axilary space에 좌 우로 나눈 배열의 원소를 하나씩 비교하면서 정렬한다. 

마지막으로 정렬된 부분 배열들을 merge 한다!! 

 

Radix Sort

 

Merge Sort vs Quick Sort 

Merge Sort needs axilary space while Quick Sort do not becuse the elements in the array were already sorted !