퀵정렬

1. 퀵정렬

퀵정렬은 일반적으로 사용되고 있는 아주 빠른 정렬 알고리즘이다.

퀵정렬은 각 그룹에 대해 피벗 설정과 그룹 나눔을 반복하며 모든 그룹 1명이 되면 정렬을 마친다.

2. 배열을 두 그룹으로 나누기 (피벗을 구하고 그룹을 나누는 과정)

그룹을 나누려면 피벗 이하의 요소를 배열 왼쪽으로, 피벗 이상의요소를 오른쪽으로 옮겨야 한다.

1. a[pl] >= x 가 성립하는 요소를 찾을때까지 pl을 오른쪽으로 스캔한다.

2. a[pr] <= x가 성립하는 요소를 찾을떄까지 pr을 오른쪽으로 스캔한다.

이 과정을 통해 pl과 pr이 멈추게 되고 pl이 위치한 지점은 피벗값 이상의 요소가 있는 지점이고

pr이 위치한 지점은 피벗값 이하의 요소가 있는 지점이다.

왼쪽(pl)과 오른쪽(pr) 커서가 가리키는 요소 a[pl]과 a[pr]의 값을 교환한다.

그러면 피하이하의 값은 왼쪽으로 이동하고 피벗이상의 값은 오른쪽으로 이동한다.

교환 후 다시 스캔하면 같이 멈추게된다.

교환 후 다시 스캔하면 두 커서가 교차하게 된다.

pl 과 pr이 교차하면 그룹을 나누는 과정이 끝나고 배열은 두그룹으로 나눠진다.

3. 피벗을 구하고 그룹을 나누는 소스코드

package myTest4;
 
import java.util.Scanner;
 
public class Partition {
    
    // 배열 요소 a[idx1] 과 a[idx2] 의 값을 바꾼다.
    static void swap(int[] a, int idx1, int idx2){
        int t = a[idx1];
        a[idx1] = a[idx2];
        a[idx2] = t;
    }
    
    // 배열을 나눈다.
    static void partitionArray(int[] a, int n){
        int pl = 0;            // 왼쪽커서
        int pr = n-1;         // 오른쪽커서
        int x = a[n/2]; // 피벗(가운데 위치 값)
        // x = a[5]
        // a[0] 
        do{
            while(a[pl] < x) pl++;
            while(a[pr] > x) pr--;
            if(pl <= pr){
                swap(a, pl++, pr--);
            }
        }while(pl <= pr);
        
        System.out.println("피벗의 값은 " + x + "입니다.");
        
        System.out.println("피벗 이하의 그룹");
        for(int i=0; i<= pl-1; i++){
            System.out.print(a[i] + " ");        // a[0] ~ a[pl-1]
        }
        System.out.println();
        
        if(pl > pr+ 1){
            System.out.println("피벗과 일치하는 그룹");
            for(int i= pr+1; i<=pl-1; i++){    // a[pr+1] ~ a[pl-1]
                System.out.print(a[i] + " ");
            }
            System.out.println();
        }
        
        System.out.println("피벗 이상의 그룹");
        for(int i=pr+1; i<n; i++){        // a[pr+1] ~ a[n-1]
            System.out.print(a[i] + " ");
        }
        System.out.println();
    }
    
    public static void main(String[] args){
        Scanner stdIn = new Scanner(System.in);
        System.out.println("배열을 나눕니다.");
        System.out.print("배열의 길이 : ");
        int nx = stdIn.nextInt();
        int[] x = new int[nx];
        
        for(int i=0; i<nx; i++){
            System.out.print("x["+i+"] : ");
            x[i] = stdIn.nextInt();
        }
        partitionArray(x, nx);            // 배열 x를 나눕니다.
    }
}

결과

배열을 나눕니다.
배열의 길이 : 9
x[0] : 5
x[1] : 7
x[2] : 1
x[3] : 4
x[4] : 6
x[5] : 2
x[6] : 3
x[7] : 9
x[8] : 8
피벗의 값은 6입니다.
피벗 이하의 그룹
5 3 1 4 2 
피벗 이상의 그룹
6 7 9 8 

4. 퀵정렬 코드 ( 재귀, 비재귀 )

package myTest4;
 
import java.util.Scanner;
 
import myTest1.IntStack;
 
public class QuickSort {
    
    // 배열 요소 a[idx1]과 a[idx2]의 값을 바꿉니다.
    static void swap(int[] a, int idx1, int idx2){
        int t = a[idx1]; 
        a[idx1] = a[idx2];
        a[idx2] = t;
    }
    
    // 재귀 사용 퀵정렬
    static void quickSort(int[] a, int left, int right){
        int pl = left;                    // 왼쪽 커서
        int pr = right;                // 오른쪽 커서
        int x = a[(pl+pr ) /2];    //피벗
        
        System.out.printf("a[%d]~a[%d] : {",left, right);
        for(int i = left; i<right; i++){
            System.out.printf("%d, ", a[i]);
        }
        System.out.printf("%d}\n", a[right]);
        
        do{
            while(a[pl] < x) pl++;
            while(a[pr] > x) pr--;
            if(pl <= pr){
                swap(a, pl++, pr--);
            }
        }while(pl <= pr);
        
        if(left < pr) quickSort(a, left, pr);
        if( pl< right) quickSort(a, pl, right);
        
    }
    
    // 비재귀 사용 퀵정렬
    static void notRecurQuickSort(int[] a, int left, int right){
        IntStack lstack = new IntStack(right - left + 1);
        IntStack rstack = new IntStack(right - left + 1);
        
        lstack.push(left);
        rstack.push(right);
        
        while(lstack.isEmpty() != true){
            int pl = left = lstack.pop();        // 왼쪽 커서
            int pr = right = rstack.pop();     // 오른쪽 커서
            int x = a[(left + right) / 2];        // 피벗
            
            do{
                while(a[pl] < x) pl++;
                while(a[pr] > x) pr--;
                if(pl <= pr){
                    swap(a, pl++, pr--);
                }
            }while(pl <= pr);
            
            if(left < pr){
                lstack.push(left);        // 왼쪽 그룹 범위의
                rstack.push(pr);        // 인덱스를 푸시합니다.
            }
            if(pl < right){
                lstack.push(pl);            // 오른쪽 그룹 범위의
                rstack.push(right);    // 인덱스를 푸시합니다.
            }    
        }
    }
    
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        System.out.println("퀵정렬");
        System.out.print("배열의 길이 : ");
        int nx = scanner.nextInt();
        int[] x = new int[nx];
        
        for(int i=0; i<nx; i++){
            System.out.print("x["+i+"] : ");
            x[i] = scanner.nextInt();
        }
        
        quickSort(x, 0, nx-1);            
//        notRecurQuickSort(x, 0, nx-1);
        System.out.println("오름차순으로 정렬했습니다.");
        for(int i=0; i<nx; i++){
            System.out.println("x["+i+"]=" + x[i]);
        }
    }
}

결과

퀵정렬
배열의 길이 : 9
x[0] : 5
x[1] : 8
x[2] : 4
x[3] : 2
x[4] : 6
x[5] : 1
x[6] : 3
x[7] : 9
x[8] : 7
a[0]~a[8] : {5, 8, 4, 2, 6, 1, 3, 9, 7}
a[0]~a[4] : {5, 3, 4, 2, 1}
a[0]~a[2] : {1, 3, 2}
a[0]~a[1] : {1, 2}
a[3]~a[4] : {4, 5}
a[5]~a[8] : {6, 8, 9, 7}
a[5]~a[6] : {6, 7}
a[7]~a[8] : {9, 8}
오름차순으로 정렬했습니다.
x[0]=1
x[1]=2
x[2]=3
x[3]=4
x[4]=5
x[5]=6
x[6]=7
x[7]=8
x[8]=9

퀵정렬에서 분할과정 출력을 통해 어떻게 분할 되는지 확인 할 수 있었다.