public class Quicksort {
public static void main(String[] args) {
/*int arr[]={11,22,3,4,8,9,5,6,15,12,7};*/
int arr[]={11,22,3,4,6,15,12,7};
int pivot=arr.length-1;
int start=0;
int end=pivot-1;
while(start<=end){
if(start==end){
int tmp=0;
tmp=arr[start+1];// 이게 pivot의 오른쪽으로 정렬한것들중에 가장 왼쪽 아이
arr[start+1]=arr[pivot];
arr[pivot]=tmp;
break;
}
/*if(arr[end]<arr[pivot]&&arr[start]>arr[pivot] || arr[end]>arr[pivot]&&arr[start]>arr[pivot]){// 둘다 큰경우가 없다
int tmp =0; // 큰것들끼리 서로 교환하고 앞으로 한칸 가는경우 가서 결국엔 ij 만나면 큰애들은 다 정렬이 안됨
tmp=arr[start];
arr[start]=arr[end];
arr[end]=tmp;
start++;
end--;
}
else if(arr[start]<arr[pivot]&& arr[end]<arr[pivot]){
start++;
}*/
if(arr[end]>arr[pivot]){
end--;
}
else if( arr[start]<=arr[pivot]){
start++;
}
int tmp =0; // 큰것들끼리 서로 교환하고 앞으로 한칸 가는경우 가서 결국엔 ij 만나면 큰애들은 다 정렬이 안됨
tmp=arr[start];
arr[start]=arr[end];
arr[end]=tmp;
}
for(int i=0; i<arr.length; i++){
System.out.print("arr[]="+arr[i]);
}
}
}
참조 사이트 http://blog.naver.com/PostView.nhn?blogId=comthird&logNo=220066947945
1. 퀵 정렬(Quick Sort)이란
C. A. R. Hoare가 개발한 정렬 방법으로, 다음과 같은 순서로 수행되는 정렬 알고리즘이다.
① 정렬할 리스트에서 피벗(pivot)을 선택한다.
② 피벗을 기준으로 하여 피벗의 왼쪽은 피벗보다 작거나 같고 피벗의 오른쪽은 크거나 같은 리스트로 분류한다.
③ 피벗에 의해 분리된 두개의 좌우 리스트를 서로 독립적으로 퀵 정렬한다.
2. 특징
퀵 정렬은 불안정적인(unstable) 정렬 방법으로, 다른 항목들과의 비교 연산만으로 정렬을 수행하는 비교 정렬에 속한다. 또한 위에서 설명하였듯이 분할 해결 전략(divide and counquer)을 사용하는 알고리즘이다.
3. 자바(java)로 구현
void quickSort(int[] list, int left, int right) |
{ |
int pivot, i, j, temp; |
if (left < right) |
{ |
i = left; |
j = right; |
pivot = list[left]; //피벗은 정렬 대상 리스트의 left로 한다. |
|
while (i < j) |
{ |
while (list[j] > pivot) //피벗보다 큰 값은 오른쪽 |
j--; |
while (i < j && list[i] <= pivot) //피벗보다 작은 값은 왼쪽 |
i++; |
|
temp = list[i]; //왼쪽에 있는 피벗보다 큰 값과 |
list[i] = list[j]; //오른쪽에 있는 피벗보다 작은 값을 |
list[j] = temp; //서로 자리 변경한다. |
} |
|
list[left] = list[j]; //j값은 피벗보다 작은 값 중에서 가장 오른쪽에 있는 값 |
list[j] = pivot; //left와 j값을 서로 자리 변경함으로써 |
//j에 피벗이 위치하게 된다. |
quickSort(list, left, j - 1); |
quickSort(list, j + 1, right); |
} |
} |
4. 시간 복잡도
퀵 정렬에서 최선의 경우란 피벗(pivot)으로 항상 정렬 대상 리스트의 중간 값이 선택되는 경우이다. 이 경우 피벗에 의해 분리된 두개의 리스트는 길이 차가 1이하가 되므로 시간 복잡도는 O(n log n)이 된다. 최악의 경우는 피벗에 의해 분리되는 두개의 리스트 중 하나의 리스트의 길이가 항상 1이 되는 경우이다. 피벗이 정렬 대상 리스트의 최소값이나 최대값이 항상 선택되어 분리가 불균형적으로 이루어지는 경우일 것이다. 이 경우 시간 복잡도는 O(n^2)가 된다. 평균적으로 퀵 정렬의 시간 복잡도는 O(n log n)으로 알려져 있다.
5. 퀵 정렬의 개선 1 - 세 값의 메디안을 사용한 퀵 정렬
위에서 설명한 퀵 정렬은 항상 현재 정렬 대상 리스트의 첫 번째 레코드를 피벗(pivot)으로 선택한다는 것을 알 수 있다. 이러한 방법보다 더 좋은 결과를 얻을 수 있는 방법이 있는데, 현재 정렬 대상 리스트의 첫 번째, 중앙, 마지막 값 중에서 메디안을 피벗으로 선택하는 방법이다. 즉 pivot = median { K_l, K_(l+r)/2, K_r } 이다.
6. 퀵 정렬의 개선 2 - 일정 크기 이하에서 삽입 정렬의 사용
삽입 정렬(삽입정렬로 가기)은 그 단순성 때문에 일정 크기 이하 (n<=30)에서 가장 빠른 정렬 방법으로 알려져 있다. 이러한 특징을 이용하여 퀵 정렬의 수행에서 정렬 대상 리스트의 크기가 일정 크기(n=30)보다 작은 경우 퀵 정렬이 아닌 삽입 정렬로 정렬을 수행하면 성능을 개선할 수 있다.
7. 퀵 정렬 프로그램 작성
위에서 배운 내용을 참고하여 입력 리스트를 파일로 입력 받아 이를 퀵 정렬한 후 내용을 출력해주는 프로그램을 작성해보자. 정렬 항목은 자연수라고 가정한다.
① 입력 파일 : input.txt
첫번째 줄에는 리스트의 크기,
두번째 줄에는 리스트의 내용, 각 숫자는 공백으로 구분한다.
ex)
10
4 27 8 11 76 43 15 1 89 16
② 출력 형식
- 파일로부터 입력 받은 리스트의 내용을 출력
ex)
입력 리스트 ( n = 10 )
4 27 8 11 76 43 15 1 89 16
- 퀵 정렬의 각 패스 결과를 출력
L과 R은 각각 퀵 정렬 함수 호출시 넘겨운 인수 left와 right의 값을 의미한다.
ex)
퀵 정렬 시작
i 0 1 2 3 4 5 6 7 8 9 L R
1 4 8 11 76 43 15 27 89 16 0 9
1 4 8 11 76 43 15 27 89 16 2 9
1 4 8 11 76 43 15 27 89 16 3 9
1 4 8 11 16 43 15 27 76 89 4 9
1 4 8 11 15 16 43 27 76 89 4 7
1 4 8 11 15 16 27 43 76 89 6 7
퀵 정렬 종료
- 퀵 정렬 결과 리스트 출력
ex)
정렬 결과
1 4 8 11 15 16 27 43 76 89
③ 자바(java)로 구현 (소스 코드는 첨부 파일 참조)
프로그램은 크게 입력 파일 읽는 부분, 퀵 정렬하는 부분, 결과 출력하는 부분으로 크게 나눌수 있는데 코드 자체가 간단하므로 각 부분에 대한 설명은 생략한다.
④ 결과 화면 캡쳐
