정렬 알고리즘은 n개의 숫자가 입력으로 주어졌을 때, 이를 사용자가 지정한 기준에 맞게 정렬하여 출력하는 알고리즘이다.
예를 들어 n개의 숫자가 저장되어있는 배열을, 오름차순의 조건으로 작성하여 입력하면 오름차순으로 정렬된 배열을 출력으로 구할 수 있다.
정렬 알고리즘은 정말 다양한데, 이에 따라 각각의 수행시간도 천차 만별이다.
1. 버블 정렬(Bubble Sort)
두 인접한 데이터를 비교해서, 앞에 있는 데이터가 뒤에 있는 데이터보다 크면, 자리를 바꾸는 방식이다.
[ 코드 ]
static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
boolean swap = false;
for (int j = 0; j < n - i - 1; j++) {
// 현재 원소와 다음 원소를 비교하여 순서가 잘못되었다면 교환
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swap = true;
}
}
if(!swap) {
break;
}
}
}
시간 복잡도
코드에서 보이는 것처럼 배열의 크기 n * n번 반복하므로 시간 복잡도는 O(n^2) 이다.
2. 삽입 정렬(Insertion Sort)
- 삽입 정렬은 두 번째 인덱스부터 시작
- 해당 인덱스(key 값) 앞에 있는 데이터(B)부터 비교해서 key 값이 더 작으면, B값을 뒤 인덱스로 복사
- 이를 key 값이 더 큰 데이터를 만날때까지 반복, 그리고 큰 데이터를 만난 위치 바로 뒤에 key 값을 이동
[ 코드 ]
static void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
// key보다 큰 원소들을 오른쪽으로 이동
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
// key를 올바른 위치에 삽입
arr[j + 1] = key;
}
}
시간 복잡도
최악의 경우 배열의 크기 n * n번 반복하므로 시간 복잡도는 O(n^2) 이다.
3. 선택 정렬(Selection Sort)
다음과 같은 순서를 반복하며 정렬하는 알고리즘
1. 주어진 데이터 중, 최소값을 찾음
2. 해당 최소값을 데이터 맨 앞에 위치한 값과 교체함
3. 맨 앞의 위치를 뺀 나머지 데이터를 동일한 방법으로 반복함
[ 코드 ]
static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
// 현재 인덱스를 최소값으로 가정
int minIndex = i;
// 현재 인덱스 이후의 원소들 중에서 최소값 찾기
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// 최소값과 현재 위치의 원소 교환
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
시간 복잡도
최악의 경우 배열의 크기 n * n번 반복하므로 시간 복잡도는 O(n^2) 이다.
