(8) 퀵정렬

package weekend02;
 
public class Quick {
    static void quick(int[] data, int start, int end) {
        if (start >= end) {
            return;
        }
 
        int P = data[start]; // 배열의 첫번째 값
        int L = start + 1; // 첫번재 값 다음값이 L이된다
        int H = end; // 마지막 배열의 숫자
 
        // --------- 이제 비교하며 시작할것 --------
        // 몇번반복하여 제자리를 찾아갈지 모르기때문에
 
        while (true) {
            // P값이 배열[L]값보다 작다면 멈춰
            // 몇번만에 멈출지 모름!
            while (P > data[L]) {
                if (L == end) { // 만약 L이 끝까지 도착했다면?
                    break; // 없는 index 오류
                }
                L++; // 계속 다음값을 본다
            }
            // P값이 배열[H]값보다 크다면 멈춰
            while (P < data[H]) {
                if (H == start) { // 만약 H가 맨 아래 도착했면?
                    break; // 없는 index 오류
                }
                H--; // 계속 다음값을 비교
            }
 
            System.out.print("멈춘값 L : " + L + " H : " + H);
            System.out.println();
 
            // 두개의 L과 H가 동일하거나 교차되었다면
            // P의 값과 H의 값을 변경하고 종료할 것이다
 
            if (L >= H) {
                int tmp = data[start];
                data[start] = data[H];
                data[H] = tmp;
                break;
            }
            // 두개의 L과 H가 멈췃다면 안의 값을 교환해라
            int tmp = data[L];
            data[L] = data[H];
            data[H] = tmp;
        }
 
        quick(data, start, H - 1); // H는 현재 잘들어간 정수의 index위치이다
        // 그 아래를 조사하기 위해 start ~ H-1 까지 퀵정렬
 
        quick(data, H + 1, end); // H은 현재 잘들어간 정수의 index 위치이다
        // 그 위를 조사하기 위해 H+1 ~ end 까지 퀵정렬
    }
 
    public static void main(String[] args) {
 
        // 퀵정렬
 
        int[] data = { 5, 1, 9, 10, 4, 2, 7, 3, 6, 8 };
 
        System.out.println("현재 배열값");
        for (int i = 0; i < data.length; i++) {
            System.out.print(data[i] + " ");
        }
        System.out.println(); // 줄정렬
 
        quick(data, 0, data.length - 1);
        // 메서드 시그니처: 함수 3요소-> input,output,기능
        // int[]x1, intx2 | output X | 기능 : 퀵 정렬
 
        System.out.println("메소드 이후 배열값");
        for (int i = 0; i < data.length; i++) {
            System.out.print(data[i] + " ");
        }
 
    }// main
}// class

 

퀵정렬

이름과 같이 퀵(Quick)정렬 빠른 정렬을 뜻한다

퀵정렬을 구현하는 방법은 다양하다 나는 그중에

피벗을 가장 왼쪽의 기준을 두고 퀵정렬을 하겠다!

 

퀵정렬의 매커니즘은 아래와 같다

하나의 리스트를 피벗(pivot)을 기준으로 두 개의 부분리스트로 나누어

하나는 피벗보다 작은 값들의 부분리스트

다른 하나는 피벗보다 큰 값들의 부분리스트로 정렬한 다음

각 부분리스트에 대해 다시 위 처럼 재귀적으로 수행하여 정렬하는 방법이다.

 

 

퀵 정렬의 전체적인 과정은 이렇다.

 

1. 피벗을 하나 선택한다.

 

2. 피벗을 기준으로 양쪽에서 피벗보다 큰 값, 혹은 작은 값을 찾는다.

왼쪽에서부터는 피벗보다 큰 값을 찾고, 오른쪽에서부터는 피벗보다 작은 값을 찾는다.

 

3. 양 방향에서 찾은 두 요소(값)를 교환한다

 

4. 왼쪽에서 탐색하는 위치와 오른쪽에서 탐색하는 위치가

엇갈리지 않을 때 까지 2번으로 돌아가 위 과정을 반복한다

 

5. 엇갈린 기점(Cross)을 기준으로 두 개의 부분리스트로 나누어 1번으로 돌아가

해당 부분리스트(배열)의 길이가 1이 아닐 때 까지 1번 과정을 반복한다

 

6. 인접한 부분리스트끼리 합친다.

 

위 6가지 과정에 의해 정렬되는 방식이다.

2~3번 과정의 경우 좀 더 구체적으로 말하자면

대부분의 구현은 현재 리스트의 양 끝에서 시작하여 왼쪽에서는 피벗보다 큰 값을 찾고

오른쪽에서는 피벗보다 작은 값을 찾아 두 원소를 교환하는 방식이다

그래야 피벗보다 작은 값은 왼쪽 부분에

피벗보다 큰 값들은 오른쪽 부분에 치우치게 만들 수 있기 때문이다

 

위의 만든 퀵정렬 코드 설명

1. 메인메소드 설명

• 정렬을 위한 배열값을 정리하여 data [ ] 안에 넣어두었다
• 현재 배열값을 출력하여 결과값과 비교할수 있도록
  for문을 이용해출력문구를 만들었다
  
  
• 퀵정렬을 사용할 메소드를 이용하여 해당 배열을 정렬할 것이다
  • 메소드 시그니쳐 (함수 3요소) ㅡ> input, output,기능
  • input 값을 먼저 생각해보면 이용할 "배열"이 필요할것 같고
    L값을  이용할 int값, H를 이용할 int값 총 3개의 인풋값이 필요할것이다
  • output은 배열을 메소드를 이용하여 변경하기때문에
    객체인 배열은 메소드안에서 값이 바뀌기때문에 output값은 필요없다
    
    
  • 기능이름은 퀵정렬을 이용한 quick을 메소드이름으로 적었다

 

2. 메소드 설명 (퀵정렬 메소드)

 

위의 전체적인 과정 1~6을 스도코딩으로 작성해보면 된다

 

1. 배열의 첫번째 값을 피벗으로 설정하고

피벗을 제외한 start값, end값을 표현할 변수를 만든다!

 

2. start값에서 end값을 피벗값과 비교하며 값을 교환한다

• 언제 완성이 될지 모르기때문에 while문을 사용한다
  
  
• 예외상황을 항상 생각해야한다
  
  • 피벗값이 배열안의 최대값이라
    L 값이 end값까지 변경없이 갈수도 있는경우
    
    
  • 피벗값이 배열안의 최소값이라
    H 값이 start값까지 변경없이 갈수도 있는경우

 

3. 피벗과 비교하여 L 값이과 H 값이 결정되어 멈추게되면

교환알고리즘을 이용하여 L 값과 H 값을 변경해준다

 

4. 1 ~ 3번을 반복하여 L 값과 H 값이 교차(Cross)가되면

피벗값과 H 위치의 값을 교환한다

4번을 실행하게되면 피벗값이 배열의 자기위치에 들어가게된다!

 

5. 피벗값의 기준으로 아래값들과 위의값들을 재귀함수를 이용하여 

다시 배열로나눠주고 해당 알고리즘을 반복한다

 

그것을 코드와하여 위의 코드처럼 표현할수 있다

 

---

코드의 조건식을 이해하는 방법

나의 주석을 적어놓아 정리하였다

 

1. if ( start >= end ) 재귀함수를 종료시켜줄 조건문

**** 왜 start가 end보다 >= 야 하는지
start == end 끝날줄 알았다
하지만 end는 H -1 하여 만든 숫자여서

배열 퀵정렬에서 L값이 그대로있고 H값이 끝까지 가는경우 나눠지게되면 그때 H값이 L값과 동일한 위치에 있기에H - 1을 하며 end값이 start보다 낮아지는 상황이 있다

 

2. L값과 H값을 증가시키는 조건문에서

 

L값을 차례로 확인하는 while문에서

while문의 조건식을 true로 놓는것이 아닌

조건식에서 그 답을 찾는것도 센스가 될것이다!

(H값도 마찬가지)

- 변환

 

3. 교차상황

 

if (L >= H)
**** 왜 L > H가 아니라 L >= H 인가

L과 H가 동일한 경우가 나오더라 (이것도 교차로 생각해야한다)
나눠진 배열 ( 4 1 2 3 ) 을 할때 P=4라면 L=3 H=3이 나오는데
L은 끝까지가고 H는 가만히 있는상황에서 발생한다
그렇기때문에 이진검색과 다르게 해당 교차현상은 같은경우에도 포함이다

 

4. 재귀함수 quick(data, start, H - 1); 사용시

 

H는 현재 잘들어간 정수의 index위치이다
그 아래를 조사하기 위해 start ~ H-1 까지 퀵정렬
*** start부분에 들어갈 input값이 0인줄 알았으나

디버깅표를 그려보며 확인해보니
아래배열을 확인할때는 0일때 가능하지만
위쪽배열을 확인하여 교차가 발생했을경우
위쪽배열의 교차발생위치의 아래배열에서는 ex(4~6)
4부터 시작해야해서 0이 아닌 strat위치를
찍어야 하기때문에 0이 아니라 strat를 적는다

 

 

5. 메인메소드에서 호출시 인풋값 예상

quick(data, 0, data.length - 1);

메서드 시그니처: 함수 3요소-> input,output,기능
int[]x1, intx2 | output X | 기능 : 퀵 정렬

*** output이 없는 이유는 객체는 힙과 스택관련 때문에
메소드를 사용하여 값 변경을 하면 주소값자체에서 변경하는 것이기에
굳이 output으로 배열값을 가져올필요가없다
이것을 경험으로 다음부턴 배열을 이용한 메소드에선 output X 한다고
외워나가면서 해야할 것 이다

배열값과 인트값2개를 넣는 이유는 배열을 이용할 함수이고

start값과 end값을 이용할 것이기때문