정렬 알고리즘

선택 정렬 (Selection Sort)

- 크기가 가장 작은 데이터를 맨 앞 순서의 원소와 서로 교체하고 그 다음으로 작은 데이터를 두 번째 순서의 원소와 교체하는 방식의 정렬 알고리즘 

- 시간 복잡도 O(N^2)

 

삽입 정렬 (Insertion Sort)

- 맨 앞의 요소는 정렬이 됐다는 가정하에 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 정렬

- 정렬이 이루어진 원소는 항상 오름차순을 유지하고 있음

- 시간 복잡도 O(N) => 최악의 경우 O(N^2)

 

퀵 정렬 (Quick Sort)

- 정렬의 기준이 되는 피벗(Pivot)을 지정한 후 피벗을 기준으로 왼쪽에서는 피벗보다 크기가 큰 원소들을, 오른쪽에는 피벗보다 크기가 작은 원소들을 찾아 서로의 위치를 교환함으로써 정렬

- 큰 원소와 작은 원소의 위치가 서로 엇갈리게 되면 작은 데이터와 피벗의 위치를 바꿈으로써 분할을 완료함

- 불안정 정렬

- 시간 복잡도 O(NlogN) => 최악의 경우 O(N^2)

 

병합 정렬 (Merge Sort)

- 리스트를 두 개의 균등한 크기의 리스트로 분할한 뒤 정렬 => 정렬된 두 리스트를 다시 하나로 합쳐 전체가 정렬된 리스트가 되도록 하는 정렬 

- 만약 부분 리스트의 크기가 충분히 작지 않으면 재귀 호출을 이용하여 다시 두 개의 리스트로 분할

- 안정 정렬

- 추가적인 메모리 공간 필요

- 시간 복잡도 O(NlogN) => 최악의 경우에도 O(NlogN)

 

힙 정렬 (Heap Sort)

- 힙 = 완전 이진 트리를 기반으로 부모 노드가 자식 노드보다 크도록 위치를 바꾸면 최대힙, 그 반대이면 최소 

(최댓값과 최솟값을 찾을때 유리)

- heapify를 진행한 후 최대 힙의 루트 노드를 pop하여 배열의 가장 오른쪽으로 정렬하고 힙에서의 마지막 원소를 루트 노드에 정렬한 뒤 다시 힙을 재구조화한 후 본 과정을 최대 힙의 크기가 2가 될때까지 반복

- 시간 복잡도 O(NlogN)