[알고리즘] 정렬 알고리즘 총 정리

Bubble sort (거품 정렬)

• n개의 원소를 가진 배열을 정렬할 때, 인접한 두 개의 데이터를 비교해가면서 정렬을 진행하는 방식
• 가장 큰 값을 배열의 맨 끝에다 이동시키면서 정렬
• 두개의 중첩된 for문을 이용해 정렬
• swap을 많이 하기 때문에 삽입 정렬과 선택 정렬보다 시간이 오래걸린다.

 

 

Selection Sort (선택 정렬)

• 주어진 데이터 중 최소값을 찾고, 맨 앞자리와 바꿔준다. 최소값을 찾고 맨 앞자리+1 인덱스와 바꿔준다... 반복

 

삽입 정렬 (Insertion Sort)

• 두번째 인덱스부터 시작해서 해당 인덱스(key 값) 앞에 있는 데이터들과 비교해 key 값보다 작은 데이터를 만나면 그 뒤에 넣는다.

• 장점
  • 거의 정렬 된 경우 매우 효율적이다. 최선의 경우 O(N)의 시간복잡도를 갖는다.
• 단점
  • 역순에 가까울수록 매우 비효율적이다. 최악의 경우로 O(N^2)의 시간복잡도를 갖는다.

 

Merge Sort (병합 정렬)

• 정렬하고자 하는 배열의 크기를 작은 단위로 나누어 정렬하고자 하는 배열의 크기를 줄이는 원리
• 더이상 나누어지지 않을 때 까지 반 씩(1/2) 분할하다가 더 이상 나누어지지 않은 경우(원소가 하나인 배열일 때)에는 자기 자신, 즉 원소 하나를 반환한다. 원소가 하나인 경우에는 정렬할 필요가 없기 때문이다. 이 때 반환한 값끼리 combine될 때, 비교가 이뤄지며, 비교 결과를 기반으로 정렬되어 임시 배열에 저장된다. 그리고 이 임시 배열에 저장된 순서를 합쳐진 값으로 반환한다. 실제 정렬은 나눈 것을 병합하는 과정에서 이뤄지는 것이다.

 

 

배열을 부분리스트로 나누고 합칠때 정렬이 이루어진다. 여기서 각각의 부분리스트는 '정렬된 상태'이고 합치는 방식은 각 부분리스트의 첫번째 원소부터 순차적으로 비교하면서 이루어진다.

이미 각각의 부분리스트는 오름차순으로 정렬되어 있기 때문에 앞부분부터 하나씩 비교하면서 정렬해준다.

 

Heap Sort (힙 정렬)

• 힙은 '최솟값 또는 최댓값을 빠르게 찾아내기 위해 완전이진트리 형태로 만들어진 자료구조'다. 부모 노드는 항상 자식 노드보다 우선순위가 높다는 조건이 있기 때문에 모든 요소들을 고려하여 우선순위를 정할 필요가 없다.
  • 완전이진트리? 리프노드를 제외한 모든 레벨의 node가 완전히 채워져 있으며 리프노드는 가능한 한 왼쪽부터 채워져 있는 구조
• 루트 노드는 항상 우선순위가 높은 노드이기 때문에 이러한 원리로 최댓값 혹은 최솟값을 빨리 찾아낼 수 있다.
• 삽입/삭제 시에도 부모노드가 자식노드보다 우선순위가 높으면 되므로 = 트리의 깊이만큼만 비교하면 되기 때문에 O(logN)의 시간복잡도를 가진다. 정렬을 하려는 대상이 n개라면 O(NlogN)의 시간복잡도를 가진다.
• heapify란, 배열을 힙의 모양으로 만드는 것이다.

내림차순 정렬은 최대 힙, 오름차순 정렬은 최소 힙을 이용해 heapify를 반복하여 아래와 같이 정렬한다.

0번 노드와 5번 노드의 값을 바꾸고 heapify, 힙사이즈 5

0번 노드와 4번 노드의 값을 바꾸고 heapify, 힙사이즈 4

 

힙에서 우선순위가 가장 높은 루트노드를 맨 마지막으로 보내고 고정시키기 -> heapify -> .. 반복!!

 

Quick Sort (퀵 소트)

• 피벗(pivot)을 기준으로 하나의 리스트를 두개의 부분리스트로 나누어 하나는 피벗보다 작은 값의 리스트, 하나는 피벗보다 큰 값의 리스트로 정렬하고 각 부분 리스트를 똑같은 방법으로 재귀적 수행해서 정렬한다.
• 분할 정복 기반, Merge Sort와 다른 점은 Merge Sort의 경우 절반으로 나누어 분할정복을 하고, Quick Sort의 경우 피벗의 값에 따라 나누어진 부분 리스트 크기가 다를 수 있다.
• 일반적으로 병합정렬보다 퀵정렬이 빠르다.

퀵소트 분할-정복

 

맨 왼쪽의 5을 pivot으로 진행

less는 5보다 크면 멈추고 more는 작으면 멈춘다. 그리고 swap

위와 같이 진행

반복하다가 more와 less가 교차하는 지점에 pivot이 위치하게 된다.

최종상태

 

계속 두개로 쪼개 n번 비교하게 되므로 시간복잡도는 O(NlogN)이 된다.

하지만 worst case는 pivot이 가장 작은 값 또는 가장 큰 값으로 설정되었을 때로, N개 리스트라면 한쪽만 N-1의 부분 리스트로 나눠지기 때문에 O(N^2)의 시간복잡도를 가진다. 그리고 리스트가 정렬되어 있는 경우 pivot을 맨앞/맨뒤 값으로 정한다면 같은 시간복잡도를 가진다.