[자바] 단순 선택 정렬과 단순 삽입 정렬

단순 선택 정렬

단순 선택 정렬이란 배열중 가장 작은 요소를 선택해 알맞은 위치로 옮겨서 정렬하는 단순한 알고리즘입니다.

아래의 배열에서 가장 작은 요소인 1을 선택해 첫 번째 위치인 6과 교환합니다.

그다음 작은 요소인 4를 선택해 두 번째 위치는 5와 교환합니다.

1. 아직 정렬하지 않은 요소중에서 가장 작은 값을 선택합니다.
2. 선택한 가장 작은 값과 아직 정렬하지 않은 부분의 첫 번째 위치의 요소와 교환합니다.

단순 선택 정렬은 위와 같은 작업을 N-1회 반복하여 정렬하는 알고리즘입니다.

 

단순 선택 정렬을 코드로 구현해보겠습니다.

package selectionsort;

public class selectionSort {
	
	static void swap(int[] a, int idx1, int idx2) {
		int temp = a[idx1];
		a[idx1] = a[idx2];
		a[idx2] = temp;
	}
	
	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);
		}
	}
}

작업을 N - 1회 반복하여 가장 작은 요소를 셀렉트하여 첫 번째 요소와 교환하는 아주 단순한 정렬 알고리즘입니다.

 

 

단순 삽입 정렬

단순 삽입 정렬이란 선택한 요소를 알맞은 위치에 삽입하는 작업을 반복하는 알고리즘입니다.

단순 선택 정렬과 비슷하게 보일 수 있지만 단순 삽입 정렬은 차례대로 요소를 선택하여 앞쪽에 적절한 위치에 삽입한다는 점이 다릅니다. 아래의 그림을 참고해주세요.

단순 삽입 정렬은 단순 선택 정렬보다는 조금 더 복잡합니다.

그 이유는 요소를 선택하여 알맞은 위치에 옮길 때, 알맞은 위치를 찾기 위해서 아래의 두 조건을 만족할 때까지 인접한 요소들과 교환해나가는 작업을 반복해야 합니다.

1. 정렬된 열의 왼쪽 끝에 도달
2. 작거나 같은 요소를 발견

작거나 같은 요소를 오름차순 기준입니다. 내림차순이라면 크거나 같은 요소가 되겠습니다.

 

위의 내용을 바탕으로 코드를 구현해보겠습니다.

package insertionsort;

public class insertionSort {
	static void swap(int[] a, int idx1, int idx2) {
		int temp = a[idx1];
		a[idx1] = a[idx2];
		a[idx2] = temp;
	}

	static void insertionSort(int[] a, int N) {
		for (int i = 1; i < N; i++) { // 두번째 요소부터 시작
			int j;
			int temp = a[i];
			for (j = i; j > 0 && a[j - 1] > temp; j--) {
				a[j] = a[j - 1]; // 왼족의 요소와 교환
			}
			a[j] = temp;
		}
	}
}

두 번째 요소부터 작업을 시작하여 반복문이 만족하지 않을 때까지 왼쪽의 요소와 교환합니다.

첫 번째 조건인 j > 0이 의미하는 것은 정렬된 열의 왼쪽 끝에 도달하지 않았다는 것이고

두 번째 조건인 a [j - 1] > temp는 작거나 같은 요소를 발견하지 못했다는 것입니다.

 

그리고 조건이 만족하지 않았을 때 교환 작업이 종료되므로 위에서 설명해드린 두 조건을 만족하는 것입니다.