[Java] 정렬 (1)

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

6-1 정렬

- 내부정렬과 외부정렬

1. 내부 정렬: 정렬할 모든 데이터를 하나의 배열에 저장할 수 있는 경우에 사용하는 알고리즘

2. 외부 정렬: 정렬할 데이터가 너무 많아서 하나의 배열에 저장할 수 없는 경우에 사용하는 알고리즘

 

- 정렬 알고리즘의 핵심 요소

정렬 알고리즘의 핵심 요소는 교환, 선택, 삽입

 

6-2 버블 정렬

- 버블 정렬

버블 정렬은 이웃한 두 요소의 대소 관계를 비교하여 교환을 반복하는 알고리즘

- 버블 정렬 과정

(n-1) + (n-2) + ... + 1 = n(n-1) /2

class BubbleSort {
	static void swap(int[] a, int idx1, int idx2) {
   		int t = a[idx1];
    	a[idx1] = a[idx2];
        a[idx2] = t;
   	}

	// 버블 정렬
    static void bubbleSort(int[] a, int n) {
    	for (int i = 0; i < n-1; i++) {
        	for (int j = n-1; j > i; j--) {
        		if (a[j-1] > a[j] swap(a, j-1, j);
            }
        }
    }
    
    // 버블 정렬 개선
    static void bubbleSort(int[] a, int n) {
    	int k = 0; // a[k]보다 앞쪽은 정렬을 마친 상태
        whie (k < n-1) {
        	int last = n-1; // 마지막으로 요소를 교환한 위치
            for (int j = n-1; j > k; k--) {
            	if (a[j-1] > a[j]) {
                	swap(a, j-1, j);
                    last = j;
                }
            }
        }
    }
    
    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();
        }
        
        bubbleSort(x, nx); // 배열을 버블 정렬한다.
    }
}

 

6-3 단순 선택 정렬

- 단순 선택 정렬

단순 선택 정렬은 가장 작은 요소부터 선택해 알맞은 위치로 옮겨서 순서대로 정렬하는 알고리즘

- 단순 선택 정렬 과정

1. 아직 정렬하지 않은 부분에서 가장 작은 키의 값(a[min])을 선택
2. a[min]과 아직 정렬하지 않은 부분의 첫 번째 요소를 교환

static void selectionSort(int[] a, int n) {
	for (int i = 0; i < n-1; i++) {
    	int min = i; // 아직 정렬되지 않은 부분에서 가장 작은 요소의 인덱스를 기록
        for (int j = i+1; j < n; j++) {
        	if (a[j] < a[min]) min = j;
        }
        swap(a, i, min); // 아직 정렬되지 않은 부분의 첫 요소와 가장 작은 요소를 교환
    }
}

단순 선택 알고리즘은 서로 떨어져 있는 요소를 교환하는 것이기 때문에 안정적이지 않다.

 

6-4 단순 삽입 정렬

- 단순 삽입 정렬

단순 삽입 정렬은 선택한 요소를 그보다 더 앞 쪽의 알맞은 위치에 삽입하는 작업을 반복하는 알고리즘

단순 선택 정렬과 비슷하게 보일 수 있지만 단순 선택 정렬은 값이 가장 작은 요소를 선택해 알맞은 위치로 옮긴다는 점이 다름

- 단순 삽입 정렬 과정

아직 정렬되지 않은 부분의 첫 번째 요소를 정렬된 부분의 알맞은 위치에 삽입

class InsertionSort {
	// 단순 삽입 정렬
    static void insertionSort(int[] a, int n) {
    	for (int i=0; i<n; i++) {
        	int j;
            int tmp = a[i];
            for (j=i; j>0 && a[j-1]>tmp; j--) {
            	a[j] = a[j-1];
            }
            a[j] = 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();
        }
        
        insertionSort(x, nx); // 배열 x를 단순 삽입 정렬
    }

}

- 단순 삽입 정렬의 특징

(1) 정렬을 마쳤거나 정렬을 마친 상태에 가까우면 정렬 속도가 매우 빨라진다.(장점)

(2) 삽입할 위치가 멀리 떨어져 있으면 이동해야 하는 횟수가 많아진다.(단점)