정렬
정렬 알고리즘 |
정의 |
시간복잡도 |
삽입 |
대상을 선택해 정렬된 영역에서 선택 데이터의 적절한 위치를 찾아 삽입하면서 정렬하는 방식 |
O(N) ~ O(N^2) |
버블 |
데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 방식 |
O(N^2) |
선택 |
대상에서 가장 크거나 작은 데이터를 찾아가 선택을 반복하면서 정렬하는 방식 |
O(N^2) |
퀵 |
pivot 값을 선정해 해당 값을 기준으로 정렬하는 방식 |
O(NlogN) ~ O(N^2) |
힙 |
이진트리를 이용하여 최대힙(오름차순)/최소힙(내림차순) 트리를 구성해 정렬하는 방식 |
O(NlogN) |
병합 |
이미 정렬된 부분 집합들을 효율적으로 병합해 전체를 정렬하는 방식 |
O(NlogN) + 추가적인 메모리 필요 |
기수 |
데이터의 자릿수를 바탕으로 비교해 데이터를 정렬하는 방식 |
O(N) + 추가적인 메모리 필요 |
퀵정렬이란?
기준값을 선정해 해당 값보다 작은데이터와 큰 데이터를 분류하여 반복하는 것을 의미
(기준 값 산정에 따라서 시간복잡도가 달라지고, 평균 시간복잡도는 O(NlogN)이다.
퀵 정렬 과정
- 데이터를 분할하는 pivot을 설정한다
- pivot을 기준으로 다음 과정을 거쳐 데이터를 2개의 집합으로 분리한다
- start가 가리키는 데이터가 pivot이 가리키는 데이터보다 작으면 start +1 이동
- end가 가리키는 데이터가 pivot이 가리키는 데이터보다 크면 end를 end -1 이동
- start가리키는 데이터가 pivbot데이터보다 크고, end가 가리키는 데이터가 pivot이 가리키는 데이터보다 작으면 start,end가 가리키는 데이터를 swap하고 start +1 , end -1 이동
- start와 end가 만날때까지 (2-1 ~ 2-3) 반복
- start와 end가 만나면 만난 지점에서 가리키는 데이터와 pivot이 가리키는 데이터를 비교하여 pivot이 가리키는 데이터가 크면 만난 지점의 오른쪽에, 작으면 만난 지점의 왼쪽에 pivot이 가리키는 데이터를 삽입
- 분리집합에서 다시 pivot을 선정한다
- 분리집합이 1개 이하가 될때까지 과정 1 ~ 3 을 반복한다
퀵정렬은 코딩테스테에서 자주 등장하며, 재귀함수로 구현하는 것을 추천
퀵 정렬 예시
퀵 정렬 구현
- swap()
- quickSort()
- 2개의 분류로 나누어진 정렬 범위들을 재귀함수를 통해 정렬 진행
- partition()
- 실제적으로, 분류가 진행되는 과정
- leftPointer > rightPointer가 되는 지점에서, endIndex(==pivot) 을 swap해줌 (leftPointer <-> endIndex)
public class App {
public static void main(String[] args) throws Exception {
int[] arr = {2,3,1,5,4,6};
quickSort(arr, 0, arr.length - 1);
printArray(arr);
}
private static void quickSort(int[] arr, int startIndex, int endIndex){
if( startIndex < endIndex ){
int pivot = partition(arr, startIndex, endIndex);
quickSort(arr, startIndex, pivot -1 );
quickSort(arr, pivot +1 , endIndex);
}
}
private static void swap (int[] arr, int i , int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
private static int partition(int[] arr, int startIndex, int endIndex){
int pivot = arr[endIndex];
int leftPointer = startIndex;
int rightPointer = endIndex -1;
while(leftPointer <= rightPointer){
while( leftPointer <= rightPointer && arr[leftPointer] < pivot ){
leftPointer++;
}
while( leftPointer <= rightPointer && arr[rightPointer] > pivot){
rightPointer--;
}
if (leftPointer <= rightPointer){
swap(arr, leftPointer, rightPointer);
leftPointer++;
rightPointer--;
}
}
swap(arr, leftPointer, endIndex);
return leftPointer;
}
private static void printArray(int[] arr){
for (int i : arr) {
System.out.println(i);
}
}
}