버블 정렬은 가장 기본적인 알고리즘 중 하나로 인접한 모든 값을 비교해서 작은 값이 앞으로 이동하도록 교환하는 알고리즘이다. 모든 값을 비교하기 때문에 데이터가 많을수록 처리시간이 오래걸리는 단점이 있다.
public class BubbleSort {
public static void main(String[] args) {
int[] a = {10, 3, 1, 4, 2};
// 시작 위치를 하나씩 뒤로 하는 반복
for (int i = 0; i < a.length - 1; i++) {
// 시작 위치를 하나씩 앞으로 하는 반복
for (int j = a.length - 1; j > i; j--) {
// 만약 인접한 두 값 중 뒤쪽 값이 더 작다면 값 교환
if (a[j] < a[j - 1]) {
int temp = a[j];
a[j] = a[j - 1];
a[j - 1] = temp;
}
}
}
for (int i : a) {
System.out.print(i + " "); // 1 2 3 4 10
}
}
}
선택 정렬은 최솟값을 찾아 앞에서부터 차례대로 나열하는 알고리즘이다. 버블 정렬과 비슷하지만 최솟값을 찾고 나서 교환하기 때문에 교환 횟수가 적고 처리속도도 약간 빠르다.
public class SelectionSort {
public static void main(String[] args) {
int[] a = {10, 3, 1, 4, 2};
// 최솟값을 넣을 위치를 앞에서부터 차례대로 반복
for (int i = 0; i < a.length - 1; i++) {
// 1. 최솟값을 구하는 알고리즘
// 임시 최솟값과 위치
int min = a[i];
int k = i;
// 마지막 값까지 임시 최솟값과 비교
for (int j = i + 1; j < a.length; j++) {
// 만약 임시 최솟값보다 작은 최솟값을 찾았다면
// 최솟값과 위치 저장
if (min > a[j]) {
min = a[j];
k = j;
}
}
// 2. 교환 알고리즘
// 임시 최솟값과 최솟값 교환
int temp = a[i];
a[i] = a[k];
a[k] = temp;
}
for (int i : a) {
System.out.print(i + " ");
}
}
}
삽입 정렬은 데이터를 빼내 올바른 위치에 삽입하는 알고리즘으로 버블, 선택 정렬 중 가장 빠르다는 특징이 있다. 정렬되지 않은 부분에서 삽입할 값을 차례로 하나씩 꺼내서 정렬된 부분의 어느 곳에 삽입할지 조사하는 반복을 수행하며 정렬한다.
public class InsertSort {
public static void main(String[] args) {
int[] a = {10, 3, 1, 4, 2};
// 정렬되지 않은 부분에서 차례대로 하나씩 꺼내기 반복
for (int i = 1; i < a.length; i++) {
// 삽입할 값 임시로 temp에 저장
int temp = a[i];
// 삽입할 위치 변수 초기화
int ins = 0;
// 값을 어디에 삽입할지 뒤에서부터 차례대로 탐색
for (int j = i - 1; j >= 0; j--) {
// 만약 삽입할 값이 정렬되어 있는 부분의 값보다 작다면
if (a[j] > temp) {
// 해당 위치에 값을 삽입할 수 있도록 배열을 하나씩 뒤로 보냄
a[j + 1] = a[j];
// 만약 삽입할 값이 정렬되어 있는 부분의 값보다 크다면
} else {
// 삽입할 위치를 ins에 저장 후 반복 종료
ins = j + 1;
break;
}
}
// 밀어내는 처리 종료 후 끝난 위치에 값 삽입
a[ins] = temp;
}
for (int i : a) {
System.out.print(i + " ");
}
}
}
앞서 소개한 세 가지 알고리즘은 O(N^2)의 시간 복잡도를 가져 비효율적이다. 이번에 소개할 퀵 정렬은 가장 빠른 정렬 알고리즘으로 O(nlogn)을 갖는다.
public class QuickSort {
public static void main(String[] args) {
int[] a = {10, 3, 1, 9, 7, 6, 8, 2, 4, 5};
quickSort(a, 0, a.length - 1);
for (int i : a) {
System.out.print(i + " ");
}
}
public static void quickSort(int[] a, int start, int end) {
// 범위 한가운데에 있는 값을 피벗으로 선언
int pivot = a[(int) (start + end) / 2];
// 왼쪽 위치를 시작 위치로 선언
int left = start;
// 오른족 위치를 종료 위치로 선언
int right = end;
while (true) {
// 왼쪽 값이 피벗보다 작다면
while (a[left] < pivot) {
// 왼쪽을 오른쪽으로 한 칸 이동
left++;
}
// 오른쪽 값이 피벗보다 크다면
while (pivot < a[right]) {
// 오른쪽을 왼쪽으로 한 칸 이동
right--;
}
// 만약 왼쪽과 오른쪽이 만나면 반복종료
if (right <= left) {
break;
}
// 교환 알고리즘
// 왼쪽과 오른쪽이 만나지 않는다면 왼쪽 값과 오른쪽 값 교환
int temp = a[left];
a[left] = a[right];
a[right] = temp;
// 왼쪽을 오른쪽으로 한 칸 이동
left++;
// 오른쪽을 왼쪽으로 한 칸 이동
right--;
}
// 만약 왼쪽에 나눌 데이터가 있다면
if (start < left - 1) {
// 재귀
quickSort(a, start, left - 1);
}
// 만약 오른쪽에 나눌 데이터가 있다면
if (right + 1 < end) {
// 재귀
quickSort(a, right + 1, end);
}
}
}