정렬

종류

종류	시간 복잡도
버블 정렬 (Bubble Sort)	O(n^2)
선택 정렬 (Selection Sort)	O(n^2)
퀵 정렬 (Quick Sort)	O(nlogn)
삽입 정렬 (Insert Sort)	O(n^2)
병합 정렬 (Merge Sort)	O(nlogn)

 

버블 정렬 (Bubble Sort)

개념

맨 앞에 있는 수부터 기준으로 잡는다. 기준으로 잡은 수를 다음에 있는 수와 비교했을 때, 더 크다면 자리를 서로 바꾸고 계속 다음 수와 비교하면서 정렬하는 방법이다. 뒤에서부터 가장 큰 수가 채워진다.

시간 복잡도

최악의 경우 n-1개의 정점을 기준으로 삼으면서 비교하고, 모두 자리 교환을 해야 하므로 O(n^2)이다.

O((n-1) * (n-1)!) = O(n^2-2n+1) = O(n^2)

코드

def bubble_sort(a):
    for i in range(len(a)-1):
        for j in range(1,len(a)-i):
            if a[j-1] > a[j]:
                a[j-1], a[j] = a[j], a[j-1]
            else:
                break
    return a

 

선택 정렬 (Selection Sort)

개념

맨 앞자리에 최솟값을 넣고, 그 다음엔 두번째로 작은 값을 넣으면서 앞자리부터 순차적으로 정렬하는 방법이다. 0부터 n-1까지 순차적으로 자리를 채워나가야 한다. 채워야하는 인덱스를 최초의 최솟값 변수에 넣고 그 이후에 오는 수 중에서 최솟값이 존재하면 그 두 수의 자리를 바꾼다.

시간 복잡도

최악의 경우 O((n-1)*(n-1)!)으로 버블 정렬과 같은 O(n^2)이다.

코드

def selection_sort(a):
    for i in range(len(a)-1):
        for j in range(i+1,len(a)):
            if a[j] < a[i]:
                a[i], a[j] = a[j], a[i]
    return a

 

퀵 정렬(Quick Sort)

개념

피벗을 정한 후에 피벗의 위치를 확정해가며 정렬하는 알고리즘

특징

분할-정복-결합의 단계로 이루어짐

문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략

다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속함

같은 값이 있는 경우 정렬 이후 순서가 초기와 달라질 수 있어 불안정 정렬에 속함

 

시간 복잡도

최악의 경우: O(n^2)

이미 정렬된 배열을 맨 왼쪽이나 오른쪽에 피벗을 두고 퀵정렬한다면 피벗이 반대쪽까지 이동할때까지 재귀를 호출하므로 깊이도 깊어질뿐더러 속도도 오래걸림

 

평균: O(nlogn)

 

매 단계에서 적어도 1개의 원소가 자리를 찾게 되므로 이후 정렬할 개수가 줄어든다. 따라서, 퀵 정렬은 다른 O(nlogn) 알고리즘에 비해 훨씬 빠르게 동작한다. O(logn)만큼의 memory를 필요로 한다.

 

Quick Sort

원리

배열의 맨 오른쪽을 피벗으로 설정한다. (정복)

피벗보다 작은 수는 맨 왼쪽으로 몰아 넣는다. (정복)

왼쪽에 있는 집합은 정렬이 되지 않았으나 피벗보다는 작은 수들의 집합이다.(정복)

피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 각각 정복한다. (분할)

부분 리스트들이 더 이상 분할될 수 없을 때까지 반복한다. (분할)

다시 돌아와서 피벗의 오른쪽 집합을 정렬한다. (결합 - 분할)

정복 - 분할 - 결합의 과정이 반복되어 정렬된다.

 

구현 방법

1. 배열의 맨 오른쪽부터 피벗으로 설정

2. 피벗보다 작은 수의 집합에서 가장 마지막 원소를 가리키는 i를 설정

3. [0]~[피벗-1]까지 탐색하면서 피벗보다 작은 수를 찾음

   1. 피벗보다 작은수를 찾았다면 그 원소와 집합의 마지막 원소 바로 다음 수인 [i+1]을 swap 한다.

      1. [i+1]은 피벗보다 큰 수이므로 swap해줘서 i까지는 피벗보다 작은 수의 집합으로 만든다.

4. 탐색이 모두 완료 됐다면 피벗의 위치와 [i+1]을 swap

5. pivot이 될 i+1을 반환

 

 

장단점

장점	단점
속도가 빠르다	정렬된 리스트에 대해서는 퀵 정렬의 불균형 분할에 의해 오히려 수행시간이 더 많이 걸린다.
추가 메모리 공간을 필요로 하지 않는다.

 

코드

def partition(arr,start,end):
    p = arr[end]
    i = start - 1 # pivot보다 작은 원소들의 마지막 위치

    for j in range(start,end):
        if arr[j] < p:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i+1], arr[end] = arr[end], arr[i+1]
    return i + 1


def quick_sort(arr, l, r):
    if l < r:
        pivot = partition(arr,l,r)
        quick_sort(arr,l,pivot-1)
        quick_sort(arr,pivot+1,r)


a = [20, 70, 60, 30, 100, 40]
quick_sort(a,0,len(a)-1)
print(a)