[자료구조]정렬 알고리즘 비교 정리

1. O(n²) 정렬

1.1 선택 정렬

• 원소를 넣을 위치는 정해져있고, 어떤 원소를 넣을지 선택
• 1번째 인덱스부터 배열을 탐색하여 1번째로 작은 값을 1번째에 위치 → 2번째 인덱스부터 탐색 & 2번째에 위치 → 3번째부터 탐색 & 3번째에 위치 → … → 총 (n-1)번 반복
• 추가 공간 없이 주어진 배열에서 위치만 변경한다. O(1)의 공간 복잡도
• 시간 복잡도
  • 1번째 루프에서 비교 : n-1
  • 2번째 루프에서 비교 : n-2
  • (n-1)+(n-2)+…+1 = n(n-1)/2
  • 최선, 최악, 평군 모두 O(n²)

def selection_sort(L):
    for i in range(N):  #해당 위치 i에 들어갈 원소를 선택
        minVal_idx = i      
        for j in range(i+1,N):
            if L[j] < L[minVal_idx] :
                minVal_idx = j
        
        L[i], L[minVal_idx] = L[minVal_idx], L[i]

1.2 삽입 정렬

• 원소는 정해져있고, 원소를 넣을 위치를 찾고 삽입하면 된다.
• k번째 원소를 그 앞의 원소들을 차례대로 비교해 적절한 위치에 삽입 후 뒤의 배열을 한 칸씩 뒤로 밀어내기. (k=2번째 원소부터 n번째 원소까지)
• 삽입하고 한 번에 밀어내는 대신에 차례대로 비교하며 왼쪽에 위치한 값이 오른쪽에 위치한 값보다 크다면 왼쪽의 값을 오른쪽에 저장한다. (밀어내는 효과)
  • 비교하다 왼쪽 값이 더 작은 경우에 k번째 원소를 넣어준다.
• 추가 공간 없이 주어진 배열에서 위치만 변경한다. O(1)의 공간 복잡도
• 시간 복잡도
  • 최선의 경우 O(n)
  • 최악, 평균의 경우 O(n²)

#왼쪽에서 나보다 큰거는 뒤로 밀어, (앞에는 정렬 완료)

def insertion_sort(L):
    for i in range(1,N):
        val = L[i]
        leftVal_idx = i-1

        while leftVal_idx >=0 and L[leftVal_idx] > val :
            L[leftVal_idx+1] = L[leftVal_idx] 
            leftVal_idx-=1
        
        L[leftVal_idx+1] = val

1.3 거품 정렬

• 1번째 원소와 2번째 원소를 비교, 2번째 원소와 3번째 원소를 비교, … , n-1번쨰 원소와 n번째 원소를 비교 → 1번째 원소와 2번째 원소를 비교, … , n-2번째 원소와 n-1번째 원소를 비교 → …
• 루프 1회당 마지막 1개의 원소가 정렬된다.
  • 1번째 루프에서 가장 큰 원소가 맨 뒤에 위치하게 된다.
  • 2번째 루프에서 2번째로 큰 원소가 뒤에서 2번째에 위치하게 된다.
• 스왑되는 횟수를 체크해 한 번도 스왑되지 않는 경우가 발생하면 정렬을 멈추면 된다.
• 스왑되는 마지막 인덱스를 저장해 해당 위치까지만 스왑하면 추가적인 최적화 가능하다. (저장된 인덱스 이후로는 완전히 정렬되었다는 의미)
• 추가 공간 없이 주어진 배열에서 위치만 변경한다. O(1)의 공간 복잡도
• 시간 복잡도
  • 최선의 경우 O(n)
  • 최악, 평균의 경우 O(n²)

#제일 큰 거 뒤로 밀어, 다시 처음으로 가서 두번째로 큰거 뒤로 밀어, (뒤에는 정렬 완료)

def bubble_sort(L):
    end = N-1
    
    while end>0:
        # isSwapped=False
        lastSwapped=0
        for i in range(end):
            if L[i] > L[i+1]:
                L[i], L[i+1] = L[i+1], L[i]
                lastSwapped = i    
        # if not isSwapped : break
        end = lastSwapped

2. O(n log n) 정렬

2.1 퀵 정렬

• 평균적인 상황에서 최고의 성능
• 배열에서 하나의 원소(pivot)을 고른다.
• 피벗 앞에는 피벗보다 작은 원소들이 오고 뒤에는 큰 원소들이 오도록 피벗을 기준으로 배열을 분할한다.
• 분할된 두 배열에 대하여 재귀적으로 반복한다.
• 공간 복잡도 - O(log n) - 제자리 정렬, 재귀로 인한 스택 메모리
• 시간 복잡도 - pivot을 선택하는 방법에 따라 달라진다.
  • 평균, 최선의 경우 O(n log n) - pivot을 기준으로 같은 개수의 값들이 분할
  • 최악의 경우 - O(n²) 값들이 한 쪽으로 치우치게 되는 경우

def quick_sort(L,s,e):
    if s >= e :
        return
    
    pivot = s
    l,r = s+1, e
    
    while l<=r :
        #pivot 보다 큰 값을 왼쪽에서부터 찾는다.
        while l<=e and L[l] <= L[pivot] :
            l+=1
            
        #pivot 보다 작은 값을 오른쪽에서부터 찾는다.
        while r>=s+1 and L[r] >= L[pivot] :
            r-=1

        #l,r 이 엇갈린 경우 피벗 이동, l위치에 pivot
        if l>r :
            L[r] , L[pivot] = L[pivot], L[r] 
        else:
            L[l] , L[r] = L[r], L[l]
            
    quick_sort(L, s, r-1)
    quick_sort(L, r+1, e)

2.2 병합 정렬 (Merge Sort)

• 요소를 쪼갠 후 다시 병합하며 정렬
• 합치는 배열의 원소 2개 이상이면 최솟값부터 차례대로 하나씩 비교한다.
• 공간 복잡도 - O(n) -> 새로운 배열 필요
• 시간 복잡도
  • 평균, 최선,최악 모두 O(n log n)

def merge_sort(L):
    def sort(l, r):
        if r-l<2 :
            return
        m = (l+r)//2
        sort(l,m)
        sort(m+1,r)
        merge(l,m,r)
            
    def merge(left,mid,right):
        tmp = []
        l, r = left, mid
        
        while l < mid and r < right :
            if L[l] < L[r]:
                tmp.append(L[l])
                l+=1
                
            else:
                tmp.append(L[r])
                r+=1
                
        #l, r 배열 중 아직 병합 안된 것들 처리
        while l < mid :
            tmp.append(L[l])
            l+=1
        while r < right:
            tmp.append(L[r])
            r+=1
            
        for i in range(left, right):
            L[i] = tmp[i-left]

    return sort(0, len(L))

2.3 힙 정렬

• 최대 힙 구성
• 루트의 값을 제거하고(출력) 마지막 요소를 루트에 넣는 것을 반복
• 공간 복잡도 - O(n)
• 시간 복잡도
  • 최선의 경우 O(n)
  • 평균, 최악의 경우 O(n log n)

3. 하이브리드 정렬

3.1 팀 정렬

• 실제 데이터가 무작위가 아닌 어느 정도 지역 참조성을 따른다는 가정에서의 알고리즘
• python 내장 함수 sort()의 방법
• 병합 정렬 + 삽입 정렬
  • 작은 n에 대하여 삽입 정렬이 매우 빠르다.
  • 작은 덩어리로 자르고 삽입 정렬을 한 뒤 병합하자는 아이디어
  • 2^x 형태의 덩어리 삽입 정렬 이용해서 만들기(min run) → 뒤에도 정렬된 것이 있다면 더 큰 덩어리로 합치기(run)
  • run을 스택에 넣으며 병합한다. 스택에 들어간 run의 크기가 피보나치 형태가 되도록 반복해서 병합한다.
• 삽입 정렬을 할 때, 하나 씩 탐색하는 것이 아니라 이분 탐색 이용
• 공간 복잡도 - 병합 정렬에 비해 적은 추가 메모리
• 시간 복잡도
  • 최선의 경우 O(n)
  • 평균, 최악의 경우 O(n log n)