선택 정렬
가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고,
그다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복하면 어떨까?
가장 원시적인 방법으로 매번 가장 작은 것을 선택한다는 의미에서 선택 정렬 알고리즘이라고 한다.
static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
static void selectionSort(int[] a) {
for(int i = 0; i < a.length-1; ++i) {
int min = i; // 아직 정렬되지 않은 부분에서 가장 작은 요소의 인덱스를 기록한다.
for(int j = i+1; j < a.length; ++j)
if(a[j] < a[min]) {
min = j;
}
swap(a, i, min); // 아직 정렬되지 않은 부분의 첫 요소와 가장 작은 요소의 자리를 바꾼다.
}
}
선택 정렬은 N-1번 만큼 가장 작은 수를 찾아 맨 앞으로 보내야 한다.
선택 정렬의 시간 복잡도는 O(N^2) 이다.
선택 정렬은 기본 정렬 라이브러리를 포함해 다른 알고리즘과 비교했을 때 매우 비효율적이다.
다만 특정 리스트에서 가장 작은 데이터를 찾는 일에서 선택 정렬 소스코드가 필요할 수 있다.
삽입 정렬
삽입 정렬을 느린 편이다.
데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입하면?
삽입 정렬은 필요할 때만 위치를 바꾸므로 데이터가 거의 정렬되어 있을 때 훨씬 효율적이다.
static void insertionSort(int[] a) {
for (int i = 1; i < a.length; ++i) {
int value = a[i]; // 삽입할 값 보관
int j;
for (j = i - 1; j >= 0; --j) { // 뒤로 이동
if (a[j] > value) {
a[j + 1] = a[j];
} else {
break;
}
}
a[j + 1] = value; // 값 삽입
}
}
퀵 정렬
퀵 정렬과 병합 정렬은 대부분의 프로그래밍 언어에서 정렬 라이브러리의 근간이 되는 알고리즘이기도 하다.
기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸면 어떨까?
퀵 정렬은 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작한다.
퀵 정렬에서는 pivot이라는 기준 값이 사용된다.
static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
static int partition(int[] a, int start, int end) {
int i = start - 1;
int value = a[end];
for(int j = start; j < end; ++j) {
if(a[j] < value)
swap(a, ++i, j);
}
swap(a, i + 1, end);
return i + 1;
}
static void quickSort(int[] a, int start, int end) {
if(start >= end) return;
int middle = partition(a, start, end); // 배열 나누기
quickSort(a, start, middle-1); // 1구역 정렬
quickSort(a, middle+1, end); // 2구역 정렬
}
계수 정렬 & 기수 정렬
https://hyerin6.github.io/2021-01-20/countingSort/
문제: 두 배열의 원소 교체
문제)
두 배열 A, B를 가지고 있다. 두 배열은 N개의 원소로 구성되어 있으며 배열의 원소는 모두 자연수이다.
최대 K번 바꿔치기 연산을 수행할 수 있는데 바꿔치기 연산이란
배열 A에 있는 원소 하나와 배열 B에 있는 원소 하나를 골라서 두 원소를 서로 바꾸는 것을 말한다.
최종 목표는 배열 A의 모든 원소의 합이 최대가 되도록 하는 것이다.
[Input]
5 3
1 2 5 4 3
5 5 6 6 5
[Output]
26
풀이 코드
public class Main {
public static void main(String[] args) {
int n = 5;
int k = 3;
int[] a = {1, 2, 5, 4, 3};
Integer[] b = {5, 5, 6, 6, 5};
// 배열 A는 오름차순 정렬 수행
Arrays.sort(a);
// 배열 B는 내림차순 정렬 수행
Arrays.sort(b, Collections.reverseOrder());
// 첫 번째 인덱스부터 확인하며, 두 배열의 원소를 최대 K번 비교
for (int i = 0; i < k; i++) {
// A의 원소가 B의 원소보다 작은 경우
if (a[i] < b[i]) {
// 두 원소를 교체
int temp = a[i];
a[i] = b[i];
b[i] = temp;
}
// A의 원소가 B의 원소보다 크거나 같을 때, 반복문을 탈출
else
break;
}
// 배열 A의 모든 원소의 합을 출력
long result = 0;
for (int i = 0; i < n; i++) {
result += a[i];
}
System.out.println(result);
}
}