2025.04.04
Algorithm
정렬
버블 정렬
서로 인접한 두 원소를 검사하여 교환하는 방식의 정렬하는 알고리즘
- 배열 전체를 여러 번 반복하며 각 반복마다 가장 큰 요소가 끝으로 이동
- 시간 복잡도는 O(n^2)으로 효율적이지 않아 코딩 테스트에서는 많이 사용하지 않음
<!-- 버블 정렬 알고리즘을 사용한 오름차순 정렬 -->
public static void solution(int[] arr) {
for(int i = 0; i < arr.length - 1; i++) {
for(int j = 0; j < arr.length - i - 1; j++) {
<!-- 내림차순일 경우 arr[j] < arr[j+1]로 변경 -->
if(arr[j] > arr[j+1]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}최적화 된 버블 정렬
정렬이 어느 정도 되어 있는 경우 더 이상 교환이 발생하지 않으면 반복을 중단하여 불필요한 비교를 줄이는 방식으로 최대 O(n)까지 성능을 개선
public static void bubbleSort(int[] arr) {
boolean swapped;
for (int i = 0; i < arr.length - 1; i++) {
<!-- 교환 발생 여부 체크 -->
swapped = false;
for (int j = 0; j < arr.length - i - 1; j++) {
<!-- 인접 요소 비교 후 교환
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
<!-- 교환 발생했음을 표시 -->
swapped = true;
}
}
<!-- 교환이 한 번도 발생하지 않으면 정렬 완료 -->
if (!swapped) break;
}
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}선택 정렬
대상 데이터에서 최대나 최소 데이터를 데이터가 나열된 순으로 맨 뒤와 맨 앞을 찾아가며 선택하는 방법
- 시간 복잡도는 O(n^2)으로 효율적이지 않아 코딩 테스트에서는 많이 사용하지 않음
<!-- 선택 정렬 알고리즘의 사용한 최소값을 사용한 오름차순 정렬 -->
public static void solution(int[] arr) {
for(int i = 0; i < arr.length - 1; i++) {
<!-- 루프 한 번을 돌 때 가장 작은 값이 존재하는 인덱스 -->
int minIndex = i;
for(int j = i + 1; j < arr.length; j++) {
if(arr[j] < arr[minIndex]) {
minIndex = j;
}
}
<!-- 선택 된 데이터(최소 값)가 들어가야할 인덱스로 교환 -->
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}삽입 정렬
이미 정렬된 데이터 범위에 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입시켜 정렬하는 방법
- 가장 처음에 있는 데이터는 정렬이 되어있다고 보고 2번째 데이터를 선택해서 비교
- 왼쪽부터 차례대로 정렬을 확장하며, 새로운 요소가 들어갈 위치를 찾기 위해 비교하며 이동
- 시간 복잡도는 O(n^2)으로 효율적이지 않아 코딩 테스트에서는 많이 사용하지 않음
<!-- 삽입 정렬을 사용하여 오름차순으로 정렬 -->
public static void solution(int[] arr) {
for(int i = 1; i < arr.length; i++) {
<!-- 중간에 삽입 될 값 -->
int temp = arr[i];
<!-- i 인덱스보다 앞으로 인덱스를 탐색하면서 기준 값 보다 큰 경우 뒤로 하나씩 인덱스를 민다 -->
for(int j = i - 1; j >= 0; j--) {
if(arr[j] > temp) {
arr[j + 1] = arr[j];
} else break;
}
<!-- 반복문을 빠져나왔다는 것은 적절한 삽입 위치를 찾았다는 의미이므로 temp를 삽입 -->
arr[j + 1] = temp;
}
}퀵 정렬
기준값(pivot)을 선정해 해당 값보다 작은 데이터와 큰 데이터로 분류하는 것을 반복해서 정렬하는 것
- 분할 후 각각의 부분 배열을 재귀적으로 정렬하여 정렬을 완성
- pivot의 설정 방식에 따라 퀵 정렬의 성능이 달라진다
- 병합 정렬과 함께 실제 정렬 알고리즘으로 많이 활용
public static void solution(int[] arr) {
<!-- 퀵 정렬을 수행하여 오름차순 정렬 -->
quickSort(arr, 0, arr.length - 1);
}
private static void quickSort(int[] arr, int low, int high) {
<!-- 기본 종료 조건 -->
if(low >= high) return;
<!-- 분할 작업 수행: pivot 기준으로 좌우 나누고, 다음 분할 기준 인덱스 반환 -->
int partitionIndex = partition(arr, low, high);
<!-- 왼쪽 구간 정렬 (pivot보다 작은 값들) -->
quickSort(arr, low, partitionIndex - 1);
<!-- 오른쪽 구간 정렬 (pivot보다 큰 값들) -->
quickSort(arr, partitionIndex, high);
}
private static int partition(int[] arr, int low, int high) {
<!-- 가운데 값을 pivot으로 설정 -->
int pivot = arr[(low + high) / 2];
<!-- low가 high를 넘기 전까지 반복 → 교차 시 분할 완료 -->
while(low <= high) {
<!-- pivot보다 작으면 제자리 → 다음으로 이동 -->
while(arr[low] < pivot) low++;
<!-- pivot보다 크면 제자리 → 이전으로 이동 -->
while(arr[high] > pivot) high--;
<!-- 교환 조건: low가 high를 지나치지 않았으면 서로 교환 -->
if(low <= high) {
swap(arr, low, high);
low++;
high--;
}
}
return low;
}
private static void swap(int[] arr, int index1, int index2) {
int temp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = temp;
}병합 정렬
분할 정복 방식을 사용해 데이터를 분할하고 분할한 집합을 정렬해서 합치는 방식
- 데이터를 절반씩 나누어 가장 작은 데이터 집합(인덱스 한개)으로 분할한 뒤 오름차순으로 정렬한 후 분할된 집합의 크기를 늘려가면서 병합하는 방식
- 정렬 된 두 개의 배열을 합치는 과정에서 안정 정렬(Stable Sort)의 특성을 유지
- 안정 정렬 : 동일한 값을 가지고 있는 배열인 경우 앞에 이미 정렬된 집합의 크기가 먼저 선언된다. -> 같은 값의 순서가 유지 - 병합 정렬이 진행되는 과정에서 병합을 진행할 새로운 배열을 선언해야 하기 때문에 O(n)의 추가적인 공간 복잡도가 발생
public static void solution(int[] arr) {
<!-- 추가 메모리 공간(병합 정렬에 사용할 임시 배열 생성) -->
int[] temp = new int[arr.length];
<!-- 전체 배열을 병합 정렬 -->
mergeSort(arr, temp, 0, arr.length - 1);
}
<!-- 배열을 분할하고 병합하는 재귀 함수 -->
private static void mergeSort(int[] arr, int[] temp, int left, int right) {
if(left < right) {
int mid = (left + right) / 2;
mergeSort(arr, temp, left, mid);
mergeSort(arr, temp, mid + 1, right);
merge(arr, temp, left, mid, right);
}
}
private static void merge(int[] arr, int[] temp, int left, int mid, int right) {
<!-- 병합 구간의 배열을 임시 배열에 복사 -->
for(int i = left; i <= right; i++) {
temp[i] = arr[i];
}
int leftIndex = left;
int rightIndex = mid + 1;
int current = left;
<!-- 두 부분의 배열을 비교하면서 작은 값부터 복사 -->
while(leftIndex <= mid && rightIndex <= right) {
<!-- 대입할 때는 증가 전의 값을 사용, 대입이 끝난 뒤에 증가 -->
if(temp[leftIndex] <= temp[rightIndex]) {
arr[current++] = temp[leftIndex++];
} else {
arr[current++] = temp[rightIndex++];
}
}
<!-- 왼쪽 배열에 남은 요소를 복사한다
(오른쪽 배열에 남아있을 경우는 이미 제자리에 있으므로 처리할 필요가 없다.) -->
while(leftIndex <= mid) {
arr[current++] = temp[leftIndex++];
}
}TimSort
삽입 정렬과 병합 정렬의 장점을 결합한 하이브리드 정렬 알고리즘
- 작은 배열은 삽입 정렬로 정렬한 후, 병합 정렬 방식으로 전체 배열을 병합
<!-- TimSort에서 사용할 최소 정렬 단위(RUN)의 크기 (작은 배열은 삽입 정렬로 정렬) -->
private static final int RUN = 32;
public static void timSort(int[] arr) {
int n = arr.length;
// 각 RUN 단위로 삽입 정렬 수행
for (int i = 0; i < n; i += RUN) {
insertionSort(arr, i, Math.min((i + RUN - 1), n - 1));
}
<!-- 한 단계마다 두 개의 정렬된 구간을 병합하여 구간 크기를 두 배로 늘림
처음에는 두 개의 RUN 구간을 병합하고,
그 다음에는 두 개의 2×RUN 구간을 병합 -->
for (int size = RUN; size < n; size = 2 * size) {
<!-- 한 번에 두 개의 구간(각각의 크기가 size)을 병합하기 때문에
병합이 끝난 후 다음 두 구간으로 건너뛰기 위해 2×size 만큼 증가 -->
for (int left = 0; left < n; left += 2 * size) {
int mid = left + size - 1;
int right = Math.min(left + 2 * size - 1, n - 1);
<!-- 병합 가능한 경우에만 수행 -->
if (mid < right) {
merge(arr, left, mid, right);
}
}
}
}
<!-- 주어진 구간에 대해 삽입 정렬을 수행하는 메소드 -->
private static void insertionSort(int[] arr, int left, int right) {
for (int i = left + 1; i <= right; i++) {
int key = arr[i];
int j = i - 1;
while (j >= left && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
<!-- 두 개의 정렬된 부분 배열을 병합하여 하나의 정렬된 배열로 만드는 메소드(병합 정렬) -->
private static void merge(int[] arr, int left, int mid, int right) {
int len1 = mid - left + 1;
int len2 = right - mid;
<!-- 임시 배열 생성 -->
int[] leftArr = new int[len1];
int[] rightArr = new int[len2];
System.arraycopy(arr, left, leftArr, 0, len1);
System.arraycopy(arr, mid + 1, rightArr, 0, len2);
int i = 0, j = 0, k = left;
<!-- 두 임시 배열을 비교하여 정렬된 순서로 원본 배열에 복사 -->
while (i < len1 && j < len2) {
if (leftArr[i] <= rightArr[j]) {
arr[k++] = leftArr[i++];
} else {
arr[k++] = rightArr[j++];
}
}
<!-- 왼쪽 배열에 남은 값 복사 (오른쪽은 이미 정렬된 상태이므로 무시 가능) -->
while (i < len1) {
arr[k++] = leftArr[i++];
}
}
참고
메서드의 테스트 코드 만드는 방법
- Alt + Insert -> Generate > Test
잔디 속 새싹 하나