후라이
[정렬 알고리즘] 선택 정렬, 버블 정렬 그리고 삽입 정렬에 대하여 본문
1. 알고리즘 개요
정렬은 말 그대로 n개의 원소를 순서대로 배열하는 것입니다.
정렬 알고리즘에는 선택, 버블, 삽입, 병합, 퀵, 기수 등 정말 많은 알고리즘이 존재하며
이번 게시글에서는 시간복잡도 O(n^2)의 시간이 소요되는 기본적인 정렬 알고리즘에 대해 알아봅시다.
2. 선택 정렬 알고리즘 (Selection Sort)
선택 정렬 알고리즘은 가장 쉽게 접근할 수 있는 알고리즘입니다.
우선 배열 A[1...n]에서 가장 큰 원소를 찾아 이 원소와 배열 끝자리에 있는 A[n]과 자리를 바꿉니다.
맨 뒷자리가 바로 가장 큰 수가 되기 때문에 이 원소는 신경 쓰지 않게 되면서 끝자리인 last는 1씩 줄어듭니다.
다시 A[1..n-1] 배열에서 가장 큰 수 를 찾아, 또 배열의 끝자리에 있는 A[n-1]과 자리를 바꿉니다.
selectionSort(A[], n) {
for last <- n downto 2 |
A[1...last] 중 가장 큰 수 A[k]를 찾는다;
A[k] <-> A[last];
}
선택 정렬 알고리즘에서 n이 1이라면 for문을 거치지 않기 때문에 당연히 아무 일도 하지 않고 정렬을 끝냅니다.
물론, 가장 작은 원소를 찾아 이 원소와 배열 첫번째 자리에 있는 A[0]과 자리를 바꾸는 선택 정렬도 가능하며, 시간복잡도 또한 동일합니다.
선택 정렬의 수행시간은 모든 경우에 O(n^2)이다.
for문이 n-1번 반복되며, 자리 교환은 상수 시간이 소요된다. 그런데 가장 큰 수를 찾는 작업은 부분 배열의 크기에 비례하므로(크기가 k인 배열에서 가장 큰 수 찾기 -> k-1번) 이 과정이 for 루프에서 n부터 시작해서 2까지 감소하게 된다.
(n-1) + (n-2) + ... + 2 + 1 = n(n-1) / 2
import java.io.*;
import java.util.*;
public class Main {
public static int [] select_sort(int [] array) {
int len = array.length;
for(int i=0;i<len;i++) {
int index = i;
for(int j=i+1;j<len;j++) {
if(array[j]<array[index]) {
index = j;
}
}
if(index!=i) {
int temp = array[i];
array[i] = array[index];
array[index] = temp;
}
}
return array;
}
public static void main(String[] args) {
int [] arrays = {1,3,4,2,7,5,8,6,9};
for(int i : select_sort(arrays)) {
System.out.print(i+" ");
}
}
}
3. 버블 정렬 (Bubble Sort)
선택 정렬과 비슷하게 "제일 큰 원소를 끝자리로 옮긴다"의 풀이법 입니다.
다만, 탐색 과정에서 맨 왼쪽 즉 가장 첫번째 원소부터 시작해서 바로 옆에 있는 두번째 원소와의 비교를 통해 더 큰 수를 오른편으로 옮기게 됩니다. 그 다음에는 두번째 원소와 세번째 원소끼리 비교, 그 다음에는 세번째 원소와 네번째 원소끼리 비교 ... 계속 반복된 비교를 통해 결과적으로 내림차순된 배열로 정렬되게 됩니다.
bubbleSort(A[], n) {
for last <- n downto2
for i <- 1 to last-1
if(A[i] > A[i+1]) then A[i] <-> A[i+1];
}
버블 정렬의 수행시간은 O(n^2)이다.
첫번째 for문에서 n-1번 순환한 후 두번째 for문에서 last-1번 순환하게 된다.
last는 n에서 2까지 1씩 감소하고 2번째 for문에서 (n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2
import java.io.*;
import java.util.*;
public class Main {
public static int[] bubble_sort(int [] array) {
int len = array.length;
for(int i=0;i<len;i++) {
for(int j=0;j<len-1;j++) {
if(array[j]>array[j+1]) {
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
return array;
}
public static void main(String[] args) {
int [] arrays = {1,3,4,2,7,5,8,6,9};
for(int i : bubble_sort(arrays)) {
System.out.print(i+" ");
}
}
}
4. 삽입 정렬(Insertion Sort)
이미 정렬되어 있는 i개짜리 배열에 하나의 원소를 더 더하여 정렬된 i+1개짜리 배열을 만드는 과정을 반복합니다.
선택 정렬과 버블 정렬이 n개짜리 배열에서 시작하여 그 크기를 하나씩 줄이는 데 반해, 삽입 정렬은 한 개짜리 배열에서 시작해 그 크기를 하나씩 늘려가게 됩니다.
InsertionSort(A[], n) {
for i <-2 to n
A[1...i]의 적합한 자리에 A[i]를 삽입한다.
}
위의 의사코드에서 for 루프는 문제의 크기를 하나씩 키워가는 역할을 합니다.
이 알고리즘에서 A[i]에 관심을 두는 시점, 즉 A[1...i]의 적합한 자리에 A[i]를 삽입하는 작업을 수행하기 직전 시점에
A[1...i-1]은 항상 정렬이 되어있습니다.
삽입을 수행하고 나면 A[i]까지는 정렬이 이루어져있습니다. 이미 정렬된 A[1...i-1]과 원소 A[i]를 받아 정렬된 배열 A[1...i]를 만들게 되는 것입니다.
삽입 정렬의 수행시간은 O(n^2)이다.
for루프는 n-1번 순환한다. 그러나 매 for루프에서 최대 i-1번 순환한다. 운이 나쁘면 A[i]가 A[1] 자리에 들어가게 되어 i-1번의 순환이 필요하게 된 것이다. 운이 좋으면 A[i]가 제자리에 그대로 있게 되어 한번도 순환하지 않을 수도 있다.
최악의 경우 수행시간은 1+2+...+(n-1) = n(n-1)/2이므로 O(n^2)이다.
삽입 정렬의 경우 비효율적인 정렬 알고리즘군에 속하지만, 배열이 거의 정렬 되어 있는 상태로 입력되는 경우에는 수행시간 O(n)으로 가장 매력적인 알고리즘이 됩니다:)
import java.io.*;
import java.util.*;
public class Main {
public static int[] insertion_sort(int [] array) {
int len = array.length;
for(int i=1;i<len;i++) {
int value = array[i]; // array[1]
int j =i-1; //j=0;
while(j>=0 && array[j]>value) {
array[j+1] = array[j];
j--;
}
array[j+1] = value;
}
return array;
}
public static void main(String[] args) {
int [] arrays = {1,3,4,2,7,5,8,6,9};
for(int i : insertion_sort(arrays)) {
System.out.print(i+" ");
}
}
}