6. 정렬 알고리즘 - 1
정렬이란?
이름, 학번, 키 등 핵심 항목(key)의 대소 관계에 따라 데이터 집합을 일정한 순서로 나열하는 작업을 말한다.
작은 데이터를 앞쪽에 놓으면 오름차순, 반대로 놓으면 내림차순 정렬이라고 부른다.
정렬 알고리즘의 안정성
예를 들어 점수와 학번이 있고 점수대로 정렬을 할 때, 키값(점수)이 같은 요소의 순서가 정렬 전후에도 유지되는 것을 정렬된 알고리즘 이라고 한다.
내부 정렬과 외부 정렬
- 내부 정렬 : 정렬할 모든 데이터를 하나의 배열에 저장할 수 있을 때에 사용하는 알고리즘
- 외부 정렬 : 정렬할 데이터가 너무 많아서 하나의 배열에 저장할 수 없을 때에 사용하는 알고리즘
※ 외부 정렬은 내부 정렬을 응용한 것으로, 외부 정렬을 구현하려면 작업을 위한 별도의 파일 등이 필요하고 알고리즘도 복잡하다.
정렬 알고리즘의 핵심 요소
정렬 알고리즘의 핵심 요소는 교환, 선택, 삽입이다. 대부분의 정렬 알고리즘은 이 3가지 요소를 응용한 것이다.
버블 정렬
정렬 중에 기본인 버블 정렬 일명 '단순 교환 정렬'이라고 불리는 정렬에 대해서 봐보겠다.
먼저 끝에 있는 두 요소 9와 8부터 시작을 한다. 이때 배열을 오름차순으로 정렬하고자 한다면 왼쪽 값이 오른쪽 값보다 작으면 된다. 9와 8을 비교했을 때 9보다 8이 더 작으므로 교환이 된다.
이런식으로 왼쪽 첫번째 인덱스까지 비교해 교환까지 하게 되면 끝이난다.
이로서 모든 정렬이 끝나려면 패스가 n - 1번 수행되어야 한다(for문 종료 조건) 그럼 이제 코드를 작성해 보겠다.
import java.util.Scanner;
public class Sorting {
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[i])
swap(a, j - 1, i);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("버블 정렬(버전 1)");
System.out.print("요솟수: ");
int num = sc.nextInt();
int[] x = new int[num];
for(int i = 0; i < num; i++) {
x[i] = sc.nextInt();
}
bubbleSort(x, num);
System.out.println("오름차순으로 정렬했습니다. ");
for(int i = 0; i < num; i++) {
System.out.println("x[" + i + "]: ");
}
}
}
알고리즘 개선하기 1
알고리즘에서 어느 순선 어떤 패스에서 요소의 교환 횟수가 0번이면 더 이상 정렬할 요소가 없다는 뜻이기 때문에 정렬 작업을 멈춘다.
이런 멈춤 방식을 도입하면 정렬을 마친 배열이나 정렬이 거의 다 된 상태의 배열에 대한 비교 연산이 많이 생략되어 짧은 시간에 정렬을 마칠 수 있다.
개선 알고리즘1
import java.util.Scanner;
public class Sorting {
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++) {
int exchange = 0;
for(int j = n - 1; j > i; j--) // 오른쪽 끝에서부터 비교
if(a[j - 1] > a[i]) {
swap(a, j - 1, i);
exchange++;
}
if(exchange == 0) break; // 더 이상 교환이 이뤄지지 않으므로 멈춤 지시
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("버블 정렬(버전 2)");
System.out.print("요솟수: ");
int num = sc.nextInt();
int[] x = new int[num];
for(int i = 0; i < num; i++) {
x[i] = sc.nextInt();
}
bubbleSort(x, num);
System.out.println("오름차순으로 정렬했습니다. ");
for(int i = 0; i < num; i++) {
System.out.println("x[" + i + "]: ");
}
}
}
알고리즘 개선하기 2
위 배열에서 첫 번째 패스(첫 번째 배열 정렬)이 지나면 아래와 같이 되는데 {1, 3, 4}는 정렬된 상태이므로 각 패스에서 비교, 교환을 하다가 어떤 시점 이후에 교환하지 않는다면 그보다 앞쪽의 요소는 이미 정렬을 마친 상태로 봐도 된다. 따라서 두 번째 패스는 첫 요소를 제외한 6개 요소가 아니라 4개 요소를 비교, 교환하면 더 빠르게 비교 교환하면서 정렬할 수 있게 된다.
개선된 알고리즘2
import java.util.Scanner;
public class Sorting {
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) {
int k = 0;
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;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("버블 정렬(버전 3)");
System.out.print("요솟수: ");
int num = sc.nextInt();
int[] x = new int[num];
for(int i = 0; i < num; i++) {
x[i] = sc.nextInt();
}
bubbleSort(x, num);
System.out.println("오름차순으로 정렬했습니다. ");
for(int i = 0; i < num; i++) {
System.out.println("x[" + i + "]: ");
}
}
}
단순 선택 정렬
가장 작은 요소를 맨 앞으로 이동하고, 두 번째 작은 요소는 맨 앞에서 두 번째로 이동하는 등의 작업을 반복하는 알고리즘
1번이 가장 작은 요소이므로 6과 교환
두 번째로는 4와 3을 교환하면 된다. 이런식으로 진행하면 결국 오름차순 정렬이 완성될 것이다.
알고리즘 코드
import java.util.Scanner;
public class Sorting {
static void swap(int[] a, int idx1, int idx2) {
int t = a[idx1];
a[idx1] = a[idx2];
a[idx2] = t;
}
static void selectionSrot(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);
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("단순 선택 정렬");
System.out.print("요솟수: ");
int num = sc.nextInt();
int[] x = new int[num];
for(int i = 0; i < num; i++) {
x[i] = sc.nextInt();
}
bubbleSort(x, num);
System.out.println("오름차순으로 정렬했습니다. ");
for(int i = 0; i < num; i++) {
System.out.println("x[" + i + "]: ");
}
}
}
위와 같은 단순 선택 정렬은 정렬한 후 두 같은 값의 순서가 뒤바뀌는 것을 알 수 있다. 따라서 안정적이지 않은 알고리즘이다.
단순 삽입 정렬
선택한 요소를 그보다 더 앞쪽의 알맞은 위치에 '삽입하는' 작업을 반복하여 정렬하는 알고리즘
이런식으로 오른쪽으로 이동하면서 알맞은 위치에 해당 요소를 넣는다.
왼쪽에 이웃한 요소가 선택한 요소보다 크면 그 값을 대입하고 앞으로 이동하면서 이 작업을 반복한다. 그러다가 선택한 값 이하의 요소를 만나면 그보다 앞쪽은 검사할 필요가 없으므로 해당 위치에 삽입할 값을 대입한다.
다시 말해 tmp에 a[i]를 대입하고 반복 제어용 변수 j에 i를 대입한 뒤 다음 두 조건 중 하나를 만족할 때까지 j를 1씩 감소시키면서 대입하는 작업을 반복한다.
- 정렬된 열의 왼쪽 끝에 도달한다.
- tmp보다 작거나 같은 key를 갖는 항목 a[j - 1]을 발견한다.
이때 드모르간 법칙을 적용하면 다음 두 조건이 모두 성립할 때까지 반복하게 된다.
알고리즘 코드
import java.util.Scanner;
public class Sorting {
static void insertionSort(int[] a, int n) {
for(int i = 1; i < n; i++) {
int j;
int tmp = a[i];
for(j = i; i > 0 && a[j - 1] > tmp; j--)
a[j] = a[j - 1];
a[j] = tmp;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("단순 삽입 정렬");
System.out.print("요솟수: ");
int num = sc.nextInt();
int[] x = new int[num];
for(int i = 0; i < num; i++) {
x[i] = sc.nextInt();
}
insertionSort(x, num);
System.out.println("오름차순으로 정렬했습니다. ");
for(int i = 0; i < num; i++) {
System.out.println("x[" + i + "]: ");
}
}
}
단순 정렬의 시간 복잡도
지금까지 언급한 세 가지 단순 정렬(버블, 선택, 삽입)의 시간 복잡도는 모두 O(n²)이다. 따라서 효율이 좋지 않다는 것을 알 수 있다.
다음에 공부할 정렬 알고리즘은 좀 더 효율적인 알고리즘이다.