quick sort 나누는 부분 성공

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)로 구현 (소스 코드는 첨부 파일 참조)

프로그램은 크게 입력 파일 읽는 부분, 퀵 정렬하는 부분, 결과 출력하는 부분으로 크게 나눌수 있는데 코드 자체가 간단하므로 각 부분에 대한 설명은 생략한다.

 

④ 결과 화면 캡쳐

[출처] 퀵 정렬 - Quick Sort|작성자 달인행세