⭐ 선택 정렬
처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복한다.
📝 코드 구현
import java.util.*;
public class Main {
public static void main(String[] args) {
int n = 10;
int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};
for (int i = 0; i < n; i++) {
int min_index = i; // 가장 작은 원소의 인덱스
for (int j = i + 1; j < n; j++) {
if (arr[min_index] > arr[j]) {
min_index = j;
}
}
// swap
int temp = arr[i];
arr[i] = arr[min_index];
arr[min_index] = temp;
}
for(int i = 0; i < n; i++) {
System.out.print(arr[i] + " ");
}
}
}선택정렬의 시간 복잡도
- 선택 정렬은 N번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다.
- 구현 방식에 따라서 사소한 오차는 있을 수 있지만, 전체 연산 횟수는 다음과 같다
N + (N - 1) + (N - 2) + ... + 2 - 이는 (N² + N - 2) / 2 로 표현할 수 있는데, 빅오 표기법에 따라서 O(N²) 이라고 작성한다.
⭐ 삽입 정렬
- 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입한다.
- 선택 정렬에 비해 구현 난이도가 높은 편이지만, 일반적으로 더 효율적으로 동작한다.
📝 코드 구현
import java.util.*;
public class Main {
public static void main(String[] args) {
int n = 10;
int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};
for (int i = 1; i < n; i++) {
// 인덱스 i부터 1까지 감소하며 반복하는 문법
for (int j = i; j > 0; j--) {
// 한 칸씩 왼쪽으로 이동
if (arr[j] < arr[j - 1]) {
// 스와프(Swap)
int temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
}
// 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
else break;
}
}
for(int i = 0; i < n; i++) {
System.out.print(arr[i] + " ");
}
}
}삽입정렬의 시간 복잡도
- 삽입 정렬의 시간 복잡도는 O(N²)이며, 선택 정렬과 마찬가지로 반복문이 두번 중첩되어 사용된다.
- 삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다.
- 최선의 경우 O(N)의 시간 복잡도를 가진다.
- 이미 정렬되어 있는 상태에서 다시 삽입 정렬을 수행하면 어떻게 될까?
왼쪽 데이터들 중 어디로 들어갈지 고르는 부분이 상수 시간으로 대체되기 때문에 전체 정렬을 위한 시간복잡도는 O(N)이 된다.
⭐ 퀵 정렬
- 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법
- 일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나
- 병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘
- 가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(Pivot)로 설정한다.
퀵 정렬이 빠른 이유: 직관적인 이해
퀵정렬의 시간 복잡도
- 퀵 정렬은 평균의 경우 O(N㏒N)의 시간 복잡도를 가진다.
- 하지만 최악의 경우 O(N²)의 시간 복잡도를 가진다.
- 첫 번째 원소를 피벗으로 삼을 때, 이미 정렬된 배열에 대해서 퀵 정렬을 수행한다면?
분할이 이루어질때마다 pivot보다 큰 값들만 존재할 것이다.
한쪽 방향으로 편향된 분할이 발생
분할이 수행되는 갯수가 N과 비례하고 분할을 하기 위해서 매번 선형탐색을 수행해야 하기 때문에 전체 시간 복잡도가 O(N²)이 된다.
- 첫 번째 원소를 피벗으로 삼을 때, 이미 정렬된 배열에 대해서 퀵 정렬을 수행한다면?
📝 코드 구현
import java.util.*;
public class Main {
public static void quickSort(int[] arr, int start, int end) {
if (start >= end) return; // 원소가 1개인 경우 종료
int pivot = start; // 피벗은 첫 번째 원소
int left = start + 1;
int right = end;
while (left <= right) {
// 피벗보다 큰 데이터를 찾을 때까지 반복
while (left <= end && arr[left] <= arr[pivot]) left++;
// 피벗보다 작은 데이터를 찾을 때까지 반복
while (right > start && arr[right] >= arr[pivot]) right--;
// 엇갈렸다면 작은 데이터와 피벗을 교체
if (left > right) {
int temp = arr[pivot];
arr[pivot] = arr[right];
arr[right] = temp;
}
// 엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체
else {
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
}
// 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
quickSort(arr, start, right - 1);
quickSort(arr, right + 1, end);
}
public static void main(String[] args) {
int n = 10;
int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};
quickSort(arr, 0, n - 1);
for(int i = 0; i < n; i++) {
System.out.print(arr[i] + " ");
}
}
}⭐ 계수 정렬
- 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작하는 정렬 알고리즘이다.
- 계수정렬은 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능
- 데이터의 개수가 N, 데이터(양수) 중 최댓값이 K일 때 최악의 경우에도 수행기간 O(N + K)를 보장한다.
- 각각의 데이터가 몇번씩 등장 했는지
📝 코드 구현
import java.util.*;
public class Main {
public static final int MAX_VALUE = 9;
public static void main(String[] args) {
int n = 15;
// 모든 원소의 값이 0보다 크거나 같다고 가정
int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2};
// 모든 범위를 포함하는 배열 선언(모든 값은 0으로 초기화)
int[] cnt = new int[MAX_VALUE + 1];
for (int i = 0; i < n; i++) {
cnt[arr[i]] += 1; // 각 데이터에 해당하는 인덱스의 값 증가
}
for (int i = 0; i <= MAX_VALUE; i++) { // 배열에 기록된 정렬 정보 확인
for (int j = 0; j < cnt[i]; j++) {
System.out.print(i + " "); // 띄어쓰기를 기준으로 등장한 횟수만큼 인덱스 출력
}
}
}
}계수정렬의 복잡도 분석
- 계수 정렬의 시간 복잡도와 공간 복잡도 모두 O(N + K)이다.
- 계수 정렬은 때에 따라서 심각한 비효율성을 초래할 수 있다.
- 데이터가 0과 999,999로 단 2개만 존재하는 경우를 생각하면 된다.
- 계수 정렬은 동일한 값을 가지는 데이터가 여러 개 등장할 때 효과적으로 사용할 수 있다.
- 성적의 경우 100점을 맞은 학생이 여러 명일 수 있기 때문에 계수 정렬이 효과적이다.
⭐ 정렬 알고리즘 비교하기
- 앞서 다룬 네가지 정렬 알고리즘을 비교하면 다음과 같다.
- 추가적으로 대부분의 프로그래밍 언어에서 지원하는 표준 정렬 라이브러리는 최악의 경우에도 O(NlogN)을 보장하도록 설계되어 있다.
🔎 <문제> 두 배열의 원소 교체
📝 문제 해결 아이디어
- 핵심 아이디어: 매번 배열 A에서 가장 작은 원소를 골라서, 배열 B에서 가장 큰 원소와 교체
- 가장 먼저 배열 A와 B가 주어지면 A에 대하여 오름차순 정렬하고, B에 대하여 내림차순 정렬한다.
- 이후에 두 배열의 원소를 첫 번째 인덱스부터 차례로 확인하면서 A의 원소가 B의 원소보다 작을 때에만 교체를 수행
- 이 문제에서는 두 배열의 원소가 최대 100,000개까지 입력될 수 있으므로, 최악의 경우 O(NlogN)을 보장하는 정렬 알고리즘을 이용해야 한다.
📝 답안 예시
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// N과 K를 입력받기
int n = sc.nextInt();
int k = sc.nextInt();
// 배열 A의 모든 원소를 입력받기
Integer[] a = new Integer[n];
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
// 배열 B의 모든 원소를 입력받기
Integer[] b = new Integer[n];
for (int i = 0; i < n; i++) {
b[i] = sc.nextInt();
}
// 배열 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);
}
}reference
Arrays.sort()를 사용하기 위해 배열 선언시 Wrapper Class를 쓰는 이유가 궁금해졌다.
2학년 때 자바를 배울때도 wrapper가 어떤 개념인지 헷갈렸는데 이참에 제대로 공부해야겠다.
Wrapper Class란?
(이코테 2021 강의 몰아보기) 4. 정렬 알고리즘
항상 궁금해하기