삽입/선택/버블 정렬 정리했습니다!

[khyunjiee]

삽입 정렬

삽입 정렬(insertion sort)는 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.

k 번째 반복 후 결과 배열은, 앞쪽 k+1 항목이 정렬된 상태이다.

배열이 길어질수록 효율이 떨어지지만, 구현이 간단한 정렬 방법이다.

과정

• 31 25 12 22 11
• 31 [25] 12 22 11
• 25 31 [12] 22 11
• 12 25 31 [22] 11
• 12 22 25 31 [11]
• 11 12 22 25 31

코드

void insertionSort(int[] arr) {
	for (int i = 1; i < arr.length; i++) {
		int temp = arr[i];
		int loc = i - 1;
		while ((loc >= 0) && (arr[loc] > temp)) {
			arr[loc+1] = arr[loc];
			loc--;
		}
		arr[loc+1] = temp;
	}
}

시간복잡도

n개의 데이터가 있을 때, 최악의 경우 (n*(n-1))/2 번 비교하므로 시간복잡도는 O(n^2)

선택 정렬

선택 정렬(selection sort)은 제자리 정렬 알고리즘의 하나로, 다음과 같은 순서로 이루어진다.

1. 주어진 리스트 중에 최소값을 찾음
2. 그 값을 맨 앞에 위치한 값과 교체
3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체

선택 정렬은 알고리즘이 단순하며 사용할 수 있는 메모리가 제한적인 경우에 사용시 성능 상의 이점이 있다.

과정

• 9 1 6 8 4 3 2 [0]
• 0 [1] 6 8 4 3 2 9
• 0 1 6 8 4 3 [2] 9
• 0 1 2 8 4 [3] 6 9
• 0 1 2 3 [4] 8 6 9
• 0 1 2 3 4 8 [6] 9
• 0 1 2 3 4 6 [8] 9

코드

void selectionSort(int[] arr) {
	int indexMin, temp;

	for (int i = 0; i < arr.length-1; i++) {
		indexMin = i;
		for (int j = i+1; j < arr.length; j++) {
			if (arr[j] < arr[indexMin]) indexMin = j;
		}
		temp = arr[indexMin];
		arr[indexMin] = arr[i];
		arr[i] = temp;
	}
}

시간복잡도

최선, 평균, 최악의 경우에서 선택 정렬에 소요되는 비교 회수는 (n*(n-1))/2 이므로 O(n^2) 이다.

#버블 정렬

버블 정렬(bubble sort)은 두 인접한 원소를 검사하여 정렬하는 방법이다.

상당히 느리지만 코드가 단순하기 때문에 자주 사용된다.

양방향으로 번갈아 수행하면 칵테일 정렬이 된다.

과정

• [55] [07] 78 12 42
• 07 [55] [78] 12 42 → 처음 패스
• 07 55 [78] [12] 42
• 07 55 12 [78] [42]
• 07 55 12 42 78
• [07] [55] 12 42 78 → 두번째 패스
• 07 [55] [12] 42 78
• 07 12 [55] [42] 78
• 07 12 42 [55] [78]
• [07] [12] 42 55 78 → 세번째 패스
• 07 [12] [42] 55 78 → 네번째 패스
• 07 12 [42] [55] 78 → 다섯번째 패스
• 07 12 42 55 78 → 정렬 완료

코드

void bubleSort(int[] arr) {
	int temp = 0;
	for (int i = 0; i < arr.length-1; i++) {
		for (int j = 1; j < arr.length-i; j++) {
			if (arr[j] < arr[j-1]) {
				temp = arr[j-1];
				arr[j-1] = arr[j];
				arr[j] = temp;
			}
		}
	}
}

시간복잡도

정렬의 여부와 상관없이 모든 배열의 요소를 계속 비교하기 때문에 O(n^2) 의 시간 복잡도를 갖는다.