07-3 퀵 정렬

※ 퀵 정렬(Quick Sort)

 - 기준값을 중심으로 왼쪽 부분집합과 오른쪽 부분집합으로 분할(divide) 한다. 왼쪽 부분집합에는 기준값보다 작은 

   원소들을 이동시키고, 오른쪽으로는 기준값보다 큰 원소들을 이동시킨다. 이때 사용하는 기준값을 피봇(pivot)이라 한다.

   일반적으로 피봇은 전체 원소 중에서 가운데에 위치한 원소를 피봇으로 선택한다.

 - 퀵 정렬은 다음의 두가지 기본 작업을 반복 수행하여 완성한다.

1. 분할(divide) : 정렬할 자료들을 기준값을 중심으로 2개의 부분집합으로 분할한다.
2. 정복(conquer) : 부분집합의 원소들 중에서 기준값보다 작은 원소들은 왼쪽 부분집합으로, 기준값보다 큰 원소들은                           오른쪽 부분집합으로 정렬한다. 부분집합의 크기가 1 이하로 충분히 작지 않으면 순환 호출을 이용해  다시 분할한다.

 - 분할 작업을 순환적으로 반복하면서 피봇의 왼쪽 부분집합과 오른쪽 부분집합을 정렬하는 방법을 반복하면서 전체 원소들을 정렬한다.

부분집합으로 분할하기 위해 L과 R을 사용한다. 왼쪽 끝에서 오른쪽으로 움직이면서 크기를 비교하여 피봇보다 크거나 같은 원소를 찾아 L로 표시하고, 오른쪽 끝에서 왼쪽으로 움직이면서 피봇보다 크거나 같은 원소를 찾아 R로 표시한 후에 두 원소를 교환한다.

L과 R이 만나면 피봇과 R의 원소를 서로 교환하고 피봇의 위치를 확정한다. 피봇의 확정된 위치를 기준으로 만들어진 왼쪽 부분집합과오른쪽 부분집합에 대해 퀵 정렬을 순환적으로 반복 수행한다. 부분집합의 크기가 1 이하가 되면 퀵 정렬을 종료한다.

 - 퀵 정렬은 버블 정렬과 마찬가지로 교환 방식의 정렬 방법이다. 버블 정렬은 인접한 두 개의 원소를 비교하며 자리를 교환하기 때문에 원소가 이동하는 거리가 1이 되어 자기 자리를 찾기까지 비교 횟수와 교환 횟수가 많아진다. 퀵 정렬은 이런 점을 개선하여 자기 자리에 최대한 가까이 이동시켜 비교 횟수와 자리 교횐 횟수를 줄인 정렬 방식이다.

피봇 6/ L과 R의 크기를 비교해 가면서 R과 L이 만날 때 까지 비교하고 조건이 맞는 원소들의 경우 교환을 한다

즉 5와 7 교환, 마지막에 L과 R은 3에서 만나게 될텐데 이때 R인 3과 피봇인 6을 교환

다시 중간 원소인 2를 피봇값으로 설정 후 L과 R 이동... 1과 4교환 후 L과R은 5에서 만남 

조건에 따라 R과 피봇의 원소를 교환한다.

나머지도 같은 방식으로 정렬한다.

Main

public class Main {

       public static void main(String[] args) {

              

              int a[] = {69,10,30,2,16,8,31,22};

              QuickSort qs = new QuickSort();

              System.out.println("\n정렬할 원소 : ");

              for(int i =0; i<a.length; i++){

                     System.out.printf(" %d ", a[i]);

              }

              System.out.println();

              qs.sorting(a,0,7);

       }

}

QuickSort

import java.util.List;

public class QuickSort {

       

       int[] a;

       

       public QuickSort() {

              // TODO Auto-generated constructor stub

              this.a= null;

       }

       

       public void sorting(int a[], int l, int r){

              

              if(this.a==null){

                     this.a = a;

              }

              if(l==r || l>r){

                     return;

              }

              int begin =l;

              int end = r;

              int pivot = (l+r)/2;

              int temp;

              do{

                     while((a[l] < a[pivot]) && (l<r)){

                           l++;

                     };

                     while((a[r] >= a[pivot]) && (l<r)){

                           r--;

                     };

                     

                     if(l != r){

                           temp = a[r];

                           a[r] = a[l];

                           a[l]= temp;

                     }else if ( l == r && l != pivot){

                           temp = a[r];

                           a[r] = a[pivot];

                           a[pivot] = temp;

                           break;

                     }

              }while(l<r);

       

              for(int i =0; i<a.length;i++){

                     System.out.print(a[i] + " ");

              }

              System.out.println();

              

              if(begin<end){

                     if(r-1 >-1){

                           sorting(this.a, begin, r-1);

                     }

                     if(r+1 < a.length-1){

                           sorting(this.a, r+1, end);

                     }

              }

       }

}