sort의 종류

오늘은 Data Structure에서 배웠고, 현재 Algorithmn Analysis 과목에서 배웠던 Sort에 대한 내용을 소개하고자 한다.

 

우선 Sorting 은 말 그대로, 정렬한다는 것이다. 

 

ISBMHQ 외우면 된다.

총 이 6개의 sorting 을 배운다.

 

우선 그럼 차근차근 하나하나 살펴보자.

 

 

---

 

I 

Insertion Sort

삽입 정렬이다.

 

 

1번째부터 끝까지 훑어서 가장 작은 게 1번째, 2번째부터 끝까지 훑어서 가장 작은 게 2번째... 정렬이 끝날 때까지 반복한다.

이미 정렬되어 있는 자료구조에 삽입/제거 할 때나 배열이 작은 경우에는 매우 효율적이다. 

 

• 시간 복잡도
  • Avg: O(n^2)
  • Worst: O(n^2)
  • Best: O(n^2)

 

 

S

Selection Sort

선택 정렬이다.

 

k번째 원소를 1부터 k-1까지와 비교해 적절한 위치에 끼워넣고 그 뒤의 자료를 한 칸씩 뒤로 밀어내는 방식이다.

 

• 시간 복잡도
  • Avg: O(n^2)
  • Worst: O(n^2)
  • Best: O(n)

 

 

B

Bubble Sort

거품 정렬이다.

 

시간 복잡도가 안좋지만 코드가 단순하다. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 대문에 지어진 이름이다.

 

시간 복잡도

• Avg: O(n^2)
• Worst: O(n^2)
• Best: O(n)

 

 

M

Merge Sort

병합 정렬이다.

 

배열의 길이가 1이 될 때까지 2개의 부분 배열로 분할한다.
그 후, 2개의 부분 배열을 합병하고 정렬한다. 모든 부분 배열이 합병될 때까지 반복한다.
부분 배열을 위한 추가적인 메모리 공간이 필요하다는 단점이 있다.

 

• 시간 복잡도
  • Avg: O(nlogn)
  • Worst: O(nlogn)
  • Best: O(nlogn)

 

H

Heap Sort 

힙 솔트이다.

 

 

선택 정렬과 거의 같지만, 힙을 사용해서 가장 큰 원소를 찾는다는 차이점이 있다.
트리 기반으로 최대 힙 트리(내림차순), 최소 힙 트리(오름차순)을 구성해 정렬한다.
항상 nlogn의 성능을 발휘해 가장 안정적인 성능을 보인다.
다만, 실제로는 퀵정렬이 일반적으로 빠르다.

 

• 힙이란?
  • 완전 이진 트리의 일종으로 우선순위 큐를 위해 만들어진 자료구조이다. 여러 값 중 최댓값/최솟값을 빠르게 찾도록 만들어진 자료구조이다.
  • 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 존재한다. (일종의 반정렬상태)
  • 이진 탐색 트리와 달리 중복된 값을 허용한다

 

• 동작 과정
  1. 배열을 힙 트리로 만든다.
  2. 배열의 최상단 부모 노드를(0번째) 마지막 인덱스와 교환한다.
  3. 바뀐 최상단 부모 노드보다 자식의 노드(왼쪽, 오른쪽 중 큰 노드)가 크다면 자식과 위치를 바꾼다. 이를 반복하여 노드의 올바른 위치를 찾는다.
  4. 2~3번 과정을 반복한다.
• 시간 복잡도
  • Avg: O(nlogn)
  • Worst: O(nlogn)
  • Best: O(nlogn)
  •  

 

Q

Quick Sort

빠른 정렬이다.

 

 

데이터 집합 내에 임의 기준(피벗)값을 정하고, 집합을 해당 피벗을 기준으로 두 개의 부분 집합으로 나눈다. 한 쪽 집합에는 피벗보다 작은 값을, 나머지 한 쪽 집합에는 피벗보다 큰 값을 넣는다. 더 이상 쪼갤 부분 집합이 없을 때까지 위 과정을 반복한다.

 

 

• 동작 과정
  1. 피벗보다 큰 left를 찾음
  2. 피벗보다 작은 right를 찾음
  3. left이 right보다 왼쪽에 있으면 둘이 자리바꾸고 left++, right--
  4. 1~3번 과정을 해당 배열의 나머지에 대해서 반복
  5. 집합을 왼쪽 부분 집합, 오른쪽 부분 집합에 대해서 1~4번 과정을 반복
• 단점
  • 피벗을 계속 최댓값/최솟값으로 잘못 잡으면 최악의 결과를 초래한다.
• 단점의 해결 방법
  • 피벗을 랜덤으로 잡는 것
  • 피벗을 배열의 중간 혹은 중간값으로 잡는 것
• 시간 복잡도
  • Avg: O(nlogn)
  • Worst: O(n^2)
  • Best: O(nlogn)

 

 

 

다음은 각 정렬에 대한 Time Complexity 이다 .

 

 

 

 

In-place Sorting 알고리즘

• Insertion Sort
• Selection Sort
• Bubble Sort
• Shell Sort
• Heap Sort
• Quick Sort

Not in place Sorting 알고리즘

• Merge Sort
• Counting Sort
• Radix Sort
• Bucket Sort