[Java] 정렬 (2)

Do it! 자료구조와 함께 배우는 알고리즘 입문 읽고 정리

https://devhooney.tistory.com/35

[Java] 정렬 (1)

이 글에 이어서...

 

6-5 셸 정렬

셸 정렬

- 셸 정렬은 단순 삽입 정렬의 장점을 살리고, 단점을 보완한 정렬 알고리즘

class ShellSort {
	// 셸 정렬
    static void sheelSort(int[] a, int n) {
    	for (int h = n/2; h > 0; h/=2) {
        	for (int i = h; i < n; i++) {
            	int j;
                int tmp = a[j];
                for (j = i-h; j>= 0 && a[j] > tmp; j -=h) {
                	a[j+h] = a[j];
                }
                a[j+h] = tmp;
            }
        }
    }
    
    public static void main(String[] args) {
   	    Scanner sc = new Scanner(System.in);
        int nx = sc.nextInt();
        int[] x = new int[nx];
        
        for (int i = 0; i < nx; i++) {
        	x[i] = sc.nextInt();
        }
        
        shellSort(x, nx); // 배열 x를 셸 정렬
   	}
}

 

6-6 퀵 정렬

- 퀵 정렬은 가장 빠른 정렬 알고리즘 중의 하나로 널리 사용되고 있음.

- 퀵정렬은 배열을 두 그룹으로 나누고 시작

pl 5

7

1

4

x 6

2

3

9

pr 8

- 배열을 두 그룹으로 나누는 순서

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

(2) a[pr] <= x가 성립하는 요소를 찾을 때까지 pr을 왼쪽으로 스캔

 

- pr과 pl이 교차하면 배열은 두 그룹으로 나뉜다.

(1) 피벗 이하의 그룹 : a[0], ..., a[pl-1]

(2) 피벗 이상의 그룹 : a[pr+1], ..., a[n-1]

 

- 그룹을 나누는 과정이 끝난 다음 pl > pr+1인 경우 피벗과 일치하는 값을 갖는 그룹이 생길 수 있다.

피벗과 일치하는 값을 가지는 그룹 : a[pr+1], ..., a[pl-1]

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 partition(int[] a, int n) {
    	int pl = 0; // 왼쪽 커서
        int pr = n-1; // 오른쪽 커서
        int x = a[n/2]; // 피벗(가운데 위치의 값)
        
        do {
        	while (a[pl] < x) pl++;
            while (a[pr] > x) pr--;
            if (pl <= pr) swap(a, pl++, pr--);
        } while (pl <= pr);
    }
    
    public static void main(String[] args) {
   	    Scanner sc = new Scanner(System.in);
        int nx = sc.nextInt();
        int[] x = new int[nx];
        
        for (int i = 0; i < nx; i++) {
        	x[i] = sc.nextInt();
        }
        
        partition(x, nx); // 배열 x를 나눈다.
   	}
}

- 위 코드는 배열을 나누는 과정

- 아래는 재귀호출을 이용한 퀵 정렬

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[([l+pr) / 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) quickSort(a, left, pr);
        if (pl < right) quickSort(a, pl, right);
    }
    
        public static void main(String[] args) {
   	    Scanner sc = new Scanner(System.in);
            int nx = sc.nextInt();
            int[] x = new int[nx];

            for (int i = 0; i < nx; i++) {
                x[i] = sc.nextInt();
            }

            quickSort(x, nx); // 배열 x를 나눈다.
   	}
}