[알고리즘] 1. 정렬

1. 정의

정렬(Sort)이란 주어진 데이터를 일정한 규칙에 따라 재배열하는 것을 의미한다. 일반적으로 우리는 데이터를 정렬할 때, 오름차순(Ascending) 혹은 내림차순(Descending)으로 정렬 가능하다. 정렬 알고리즘은 많은 것들이 있는데, 현재도 꾸준히 제안되고 발전되고 있다. 많은 정렬 알고리즘들은 데이터의 양, 데이터의 초기 배열 상태 등에 따라서 그 성능이 달라지므로, 상황에 알맞은 정렬법이 필요하다.

2. 종류

1) 삽입 정렬(Insertion Sort)

현재 선택된 데이터를 정렬된 데이터 부분에서 위치를 찾아 '삽입'과정을 통해 정렬하는 방법이다.

성능은 평균적으로 O(n^2)이다. 다만 어느 정도 정렬된 데이터인 경우 매우빠른 속도를 자랑한다.

>_본문으로

2) 버블 정렬(Bubble Sort)

거품이 올라가듯이 인접한 두개의 데이터를 비교해 위치를 바꾸어주는 방식으로 정렬하는 방법이다.

성능은 평균적으로 O(n^2)이다.

>_본문으로

3) 선택 정렬(Selection Sort)

현재 선택된 데이터 이후의 데이터 중 가장 작은 데이터의 위치를 찾아 현재 데이터와 위치를 바꾸는 방식으로 정렬하는 방법이다.

성능은 평균적으로 O(n^2)이다.

>_본문으로

4) 병합 정렬(Merge Sort)

Divide and Conquer 방법을 통해 구현한 정렬 알고리즘이다. 데이터를 두 개로 쪼개는 과정을 반복하여, 완전히 쪼갠 뒤 합쳐가며 정렬하는 방법이다.

성능은 평균적으로 O(nlogn)이다.

>_본문으로

5) 힙 정렬(Heap Sort)

Heap을 이용한다. Maxheap, 혹은 Minheap을 구현해 데이터를 하나씩 삭제해가며 정렬하는 방법이다.

성능은 평균적으로 O(nlogn)이다.

>_본문으로

6) 퀵 정렬(Quick Sort)

일반적으로 가장 빠르다고 알려진 알고리즘이다. Divide and Conquer 방법으로 구현되었으며, pivot을 선택해 pivot보다 작은 데이터는 왼쪽으로 그보다 큰 데이터는 오른쪽으로 몰아 데이터를 쪼갠다. 쪼개진 데이터에서 다시 한번 각각 pivot을 선택해 앞선과정을 반복한다. 이 과정을 쪼개진 데이터의 크기가 1이 될 때까지 반복한 뒤, 데이터를 합치는 방법이다.

성능은 평균적으로 O(nlogn)이다. 다만 퀵 정렬의 경우, 최악의 경우에 O(n^2)까지 느려진다.

>_본문으로