『Do it! 알고리즘 코딩 테스트 with JAVA 강의』를 듣고 정리한 글입니다.
정렬 알고리즘 | 정의 |
---|---|
버블 (Bubble) | 데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 방식 |
선택 (Selection) | 대상에서 가장 크거나 작은 데이터를 찾아가 선택을 반복하면서 정렬하는 방식 |
삽입 (Insertion) | 대상을 선택해 정렬된 영역에서 선택 데이터의 적절한 위치를 찾아 삽입하면서 정렬하는 방식 |
퀵 (Quick) | pivot 값을 선정해 해당 값을 기준으로 정렬하는 방식 |
병합 (Merge) | 이미 정렬된 부분 집합들을 효율적으로 병합해 전체를 정렬하는 방식 |
기수 (Radix) | 데이터의 자릿수를 바탕으로 비교해 데이터를 정렬하는 방식 |
❓ N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램
for (int i = 0; i < N-1; i++) {
for (int j = 0; j < N-1-i; j++) {
// 인접한 두 데이터를 비교
if(A[j] > A[j+1]) {
int temp = A[j];
A[j] = A[j+1];
A[j+1] = temp;
}
}
}
❓ N개의 수가 주어졌을 때, 이를 내림차순으로 정렬하는 프로그램
// i : 정렬된 부분의 범위
for (int i = 0; i < N; i++) {
// 최댓값의 인덱스
int Max = i;
// j : 남은 정렬 부분의 범위
for (int j = i+1; j < N; j++) {
// 최댓값의 인덱스 찾기
if (A[j] > A[Max]) {
Max = j;
}
}
// 최댓값이면 swap
if(A[i] < A[Max]) {
int temp = A[i];
A[i] = A[Max];
A[Max] = temp;
}
}
❓ N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램
// temp : 정렬할 데이터, j : 정렬된 범위
int temp, j;
for (int i = 1; i < N; i++) {
// 정렬할 데이터 선택
temp = A[i];
// 삽입 위치 탐색하면서 Shift 연산 수행
for (j = i-1; j >= 0; j--) {
if(A[j] > temp) {
// 선택 데이터보다 클 경우 한 칸 뒤로 Shift
A[j+1] = A[j];
}
else {
// 선택 데이터보다 작을 경우 반복문 종료
break;
}
}
// 적절한 위치에 삽입
A[j+1] = temp;
}
// 위키백과의 퀵정렬 알고리즘
public void quickSort(int[] arr, int left, int right) {
// base condition
if (left >= right) {
return;
}
int pivot = arr[right];
int sortedIndex = left;
for (int i = left; i < right; i++) {
if (arr[i] <= pivot) {
swap(arr, i, sortedIndex);
sortedIndex++;
}
}
swap(arr, sortedIndex, right);
quickSort(arr, left, sortedIndex - 1);
quickSort(arr, sortedIndex + 1, right);
}
private void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
private static void mergeSort() {
int A[] = new int[N];
devide(A, 0, N);
}
private static void devide(int[] arr, int low, int high) {
if (high - low < 2) {
return;
}
int mid = (low + high) / 2;
devide(arr, 0, mid);
devide(arr, mid, high);
merge(arr, low, mid, high);
}
private static void merge(int[] arr, int low, int mid, int high) {
int[] temp = new int[high - low];
int t = 0, l = low, h = mid;
// 왼쪽 배열과 오른쪽 배열 중 하나를 다 비울때까지 반복
while (l < mid && h < high) {
// 작은 값을 temp 배열에 우선해서 담기
if (arr[l] < arr[h]) {
temp[t++] = arr[l++];
} else {
temp[t++] = arr[h++];
}
}
// 만약 왼쪽 배열이 남아있다면 담기
while (l < mid) {
temp[t++] = arr[l++];
}
// 만약 오른쪽 배열이 남아있다면 담기
while (h < high) {
temp[t++] = arr[h++];
}
// temp 배열을 원본 배열로 복사 (정렬 완료)
for (int i = low; i < high; i++) {
arr[i] = temp[i - low];
}
}
// 자릿수 (개수)
int MaxNumber = A[0];
for (int num : A){
if (num > MaxNumber) {
MaxNumber = num;
}
}
// bucket 초기화
Queue<Integer>[] buckets = new Queue[10];
for (int i = 0; i < 10; i++) {
buckets[i] = new LinkedList<>();
}
// 자릿수를 기준으로 정렬
for (int exp = 1; exp <= MaxNumber; exp *= 10) {
// 버킷에 분류하여 저장
for (int num : A) {
int digit = (num / exp) % 10;
buckets[digit].add(num);
}
// 버킷에서 꺼내기 (정렬)
int index = 0;
for (int digit = 0; digit < buckets.length; digit++) {
while (!buckets[digit].isEmpty()) {
A[index++] = buckets[digit].poll();
}
}
}
for (int i = 0; i < N; i++) {
System.out.print(A[i] + " ");
}