오늘은 데이터를 일정한 순서로 정렬하는 정렬 알고리즘을 알아보자.
📘 정렬이란?
정렬(sorting)은 핵심 항목(key)의 대소 관계에 따라 데이터 집합을 일정한 순서로 줄지어 늘어서도록 바꾸는 작업을 말한다.
오름차순 정렬(ascending order) : 키 값이 작은 데이터를 앞쪽에 놓는 것을 말함
내림차순 정렬(descending order) : 오름차순의 반대로 큰 데이터를 앞쪽에 놓는 것을 말함
정렬 알고리즘엔 대표적으로 8가지가 있다.
여기에는 안정된(stable) 알고리즘과 그렇지 않은 알고리즘으로 나눌 수 있다.
안정된 정렬이란 같은 값의 키를 가진 요소의 순서가 정렬 전후에도 유지되는 것을 말한다.
✏ 내부 정렬과 외부 정렬
- 내부 정렬(internal sorting) : 정렬할 모든 데이터를 하나의 배열에 저장할 수 있는 경우에 사용하는 알고리즘
- 외부 정렬(external sorting) : 정렬할 데이터가 너무 많아서 하나의 배열에 저장할 수 없는 경우에 사용하는 알고리즘
정렬 알고리즘의 핵심 요소는 교환, 선택, 삽입이며 대부분의 정렬 알고리즘은 이 세가지 요소를 응용한 것이다.
📘 버블 정렬
8가지의 정렬 중 첫 번째인 버블 정렬을 알아보자.
✏ 버블 정렬이란?
버블 정렬(bubble sort)이란 주어진 데이터를 오름차순으로 정렬시킬 때 버블 정렬 방법은 첫번째 값과 두 번째 값을 비교해 첫번째 값이 더 크면 교환 후 두번째와 세번째, 세번째와 네번째···. 끝까지 비교해가는 방식으로 n개의 데이터가 있다면 n-1번을 비교하게 된다.
이렇게 제일 마지막 값까지 한 바퀴 비교하는 과정을 통해 제일 큰 값이 제일 마지막에 정렬된다.
이제 다시 처음으로 돌아와 정렬된 제일 큰 값을 뺀 나머지 n-1 개에 대해 처음부터 똑같은 작업을 반복해 n-2번을 비교하게 되고 그 결과 그 다음 큰 값이 정렬된다.
✏ 버블 정렬 구현
버블 정렬 알고리즘을 프로그램으로 구현해보자.
for (int i = 0; i < n - 1; i++) {
// a[i], a[i + 1], ..., a[n - 1]에 대해
// 끝에서 부터 앞쪽으로 스캔하며 이웃하는 두 요소를 비교하고 교환
}변수 i의 값을 0부터 n - 2까지 1씩 증가하며 n - 1회의 패스를 수행하는 코드는 위처럼 구성하면 된다.
import java.util.Scanner;
public class bubbleSort {
// a[idx1]와 a[idx2]을 바꾸는 swap메서드
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);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("요솟수 : ");
int n = sc.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) {
System.out.print("a[" + i + "] : ");
a[i] = sc.nextInt();
}
bubbleSort(a, n);
for (int i = 0; i < n; i++)
System.out.println("x[" + i + "] = " + a[i]);
}
}위의 코드에서 bubbleSort 메서드를 알아보자면 비교하는 두 요소의 인덱스를 j - 1, j라 하고, 이때 두 요소(a[j - 1], a[j])의 값을 비교하여 앞쪽이 크면 교환을 한다. 그 이후의 비교, 교환 과정은 바로 앞쪽에서 수행해야 하므로 j의 값은 1씩 감소한다.
✏ 알고리즘 개선(1)
버블 정렬을 실행했을때 이미 진작에 정렬을 마친 상태가 되어 있음에도 계속해서 탐색을 할 경우가 생길 수 있다.
그렇게 되면 이미 정렬을 마친 상태의 이후에 패스에서는 요소 교환을 하지 않기 때문에 이 부분을 수정한다면 비교 연산이 많이 생략되어 짧은 시간에 마칠 수 있을 것이다.
// 버블 정렬 (알고리즘 개선(1))
static void bubbleSort(int[] a, int n) {
for (int i = 0; i < n - 1; i++) {
int count = 0; // 패스의 교환 횟수를 기록
for (int j = n - 1; j > i; j--) // * 패스
if (a[j - 1] > a[j]) {
swap(a, j - 1, j);
count++;
} // * 패스
if (count == 0) break; // 교환이 이루어지지 않으면 종료
}
}위에서 고친 메서드는 어떤 패스에서 요소의 교환 횟수가 0이면 더 이상 정렬할 요소가 없다는 뜻이기 때문에 정렬 작업을 멈추게 된다.
이런 방식으로 만약 첫번째 패스에서 교환 횟수가 0이라면 첫 번째 패스 이후의 모든 패스는 정렬 작없을 멈춘다.
✏ 알고리즘 개선(2)
하나 더 생각을 해보자.
각각의 패스에서 비교, 교환을 하다가 어떤 시점 이후에 교환이 수행되지 않는다면 그보다 앞쪽의 요소는 이미 정렬을 마친 상태라고 생각해도 좋다.
이 방식으로 개선을 해보자면 아래와 같이 메서드를 수정할 수 있다.
// 버블 정렬 (알고리즘 개선(2))
static void bubbleSort(int[] a, int n) {
int k = 0; // a[k]보다 앞쪽은 정렬을 마친 상태
while (k < n - 1) {
int last = n - 1; // 마지막으로 요소를 교환한 위치
for (int j = n - 1; j > k; j--) // * 패스
if (a[j - 1] > a[j]) {
swap(a, j - 1, j);
last = j;
} // * 패스
k = last;
}
}last는 각 패스에서 마지막으로 교환한 두 요소 가운데 오른쪽 요소(a[j])의 인덱스를 저장하기 위한 변수이다.
교환을 수행할 때마다 오른쪽 요소의 인덱스 값을 last에 저장한다.
하나의 패스를 마쳤을 때 last 값을 k에 대입하여 다음에 수행할 패스의 범위를 제한한다.
그러면 다음 패스에서 마지막으로 비교할 두 요소는 a[k]와 a[k + 1]이 된다.
이때 bubbleSort메서드의 시작 부분에서 k 값을 0으로 초기화하는 이유는 첫 번째 패스에서는 모든 요소를 검사해야 하기 때문이다.
버블 정렬의 시간 복잡도 : O(n^2)
