[1주차] 정렬 & 탐색 알고리즘 정리
🎯 목표
- 정렬 알고리즘의 종류를 익히고 각각의 시간복잡도와 구현법을 이해한다.
- 이분탐색 알고리즘을 이해한다.
🪜 정렬 알고리즘
- 이름 그대로 주어진 데이터를 정렬하는 알고리즘.
- 7가지 알고리즘이 기본이고, 응용에 따라서 추가적인 알고리즘이 존재한다.
1️⃣ 선택 정렬
- 선택한 값을 모두 비교해서 알맞는 자리를 찾는 정렬 알고리즘이다.
- 즉, 선택한 값 다음에 오는 모든 값을 비교해서 가장 작은 값과 위치를 바꾼다.
- 시간복잡도 : O(n^2)
public void selectionSort(int arr[], int size) {
for (int i = 0 ; i < size -1 ; i++) {
int minIndex = i;
for (int j = i + 1 ; j < size ; i++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
swap(arr[i], arr[minIndex]); // 가장 작은 값과 위치를 바꾼다.
}
}2️⃣ 삽입 정렬
- 선택한 값을 이전 값들과 비교해서 알은은 자리를 찾는 정렬 알고리즘.
- 두 번째 값부터 선택해서 이전 값들과 비교하는 게 핵심이다.
- 시간복잡도 : O(n^2)
public void insertionSort(int arr[], int size) {
for(int i = 1 ; i < size ; i++) {
int target = arr[i];
int j = i - 1;
// 더 작지 않다면 비교할 필요가 없다.
while (j >= 0 && target < arr[j]) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = target; // 가장 마지막에 비교한 위치에 위치시킨다.
}
}3️⃣ 버블 정렬 🔥
- 내가 생각하는 핵심 정렬 알고리즘 중 하나, 이유는 CS에서 많이 등장하기 때문이다.
- 인접한 두 수를 비교해서 알은은 위치를 찾아가는 정렬 알고리즘이다.
- 시간복잡도 : O(n^2)
public void bubbleSort(int arr[], int size) {
for (int i = 0 ; i < size - 1; i++) {
for (int j = 0; j < size - 1 - i ; j++) {
// 인접한 두 값을 비교해서 자리를 바꾼다.
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j+1]);
}
}
}
}4️⃣ 합병 정렬 🔥
- 내가 생각하는 핵심 정렬 알고리즘 중 하나, 분할-정복 알고리즘의 한 종류이기 떄문이다.
- 부분 집합을 계속 정렬하면서 나누고, 정렬된 부분 집합을 합치는 알고리즘이다.
- 시간복잡도 : O(nlogn)
// 임시로 저장할 메모리가 필요하다.
int[] temp = new int[arr.length];
public void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
// 중간 값을 기준으로 나눠 재귀적으로 수행한다.
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
// 나눠진 부분 집합을 합친다.
merge(arr, left, mid, right);
}
}
private void merge(int[] arr, int left, int mid, int right) {
int i = left; // 첫 번째 배열의 인덱스
int j = mid + 1; // 두 번재 배열의 인덱스
int k = left; // 임시 배열의 인덱스
// 임시 배열에 두 배열을 비교해서 더 작은 값을 저장한다.
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
// 남아있는 값들을 임시 배열에 넣어준다.
while (i <= mid) {
temp[k++] = arr[i++];
}
while (j <= right) {
temp[k++] = arr[j++];
}
// 마지막으로 임시 배열을 원래 배열에 복사해준다.
for (int index = left; index < k; index++) {
arr[index] = temp[index];
}
}5️⃣ 힙 정렬
- 개인적으로 중요하지 않다고 생각하는 정렬 알고리즘.
- 트리 기반이며, 정렬을 위해서 최대 힙과 최소 힙을 알아야한다. 따라서 설명은 PASS
- 시간복잡도 : O(nlogn)
public void heapSort(int[] arr) {
int n = arr.length;
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// 힙에서 요소 하나씩 꺼내어 배열의 뒤쪽부터 저장
for (int i = n - 1; i >= 0; i--) {
swap(arr[0], arr[i]);
heapify(arr, i, 0);
}
}
private void heapify(int[] arr, int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
if (largest != i) {
swap(arr[i], arr[largest];
heapify(arr, n, largest);
}
}6️⃣ 퀵 정렬 🔥
- 내가 생각하는 핵심 정렬 알고리즘 중 하나, 가장 자주 쓰이는 알고리즘이기 때문이다.
- 임의의 값(pivot)을 기준으로 작은 값과 큰 값으로 두 부분집합을 나누어 재귀적으로 정렬한다.
- 합병 정렬과 같이 분할-정복 알고리즘을 응용한 알고리즘이다.
- 시간복잡도 : O(nlogn)
public void quickSort(int[] arr, int left, int right) {
if (left < right) {
// 기준점(pivot)을 기준으로 배열을 나눈다.
int pivotIndex = partition(arr, left, right);
// 재귀적으로 정렬한다.
quickSort(arr, left, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, right);
}
}
private int partition(int[] arr, int left, int right) {
// 일반적으로 기준값(pivot)은 처음 혹은 마지막 값으로 정한다.
int pivot = arr[left];
int i = left + 1;
int j = right;
// 기준값보다 큰 값과 작은 값을 좌우로 나누는 과정
while (i <= j) {
while (i <= j && arr[i] <= pivot) {
i++;
}
while (i <= j && arr[j] > pivot) {
j--;
}
if (i < j) {
swap(arr[i], arr[j]);
}
}
// 기준값을 교차지점에 둔다.
swap(arr[left], arr[j]);
return j;
}7️⃣ 기수 정렬
- 개인적으로 중요하지 않다고 생각하는 정렬 알고리즘.
- 사용되는 것을 단 한번도 본 적이 없기 때문이다. 따라서 설명은 PASS
- 시간복잡도 : O(dn) (d : 자수), 사실상 O(n)이다.
public void radixSort(int[] arr) {
int max = getMax(arr);
for (int exp = 1; max / exp > 0; exp *= 10) {
countSort(arr, exp);
}
}
private int getMax(int[] arr) {
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}
private void countSort(int[] arr, int exp) {
int n = arr.length;
int[] output = new int[n];
int[] count = new int[10];
for (int i = 0; i < n; i++) {
int digit = (arr[i] / exp) % 10;
count[digit]++;
}
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
for (int i = n - 1; i >= 0; i--) {
int digit = (arr[i] / exp) % 10;
output[count[digit] - 1] = arr[i];
count[digit]--;
}
for (int i = 0; i < n; i++) {
arr[i] = output[i];
}
}🪜 나아가기
- 우리가 Java에서 사용하는 정렬 알고리즘은 그럼 무엇일까?
- 보통 Arrays.sort()와 Collections.sort() 두 가지 정렬을 사용한다.
1️⃣ Arrays.sort()
- 내부 구현을 확인해보면 다음과 같이 듀얼 피벗 퀵정렬을 사용하는 것을 알 수 있다.
🤔 듀얼 피벗 퀵정렬?
듀얼 피벗 퀵정렬은 기준값(pivot)이 두 개, 분할되는 영역이 3개인 퀵정렬 알고리즘이다.
시간복잡도는 좀더 개선된 O(nlog3n)이다.
2️⃣ Collections.sort()
- 내부 구현을 확인해보면 아는 정렬 알고리즘과 다른 것을 사용한다. 바로 TimSort!
🤔 TimSort?
팀 피터스가 만든 정렬 알고리즘이다. 파이썬의 표준 정렬 알고리즘이기도 하다.
삽입 정렬과 합병 정렬을 결합한 알고리즘이고, 시간복잡도는 O(nlogn)이다.
🪄 탐색 알고리즘
- 이름 그대로 원하는 값을 찾는 알고리즘
- 다양한 알고리즘이 존재하지만 코딩 테스트에서 주로 나오는 것은 이분 탐색이다.
- 사실 BFS, DFS도 탐색 알고리즘 중 하나라고 볼 수 있다. 😋😋😋
👀 이분 탐색 (이진 탐색)
- 범위를 절반씩 줄여나가면서 원하는 값을 찾는 탐색 알고리즘이다.
- 탐색하는 값들은 반드시 정렬되어야 한다.
- 이분 탐색의 핵심은 어떤 값을 찾을지와 어떤 값을 범위로 삼을지이다.
- 시간복잡도 : O(logn)
public int binarySearch(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
Backend-Dev