Java - 정렬 알고리즘 - 7 (퀵 정렬)
◎퀵 정렬
pivot이라는 특정한 값을 기준으로 분할 정복(Devide and Conquer) 기법을 사용하여 작은 부분으로 분할하여 정렬하는 방식
◎퀵 정렬의 특징
1. 비교 정렬(comparison sort)
퀵 정렬은 데이터를 비교하면서 찾는다.
2. 제자리 정렬(in-place sort)
정렬의 대상이 되는 데이터 외에 추가적인 공간을 필요로 하지 않는다.
3. 불안정 정렬(unstable sort)
정렬되지 않은 상태에서 같은 키값을 가진 원소의 순서가 정렬 후에도 유지되지 않는다.
◎퀵 정렬의 동작
1. 피벗 선택(일반적으로 맨 왼쪽, 맨 오른쪽 또는 중간 index의 값 중 하나를 피벗으로 정한다)
2. 피벗을 기준으로 왼쪽에서부터는 피벗보다 큰 값을 찾고, 오른쪽에서부터는 피벗보다 작은 값을 찾는다
3. 찾은 두 값을 교환한다
4. 왼쪽 탐색 idx가 오른쪽 탐색 idx보다 커질 때까지 계속해서 피벗보다 큰 값, 피벗보다 작은 값을 찾고 교환한다
(교환이 모두 끝나면 배열은 왼쪽 탐색 idx가 오른쪽 탐색 idx보다 커진 지점을 기준을 기준으로 왼쪽은 모두 작은 값, 오른쪽은 모두 큰 값이 된다)
6. 왼쪽 탐색 idx가 오른쪽 탐색 idx보다 커진 지점을 기준으로 왼쪽과 오른쪽을 부분 리스트로 분할해서 1~4 과정을 반복한다(Divide)
7. 인접한 부분리스트끼리 합친다(Conqure : 정복)
-맨 왼쪽 원소를 pivot으로 정한 경우 quicksort의 동작
◎퀵 정렬의 구현
퀵 정렬은 분할이 되지 않을때(pivot을 기준으로 나누었을 때, 모든 원소가 pivot보다 크거나, 모든 원소가 pivot보다 작은 경우) 가장 성능이 저조하다.
그러므로, 무조건 분할을 시키기 위해, 맨 왼쪽 원소, 맨 오른쪽 원소, 중간 index 원소의 값 중 중간값을 pivot으로 정하였다.
1. 재귀적 구현
package SortAlgorithm;
import java.util.Arrays;
public class sort {
// 퀵 정렬(재귀함수 사용) -1
private void recursive_quicksort(int[] numarr) {
recursive_innerquicksort(numarr, 0, numarr.length - 1);
print(numarr, "재귀적 퀵 정렬");
}
// 퀵 정렬(재귀함수 사용) -2
private void recursive_innerquicksort(int[] numarr, int firststart, int firstend) {
if(firststart>=firstend) {
return;
}
int start = firststart;
int end = firstend;
// 효율적인 pivot 값을 얻기 위해서 첫값, 마지막값, 중간값 중에
// 크기가 중간인 값을pivot으로 선택
int[] tmp = new int[3];
tmp[0] = numarr[start];
tmp[1] = numarr[(start + end) / 2];
tmp[2] = numarr[end];
Arrays.sort(tmp);
int pivot = tmp[1];
//pivot보다 작은 숫자는 pivot 왼쪽으로, pivot보다 큰 숫자는 pivot 오른쪽으로
while (start <= end) {
while (numarr[start] < pivot)
//numarr[start] < pivot이면, pivot왼쪽에 pivot보다 작은 수가 있다는 뜻
start++;
while (numarr[end] > pivot)
//numarr[end] > pivott이면, pivot오른쪽에 pivot보다 큰 수가 있다는 뜻
end--;
//'pivot보다 작은 숫자는 pivot 왼쪽으로, pivot보다 큰 숫자는 pivot 오른쪽으로'가
//만족되지 않는 경우 숫자 교환
if(start <= end) {
swap(numarr, start,end);
start ++;
end --;
}
}
recursive_innerquicksort(numarr,firststart, start-1); //pivot왼쪽 원소들 다시 재귀로 정렬
recursive_innerquicksort(numarr,start,firstend); //pivot오른쪽 원소들 다시 재귀로 정렬
}
// swap
private void swap(int[] numarr, int i, int j) {
int temp = numarr[i];
numarr[i] = numarr[j];
numarr[j] = temp;
}
// 출력
private void print(int[] numarr, String sortname) {
System.out.println(sortname + "로 정렬된 배열:" + Arrays.toString(numarr));
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] numarr = { 5, 1, 3, 4, 2, 6 }; // 정렬할 배열
System.out.println("원래 배열:" + Arrays.toString(numarr));
sort Sort = new sort();
Sort.recursive_quicksort(numarr);
}
}
실행 결과:
원래 배열:[5, 1, 3, 4, 2, 6]
재귀적 퀵 정렬로 정렬된 배열:[1, 2, 3, 4, 5, 6]
2. 비재귀적 구현
재귀 함수는 직관적으로 이해하기 쉽지만, 언제나 overflow의 위험이 내재되어있기 때문에 재귀 함수를 사용하는 건 위험할 수도 있다. 비재귀적 퀵 함수에서는 재귀 함수를 대체하여 stack 자료 구조를 이용하였다
package SortAlgorithm;
import java.util.Arrays;
import java.util.Stack;
public class sort {
//퀵 정렬(stack 사용, 재귀함수 x)
private void stack_quicksort(int[] numarr) {
Stack<Integer> startidx = new Stack<>();
Stack<Integer> endidx = new Stack<>();
startidx.add(0);
endidx.add(numarr.length-1);
while(!endidx.isEmpty()){
//startidx와 endidx 스택은 한 쌍이므로 endidx가 비었다는 것은
//startidx도 비었다는 것을 의미한다 ==> 정렬할 것이 더 이상 없다
int firststart = startidx.pop();
int firstend = endidx.pop();
int start = firststart;
int end = firstend;
int[] tmp = new int[3];
tmp[0] = numarr[start];
tmp[1] = numarr[(start + end) / 2];
tmp[2] = numarr[end];
Arrays.sort(tmp);
int pivot = tmp[1];
//pivot보다 작은 숫자는 pivot 왼쪽으로, pivot보다 큰 숫자는 pivot 오른쪽으로
while (start <= end) {
while (numarr[start] < pivot)
//numarr[start] < pivot이면, pivot왼쪽에 pivot보다 작은 수가 있다는 뜻
start++;
while (numarr[end] > pivot)
//numarr[end] > pivott이면, pivot오른쪽에 pivot보다 큰 수가 있다는 뜻
end--;
//'pivot보다 작은 숫자는 pivot 왼쪽으로, pivot보다 큰 숫자는 pivot 오른쪽으로'가
//만족되지 않는 경우 숫자 교환
if(start <= end) {
swap(numarr, start,end);
start ++;
end --;
}
}
if(start-1 > firststart) {
// 왼쪽 정렬할 부분이 남은경우
// startidx와 endidx 스택에 정렬할 부분의 시작 인덱스 끝 인덱스 추가
startidx.add(firststart);
endidx.add(start-1);
}
if(start < firstend) {
// 오른쪽 정렬할 부분이 남은경우
// startidx와 endidx 스택에 정렬할 부분의 시작 인덱스 끝 인덱스 추가
startidx.add(start);
endidx.add(firstend);
}
}
print(numarr, "비재귀적 퀵 정렬");
}
// swap
private void swap(int[] numarr, int i, int j) {
int temp = numarr[i];
numarr[i] = numarr[j];
numarr[j] = temp;
}
// 출력
private void print(int[] numarr, String sortname) {
System.out.println(sortname + "로 정렬된 배열:" + Arrays.toString(numarr));
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] numarr = { 5, 1, 3, 4, 2, 6 }; // 정렬할 배열
System.out.println("원래 배열:" + Arrays.toString(numarr));
sort Sort = new sort();
Sort.stack_quicksort(numarr);
}
}실행 결과:
원래 배열:[5, 1, 3, 4, 2, 6]
비재귀적 퀵 정렬로 정렬된 배열:[1, 2, 3, 4, 5, 6]
◎퀵 정렬의 시간 복잡도
일반적으로 같이 O(NlogN)의 시간 복잡도를 가지는 병합 정렬보다 더 좋은 정렬 성능을 보인다.
하지만 분할이 되지 않는 특정한 경우(ex. 정렬된 배열)에는 O(N^2)의 최악의 성능을 보여준다.
◎Sorting algorithm 시간 복잡도(time complexity) & 평균 정렬 속도(average sorting rate)
◎정렬 알고리즘 구현-github
github.com/jerry-ryu/java_problemsolving_algorithm/tree/main/sorting_algorithm
jerry-ryu/java_problemsolving_algorithm
solving problems and learning algorithm using java - jerry-ryu/java_problemsolving_algorithm
github.com