기본 정렬 알고리즘 - 선택정렬, 버블 정렬, 삽입 정렬

 

안녕하세요,

자바 프로그래밍 알고리즘 첫 포스팅으로 가장 기본이자 알고리즘의 시작이라고 할 수 있는 기본 알고리즘 3종 (선택/버블/삽입 정렬)에 관해서 정리하도록 하겠습니다. 알고리즘 시험이나 코딩 테스트에서는 해당 알고리즘을 그대로 이용해서 구현하는 식의 문제가 나올 가능성은 적겠지만, 기본 정렬 알고리즘을 완벽히 이해하고 구현할 수 있어야 다른 복잡하고 어려운 알고리즘 문제를 이해하고 해결하는데 큰 도움이 될 것입니다.

 

만약 아래와 같이 정렬이 되지 않은 배열 크기 N이 5인 int 배열이 있고, 해당 배열을 좌측부터 오름차순으로 정렬을 해야 한다고 가정을 하고 선택/버블/삽입 정렬을 이용하여 정렬을 하도록 하겠습니다.

{ 3, 5, 1, 2, 4 } -> { 1, 2, 3, 4, 5 }

 

1. 선택 정렬 (Selection Sort)

컴퓨터 프로그래밍을 이용해 정렬을 한다고 하면 아마 가장 이해하기 쉽게 구현할 수 있는 방법이 선택 정렬 일 것입니다. 선택 정렬은 가장 작은 수를 찾아서 앞으로 보내는 행동을 계속하는 것입니다. 

배열의 처음부터 끝까지 반복문을 통해 돌면서 가장 작은 수를 찾습니다. 그런 후 가장 작은 수를 배열의 맨 앞으로 보냅니다. 그다음 배열부터 끝까지 또 작은 수를 찾아 맨 앞으로 보내고, 배열이 끝날 때까지 위의 행위를 계속해서 정렬을 하는 것이 선택 정렬, Selection Sort입니다. 선택 정렬의 시간 복잡도는 배열의 길이 n을 n회 2중 반복문을 돌아야 하기 때문에 n^2, O(n^2)이라고 표기합니다.

 

선택 정렬을 애니메이션으로 간단히 만들어 봤는데요, 좀 허접하더라도 직접 만들어 보는 게 의미가 있는 것 같아서 직접 작성을 하였습니다:)

 

선택정렬

 

위의 애니메이션을 JAVA로 구현하면 아래와 같습니다.

 

 

import java.util.Arrays;

public class selectionSort {
	public static void main(String[] args) {
		int[] a = { 3, 5, 1, 2, 4 };
		int tempValue, tempJ = 0;
		for (int i = 0; i < a.length; i++) {  // 배열 처음부터 끝까지 반복 (i는 현재 위치)
			int min = Integer.MAX_VALUE;  // 제일 작은 수를 찾기 위해, min은 int의 최대 값으로 임시 세팅
			for (int j = i; j < a.length; j++) {
				if (a[j] < min) {  // 현재 위치부터 배열 마지막까지 반복문 돌면서 최소 값을 계속 찾음
					min = a[j];
					tempJ = j;
				}
			}
			tempValue = a[i]; // 찾은 최소값과 현재 위치의 값과 서로 바꿈
			a[i] = a[tempJ];
			a[tempJ] = tempValue;
		}
		System.out.println(Arrays.toString(a));
	}
}

 

 

2. 버블 정렬 (Bubble Sort)

버블정렬은 오름차순 정렬의 경우, 바로 오른쪽 옆에 있는 숫자와 크기를 비교해서 그 숫자가 크기가 작으면 서로 자리를 바꿔주면서 정렬을 합니다. 맨 처음 반복에서 가장 큰 수를 가장 오른쪽으로 보내게 되고, 다시 배열 시작부터 배열의 크기 - 1, n-1까지 다시 반복을 돌면서 옆의 수와 비교하면서 정렬을 계속하면서 그다음 작은 수를 그다음 오른쪽에 놓이게 됩니다. 이런 식으로 계속 반복을 돌게 되면서 정렬을 하게 됩니다. 버블 정렬의 시간 복잡도도 역시 배열의 길이 n을 n회 2중 반복문을 돌아야 하기 때문에 n^2, O(n^2)이 됩니다.

버블 정렬의 애니메이션 및 자바 코드는 아래와 같습니다.

 

버블정렬

 

import java.util.Arrays;

public class bubbleSort {
	public static void main(String[] args) {
		int[] a = { 3, 5, 1, 2, 4 };
		int tempValue;
		for (int i = 0; i < a.length; i++) {
			for (int j = 0; j < a.length - i - 1; j++) { // 0 ~ n, 0 ~ n-1 번 반복를 돌면서 바로 옆 숫자릴 비교
				if (a[j] > a[j + 1]) {  // 바로 오른쪽 숫자와 비교하여 크기가 클 경우, 서로 위치를 바꿈
					tempValue = a[j];
					a[j] = a[j + 1];
					a[j + 1] = tempValue;
				}
			}
		}
		System.out.println(Arrays.toString(a));
	}
}

 

3. 삽입 정렬 (Insertion Sort)

삽입 정렬은 숫자를 한 개 선택하고 선택된 숫자를 적절한 위치에 삽입하는 정렬 방법이다. 오름차순의 경우, 배열의 왼쪽에서 두 번째 숫자( 배열[1] )를 제일 먼저 선택한 후, 선택된 숫자의 왼쪽 숫자의 크기를 비교해서 숫자가 더 작다면 서로 위치를 바꿔줍니다. 그다음 한 칸 오른쪽 숫자를 선택한 후에 왼쪽 숫자들을 비교해서 정렬을 하게 되는데, 왼쪽 숫자들은 정렬이 되어 있는 상태이기 때문에 바로 왼쪽 옆 숫자 한 개씩 비교하면서 선택된 숫자보다 작은 숫자가 나올 때까지만 이동을 하면 됩니다. 나보다 작은 숫자를 찾으면 그 오른쪽 옆으로 삽입을 하는 식으로 모든 숫자를 다 선택해서 삽입할 때까지 동작을 합니다. 시간 복잡도는 배열의 상태에 따라 모두 숫자를 비교를 하고 위치를 바꿔야 할 Worst Case의 경우 n^2이 되고, Best Case의 경우 n번 만으로도 정렬이 가능합니다. 다만 시간 복잡도는 최악의 경우를 표기하기에 O(n^2)가 됩니다.

삽입 정렬의 애니메이션 및 자바 코드는 아래와 같습니다.

 

삽입 정렬

 

import java.util.Arrays;

public class insertionSort {

	public static void main(String[] args) {
		int[] a = { 3, 5, 1, 2, 4 };
		int tempValue, target;
		for (int i = 1; i < a.length; i++) {
			tempValue = a[i]; // 선택된 숫자를 임시 저장
			target = i - 1;  // 비교 대상의 위치
			while (target >= 0 && a[target] > tempValue) { // 왼쪽 끝까지 가거나, 자신보다 작은 수를 만나기 전까지 이동하면 삽입될 위치를 찾음
				a[target + 1] = a[target]; // 나보다 큰 수는 오른쪽으로 한칸 이동
				target--; // 그 다음 비교대상을 왼쪽으로 한 칸 이동
			}
			a[target + 1] = tempValue;  // 적정한 위치를 찾아 선택된 숫자를 삽입
		}
		System.out.println(Arrays.toString(a));
	}
}