정렬 알고리즘
- 왜 정렬을 해야할까?
탐색을 빠르게 하기 위해서
- 같은 시간복잡도를 갖고 있더라도 요소에 따라 달라짐.
버블 정렬(Bubble sort) (평균 및 최악 : O(n^2))
- 인접한 두 원소를 검사하며 정렬하는 방법
- 시간복잡도 O(n^2)
- 코드는 단순하지만, 정말 비효율적이라 거의 쓰이지 않음. 다만 이미 정렬된 데이터에 대해서 검사하는데는 O(N)으로 간단하게 알 수 있음.
- 1번째부터 n번째까지 swap을 통해 정렬. 1번째부터 n-1번째 까지 swap. ...
O(N + N-1 + N-2 + ... +1) => O(N(N+1)/2) => O(N^2)
선택 정렬(Selection sort) (평균 및 최악 : O(n^2)
- 선형 탐색을 하며 가장 작은 원소를 배열의 맨 앞으로 보낸다. 그 다음에는 2번째 원소부터 끝까지 탐색.
- simple하지만, 비효율적인건 마찬가지.
삽입 정렬(Insert sort) (평균 및 최악 : O(n^2))
- O(n^2) 정렬 방식 중 평균적으로 가장 빠름
- 역순으로 정렬되어 있는 경우거나, 작은 값이 뒤에 몰려있는 경우 최악의 성능을 갖는다.
- K번째 원소를 1~k-1 원소와 비교하여 적절한 위치에 끼워넣은 후, 그 뒤의 자료를 한 칸씩 뒤로 밀어내는 방식. 이때 k-1, k-2, ... 1의 순서로 접근한다.
힙정렬(heap sort) (평균 및 최악 : O(n log n))
- 힙 자료구조를 사용한 정렬
- 힙의 root의 값을 하나씩 뽑아오며 정렬을 수행한다.
- 값을 추출하는데 O(1), 저장, 삭제 시 heapify를 수행하는데 O(log N)
- N번 데이터를 추출해야 하므로 O(nlog n)이다.
병합 정렬(merge sort) (평균 및 최악 : O(n log n))
- 원소의 개수가 1 또는 0이 될 때까지 두 부분으로 자른 뒤 자른 순서의 역순으로 크기를 병합해 나간다.
- 성능은 퀵정렬보다 떨어지고, 데이터 크기만한 메모리가 더 요구되지만, stable sort라는 강점이 있다.
퀵 정렬(Quick sort) (평균: O(n log n) , 최악: O(n^2))
- 평균적인 상황에서 최고의 성능을 갖는 정렬 알고리즘.
- 정렬된 상태에서 최악의 성능 O(n^2) - > 피벗이 항상 최대 혹은 최소값이 되기 때문 - > 피벗을 랜덤값으로 설정하기도 함
- 피벗을 기준으로 왼쪽은 피벗보다 작은 값, 오른쪽은 피벗보다 큰 값으로 정렬.