시간복잡도에 따른 정렬의 종류

$O(n^2)$(평균)

• 버블정렬 (단순 교환 정렬)
  • 이웃한 두 원소의 대소관계를 비교하여 필요에 따라 교환을 반복
  • $T(n) = O(n^2)$
  • 최대 $n(n-1)/2$번 정렬
  • 가장 성능이 안좋은 정렬
  • 셰이커 정렬
    • 버블정렬을 개선한 정렬
    • 홀수 반복 : 가장 작은수를 앞으로, 짝수 반복 : 가장 큰 수를 뒤로
    • 전체 반복(while) 구간에서 for문이 두개가 들어있음(이중x)
• 선택 정렬 (Selection sort)
  • 모든 수를 훑어서 가장 작은(또는 큰) 것을 1번째, 2번째… (n-1)번 반복한다
  • 최대 $n(n-1)/2$에 비례하는 시간 소요 $O(n^2)$
• 삽입 정렬 (Insertion sort)
  • k번째 원소를 1부터 k-1 까지와 비교해 적절한 위치에 넣고, 그 뒤의 자료를 한 칸씩 뒤로 밀어내는 방식
  • 평균적으로 3 종류 중 빠른편이나, 구조에 따라 밀어내는데 걸리는 시간이 큼
  • 배열이 작을 경우 가장 효율적

$O(n log n)$(평균)

• 병합 / 합병 정렬 (Merge sort)
  • 원소 개수가 1 또는 0이 될 때 까지 두 부분으로 쪼개고, 자른 순서의 역순으로 크기를 비교, 병합한다
  • 병합된 부분은 이미 정렬되어 전부 비교하지 않고 제자리를 찾는다
  • 장점 : 데이터의 상태에 영향을 받지 않음
  • 단점 : 퀵 정렬보다 성능이 뒤떨어짐, 데이터만큼의 메모리가 더 필요함

• 힙 정렬 (Heap sort)
  • 힙
  • import heapq heapq.heappush(heap,data) # 힙에 새로운 데이터를 삽입 heappop(heap) #루트노드(최상위값)을 꺼낸 후 삭제 heapify(x) # wndjwls qodufdmf glq rnwhfh qusghks
  • 힙의 특성을 활용한 정렬
    • 부모의 값이 자식의 값보다 항상 크다
    • 자식노드가 부모노드의 위치로 가기 위한 공식 = $(idx-1)//2$
    • 부모노드 → 자식노드 $2idx + 1$(left) $2idx +2$(right)
• 퀵 정렬 (Quick sort)
  • 불안정 정렬 에 속하며, 비교만으로 정렬을 수행하는 비교정렬에 속함
  • 평균적으로 가장 빠른 알고리즘 (최악의 경우 O(n^2)의 시간복잡도를 보임)
  • 분할 정복 알고리즘(divide and conquer)의 하나
    • 문제를 작은 2개의 문제로 분리하고 각각 해결 후, 결과를 모아 원래의 문제를 해결
    • 대게 순환 호출을 이용하여 구현
  • 과정
    1. 피벗(pivot) 선택
       1. 배열에서 하나의 요소를 선택, 이는 배열을 두개의 부분으로 나누는 기준이 됨
    2. 분할 (Partition)
       1. 피벗을 기준으로 배열을 두 부분으로 나눔 (보통 중앙)
          • 왼쪽 : 피벗보다 작은 요소들
          • 오른쪽 : 피벗보다 큰 요소들
    3. 재귀적 정렬
       1. 피벗을 제외한 왼쪽, 오른쪽 부분 각각에 대해 퀵 정렬을 재귀적으로 적용

       #예시
       def partition_center(arr):
        if len(arr) <= 1:
            return arr
       
        # 중앙 인덱스의 요소를 피벗으로 선택
        pivot = arr[len(arr) // 2]
        left = []
        equal = []
        right = []
       
        for x in arr:
            if x < pivot:
                left.append(x)
            elif x > pivot:
                right.append(x)
            else:
                equal.append(x)
       
        # 재귀적으로 분할 정복: 각 부분도 동일한 방식으로 정렬 후 병합
        return partition_center(left) + equal + partition_center(right)
       
       # 먼저 피벗을 기준으로 left, equal, right 리스트를 구성한 후
       # return partition_center(left) + equal + partition_center(right)
       # 재귀 호출을 통해 왼쪽과 오른쪽 리스트 각각에 대해 동일한 정렬 과정을 반복

  • (참고) 다른 분할 방식
    1. Lomuto Partition Scheme
       1. 배열의 마지막 원소를 피벗으로 선택
       2. index $i$를 시작 부분으로 초기화하고, index $j$를 처음부터 피벗 바로 전 까지 순회
       3. $a[j]$ 가 피벗보다 작거나 같으면 $a[i]$와 $a[j]$를 교환하고 $i$를 증가
       4. 순회가 끝난 후, $a[i]$와 피벗을 교환
    2. Hoare Partition Scheme
       1. 배열의 첫 번째 원소를 피벗으로 선택
       2. 두 개의 포인터 $i$와 $j$를 배열의 양 끝에서 시작
       3. $i$는 오른쪽으로 이동하며 피벗보다 큰 원소를 찾고, $j$는 왼쪽으로 이동하면서 피벗보다 작은원소를 찾음
       4. 두 포인터가 만날 때 까지, 찾은 두 원소를 교환