[알고리즘] 퀵정렬

 

이번 포스팅에서는 퀵정렬 함수를 생성하여 main에서 바로 사용이 가능하도록 코딩하는 방법에 대해 다루어보았다.

 

---

 

1. 이론 과정

 

: 퀵정렬은 한 번 반복시 피벗이 제자리를 찾는다.

 

---

 

[ 4 1 10 2 8 7 9 3 6 5 ]
  P L                    H

위의 상황에서 정렬은 시작된다고 가정한다.

1. pivot 피벗,피봇 : [0]에 위치한 값 : 4
2. pivot에 맞지않는 위치를 찾음
 [L]의 값 < pivot
 [H]의 값 > pivot

 

[L]의 값 <--교환--> [H]의 값
[ 4 1 3 2 8 7 9 10 6 5 ]
       L (교환됨) H

*if(L과 H가 교차되면 : cross면) 교환하지않고 종료*

 

3. pivot <--교환--> [H]의 값
[ 2 1 3 4 8 7 9 10 6 5 ]
        H L
4. pivot은 본인자리를 찾고,
[1 2 3]
   H L
pivot 2
[8 7 9 10 6 5]
   L        H
pivot 8

 

 

 

---

 

 

2. 구현

 

package quick;

public class Test01 {

   public static void quick(int[] data,int start,int end) {
      // 1. 피벗 설정
      int pivot=data[start];
      int L=start+1;
      int H=end;

      // 2. 피벗과 맞지않은 값 검색
      while(L!=H) {     //원래 l<h였는데 마지막부분 오류때문에 수정한 것! 둘이 같이 않을때 반복!
         while(data[L]<pivot) {
            L++;
         }
         while(data[H]>pivot) {
            H--;
         }
         if(L>=H) { // cross 교차
            break;
         }
         int tmp=data[L];
         data[L]=data[H];
         data[H]=tmp;
      }

      // 3. 피벗교환
      int tmp=data[start];
      data[start]=data[H];
      data[H]=tmp;
     
      // 4. 재귀 호출
      if(start<H-1) {
         quick(data,start,H-1);
      }
      if(H+1<end) {
         quick(data,H+1,end);
      }
   }
   public static void main(String[] args) {
      int[] data= {4,1,10,2,8,7,9,3,6,5};

      quick(data,0,data.length-1);
      // 결과보기
      for (int v:data) {
    	  System.out.print(v+" ");
      }
   }
}