선택정렬
- 처리되지 않은 데이터 중 가장 작은 데이터를 선택해 맨 앞 데이터와 바꾸는 것.
- 가장 작은 수를 찾기 위해 매번 N번의 순회
- O(N2) ← N+(N-1)+….+2 = (N2+N-2)/2
private static void selectSort(int[] w) {
// 정렬 시작지점
for (int i = 0; i < w.length - 1; i++) {
int minIdx = i;
// 범위 내 최저값 찾기
for (int j = i + 1; j < w.length; j++) {
if (w[minIdx] > w[j]) {
minIdx = j;
}
}
swap(i, minIdx, w);
}
}
삽입 정렬
- 처리되지 않은 데이터를 하나씩 골라 앞 수와 비교해 바꿔가며 적절한 위치에 삽입
- 평균 시간복잡도: O(N2)
- 기존 배열이 거의 정렬되어 있을수록 빠르게 동작 ⇒ 최선의 경우 O(N)
private static void insertSort(int[] w) {
// 정렬 대상 구간 => 첫 인덱스는 정렬된 것으로 보고 인덱스 1부터 시작
for (int i = 1; i < w.length - 1; i++) {
// 정렬 대상 원소를 정렬된 구간의 수와 비교하며 삽입
for (int j = i + 1; j > 0; j--) {
// 나보다 작은 원소를 만날 때까지 스왑
if (w[j] < w[j - 1]) {
swap(j, j - 1, w);
} else
break;
}
}
}
버블정렬
- 인접한 두 원소를 검사하며 정렬하는 알고리즘
- 1회전 시 가장 마지막 인덱스에 가장 큰 수가 배치되고, 회전을 거듭할수록 뒤쪽부터 정렬되는 방식
- 평균 시간복잡도:O(N2)
장점
- 구현이 매우 간단하다.
단점
- 위치 교환 과정이 많아 비효율
- 하나의 요소가 가장 왼쪽에서 가장 오른쪽으로 이동하기 위해서는 배열에서 모든 다른 요소들과 교환되어야 한다.
- 특히 특정 요소가 최종 정렬 위치에 이미 있는 경우라도 교환되는 일이 일어난다.
private static void bubbleSort(int[] w) {
// 뒤쪽부터 정렬됨 -> 정렬 완료된 부분 직전까지만 정렬하도록 제한
for (int i = w.length - 1; i > 0; i--) {
for (int j = 0; j < i; j++) {
if (w[j] > w[j + 1]) {
swap(j, j + 1, w);
}
}
}
}
퀵 정렬
- 기준 데이터를 설정하고 그 기준보다 큰 데이터와 자근데이터의 위치를 바꾸는 방법
- 병합정렬과 더불어 대부분 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘
- 기본 방식은 첫 데이터를 기준데이터(Pivot)로 설정함
- O(N logN)
- 최악의 경우 O(N2) → 이미 정렬된 경우
private static void quickSort(int[] w, int start, int end) {
if (start >= end) {
return;
}
int pivot = w[start];
int l = start + 1;
int r = end;
while (l <= r) {
// 왼쪽부터 나보다 큰거 찾기
while (l <= end && w[l] <= pivot) {
l += 1;
}
// 오른쪽부터 나보다 작은거 찾기
while (r > start && w[r] >= pivot) {
r -= 1;
}
// l, r 교차하는 순간 피봇과 작은수 위치 스왑
if (l > r) {
swap(start, r, w);
// 교차하지 않으면 l, r만 스왑
} else
swap(l, r, w);
}
quickSort(w, start, r - 1);
quickSort(w, r + 1, end);
}
병합정렬
단점
- 임시 배열이 필요하다.
- 제자리 정렬이 아니다.
- 배열 크기가 큰 경우에는 이동 횟수가 많으므로 비효율 발생한다.
장점
- 최선과 최악 모두 시간복잡도 O(NlogN)으로, 안정적인 정렬 방법
- 만약 레코드를 연결 리스트(Linked List)로 구성하면, 링크 인덱스만 변경되므로 데이터의 이동은 무시할 수 있을 정도로 작아진다.
- 제자리 정렬(in-place sorting)로 구현할 수 있다.
- 따라서 크기가 큰 레코드를 정렬할 경우에 연결 리스트를 사용한다면, 합병 정렬은 퀵 정렬을 포함한 다른 어떤 졍렬 방법보다 효율적이다.
private static void mergeSort(int[] w, int start, int end) {
if (start >= end)
return;
int mid = (start + end) / 2;
mergeSort(w, start, mid);
mergeSort(w, mid + 1, end);
merge(w, start, mid, end);
}
private static void merge(int[] w, int start, int mid, int end) {
int[] tmp = new int[end - start + 1];
int l = start;
int r = mid + 1;
int tIdx = 0;
while (l <= mid && r <= end) {
if (w[l] <= w[r]) {
tmp[tIdx++] = w[l++];
} else {
tmp[tIdx++] = w[r++];
}
}
while (l <= mid) {
tmp[tIdx++] = w[l++];
}
while (r <= end) {
tmp[tIdx++] = w[r++];
}
for (int i = 0; i < tmp.length; i++) {
w[start + i] = tmp[i];
}
}