Java 정렬 알고리즘(Sorting Algorithms)
자바에서 사용되는 정렬 알고리즘에는 여러 가지가 있으며, 각 알고리즘은 서로 다른 방식과 성능 특성을 가지고 있다.
대표적인 정렬 알고리즘은 아래와 같다.
- 버블 정렬(Bubble Sort)
- 선택 정렬(Selection Sort)
- 삽입 정렬(Insertion Sort)
- 퀵 정렬(Quick Sort)
- 병합 정렬(Merge Sort)
- 힙 정렬(Heap Sort)
퀵 정렬(Quick Sort)
기준 원소(pivot)을 선택하여 기준 원소보다 작은 원소들은 왼쪽에, 큰 원소들은 오른쪽에 배치하고 재귀적으로 이 과정을 반복한다.
특징
- 시간 복잡도: 평균적으로 O(n log n), 최악의 경우 O(n^2) - 피벗 선택에 따라 다름
- 공간 복잡도: O(log n) - 재귀 호출 스택 사용
- 불안정 정렬: 동일한 값의 원소들이 정렬 후 원래 순서를 유지하지 않을 수 있음
- 분할 정복: 배열을 두 부분으로 분할하고 각각을 재귀적으로 정렬
장점
- 대부분의 경우 매우 빠름
- 추가 메모리 사용이 적음(제자리 정렬)
단점
- 최악의 경우 O(n^2)의 시간 복잡도
- 안정적이지 않음
예제 및 문제 풀이
문제: 주어진 배열 [3, 6, 8, 19, 1, 2, 1]을 퀵 정렬을 사용하여 오름차순으로 정렬하시오.
풀이
package algorithm.sort;
/* Quick Sort(퀵 정렬)
* 특징
* 시간 복잡도: 평균적으로 O(n log n), 최악의 경우 O(n^2) 피벗 선택에 따라 다름
* 공간 복잡도: O(log n) 재귀 호출 스택 사용
* 불안정 정렬: 동일한 값의 원소들이 정렬 후 원래 순서를 유지하지 않을 수 있음
* 분할 정복 알고리즘: 배열을 두 부분으로 분할하고 각각을 재귀적으로 정렬
*
* 장점
* 대부분의 경우 매우 빠름, 추가 메모리 사용이 적음(제자리 정렬)
*
* 단점
* 최악의 경우 O(n^2)의 시간 복잡도, 안정적이지 않음
*
* 예제
* 주어진 배열 [3, 6, 8, 10, 1, 2, 1]을 퀵 정렬을 사용하여 오름차순으로 정렬하시오*/
import java.util.Arrays;
// 풀이
public class QuickSort {
// 퀵 정렬 함수
public static void quickSort(int[] arr, int left, int right) {
if (left < right) {
// 배열을 분할하고 피벗의 인덱스를 반환
int pivotIndex = partition(arr, left, right);
// 피벗을 기준으로 좌우 부분 배열을 재귀적으로 정렬
quickSort(arr, left, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, right);
}
}
// 배열을 분할하는 함수
private static int partition(int[] arr, int left, int right) {
int pivot = arr[right]; // 피벗을 배열의 마지막 요소로 설정
int i = (left - 1); // 작은 요소들의 마지막 인덱스
for (int j = left; j < right; j++) {
// 현재 요소가 피벗보다 작거나 같으면
if (arr[j] < pivot) {
i++;
// arr[i]와 arr[j]를 교환
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// 피벗을 올바른 위치로 이동
int temp = arr[i + 1];
arr[i + 1] = arr[right];
arr[right] = temp;
return i + 1; // 피벗의 인덱스를 반환
}
// 메인 함수
public static void main(String[] args) {
int[] arr = {3, 6, 8, 10, 1, 2, 1};
quickSort(arr, 0, arr.length - 1); // 퀵 정렬 호출
System.out.println(Arrays.toString(arr)); // 정렬된 배열 출력
}
}
퀵 정렬의 partition 함수
1. 피벗을 선택하고, 피벗보다 작은 요소들은 피벗의 왼쪽에, 큰 요소들은 피벗의 오른쪽에 위치시킨다.
2. 최종적으로 피벗의 위치를 반환한다.
피벗을 기준으로 배열이 두 부분으로 나뉘면, 각 부분 배열을 독립적으로 정렬해야 하므로 quickSort를 두 번 호출한다.
- 첫 번째 호출: 피벗의 왼쪽 부분 배열을 정렬
- 두 번째 호출: 피벗의 오른쪽 부분 배열을 정렬
배열 [3, 6, 8, 10, 1, 2, 1]에 대해 퀵 정렬을 수행하는 과정
- 초기 배열: [3, 6, 8, 10, 1, 2, 1]
- 피벗을 선택 (예: 마지막 요소 1)
- partition 함수로 배열을 재배열:
- [1, 1, 3, 10, 6, 2, 8] (피벗 1의 위치는 1)
- 피벗을 기준으로 배열을 두 부분으로 분할:
- 왼쪽 부분 배열: [1]
- 오른쪽 부분 배열: [3, 10, 6, 2, 8]
- 왼쪽 부분 배열 [1]에 대해 quickSort를 호출:
- 더 이상 분할할 필요 없음 (기저 조건 충족)
- 오른쪽 부분 배열 [3, 10, 6, 2, 8]에 대해 quickSort를 호출:
- 피벗을 선택 (예: 8)
- partition 함수로 배열을 재배열:
- [3, 6, 2, 8, 10] (피벗 8의 위치는 3)
- 피벗을 기준으로 다시 두 부분으로 분할:
- 왼쪽 부분 배열: [3, 6, 2]
- 오른쪽 부분 배열: [10]
- 왼쪽 부분 배열 [3, 6, 2]에 대해 quickSort를 호출:
- 피벗을 선택 (예: 2)
- partition 함수로 배열을 재배열:
- [2, 3, 6] (피벗 2의 위치는 0)
- 피벗을 기준으로 다시 두 부분으로 분할:
- 왼쪽 부분 배열: [] (기저 조건 충족)
- 오른쪽 부분 배열: [3, 6]
이 과정을 계속 반복하여 배열 전체가 정렬된다.
병합 정렬(Merge Sort)
병합 정렬은 분할 정복 알고리즘으로, 배열을 두 부분으로 나눈 후 각각을 재귀적으로 정렬하고, 두 부분을 병합하는 방식으로 전체 배열을 정렬한다.
특징
- 시간 복잡도: 항상 O(n log n)
- 공간 복잡도: O(n) - 추가 배열 사용
- 안정 정렬: 동일한 값의 원소들이 정렬 후 원래 순서를 유지
- 분할 정복: 배열을 반으로 나누고 각각을 정렬한 후 병합
장점
- 최악의 경우에도 O(n log n)의 시간 복잡도
- 안정적
단점
- 추가적인 메모리 공간 필요
예제 및 문제 풀이
문제: 주어진 배열 [38, 27, 43, 3, 9, 82, 10]을 병합 정렬을 사용하여 오름차순으로 정렬하시오.
풀이
package algorithm.sort;
/* Merge Sort(병합 정렬)
* 특징
* 시간 복잡도: 항상 O(n log n)
* 공간 복잡도: O(n) (추가 배열 사용)
* 안정 정렬: 동일한 값의 원소들이 정렬 후 원래 순서를 유지
* 분할 정복 알고리즘: 배열을 반으로 나누고 각각을 정렬한 후 병합
*
* 장점
* 최악의 경우에도 O(n log n)의 시간 복잡도, 안정적
*
* 단점
* 추가적인 메모리 공간 필요
*
* 예제
* 주어진 배열 [38, 27, 43, 3, 9, 82, 10]을 병합 정렬을 사용하여 오름차순으로 정렬하시오.*/
import java.util.Arrays;
// 풀이
public class MergeSort {
// 병합 정렬 함수
public static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int middle = (left + right) / 2; // 중간 인덱스를 계산
// 좌측 반을 정렬
mergeSort(arr, left, middle);
// 우측 반을 정렬
mergeSort(arr, middle + 1, right);
// 정렬된 두 부분을 병합
merge(arr, left, middle, right);
}
}
// 두 부분 배열을 병합하는 함수
private static void merge(int[] arr, int left, int middle, int right) {
int n1 = middle - left + 1;
int n2 = right - middle;
// 임시 배열 생성
int[] L = new int[n1];
int[] R = new int[n2];
// 임시 배열에 데이터 복사
System.arraycopy(arr, left, L, 0, n1);
System.arraycopy(arr, middle + 1, R, 0, n2);
// 병합 과정
int i = 0, j = 0, k = left;;
// 두 부분 배열을 병합
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
// 왼쪽 부분 배열의 남은 요소들을 병합
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
// 오른쪽 부분 배열의 남은 요소들을 병합
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
// 메인 함수
public static void main(String[] args) {
int[] arr = {38, 27, 43, 3, 9, 82, 10};
mergeSort(arr, 0, arr.length - 1); // 병합 정렬 호출
System.out.println(Arrays.toString(arr)); // 정렬된 배열 출력
}
}
병합 정렬의 전체 과정
- 분할(Divide): 배열을 반으로 나누어 두 부분으로 분할한다.
- 정복(Conquer): 각 부분 배열을 재귀적으로 정렬한다.
- 병합(Merge): 두 정렬된 부분 배열을 병합하여 하나의 정렬된 배열로 만든다.
mergeSort 함수
배열을 계속해서 반으로 나누고, 배열의 크기가 1이 되면 더 이상 나눌 수 없으므로 정렬된 상태로 간주한다.
public static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int middle = (left + right) / 2;
mergeSort(arr, left, middle); // 왼쪽 반을 정렬
mergeSort(arr, middle + 1, right); // 오른쪽 반을 정렬
merge(arr, left, middle, right); // 두 부분을 병합
}
}
위 코드에서 mergeSort 함수는 배열을 재귀적으로 3번 호출한다.
- mergeSort(arr, left, middle): 배열의 왼쪽 반을 정렬
- mergeSort(arr, middle + 1, right): 배열의 오른쪽 반을 정렬
- merge(arr, left, middle, right): 두 정렬된 부분 배열을 병합
merge 함수
두 정렬된 부분 배열을 하나의 정렬된 배열로 병합한다.
merge 함수의 while 문들:
- 첫 번째 while 문:
- 왼쪽 부분 배열(L)과 오른쪽 부분 배열(R)의 요소들을 비교하여 더 작은 값을 arr에 넣는다.
- 두 부분 배열을 순차적으로 병합한다.
- 이 과정에서 L과 R의 요소들을 차례로 비교하여 arr에 넣기 때문에 정렬이 유지된다.
- 두 번째 while 문:
- 첫 번째 while 문이 종료되면 왼쪽 부분 배열에 남은 요소들이 있을 수 있다.
- 이 남은 요소들을 arr에 그대로 복사한다.
- 이 과정이 필요한 이유는 왼쪽 부분 배열의 요소들이 모두 병합되지 않았기 때문이다.
- 세 번째 while 문:
- 첫 번째 while 문이 종료되면 오른쪽 부분 배열에 남은 요소들이 있을 수 있다.
- 이 남은 요소들을 arr에 그대로 복사한다.
- 이 과정이 필요한 이유는 오른쪽 부분 배열의 요소들이 모두 병합되지 않았기 때문이다.
힙 정렬(Heap Sort)
힙 정렬(Heap Sort)은 힙 자료 구조를 사용하여 배열을 정렬하는 알고리즘으로 먼저 주어진 배열을 힙으로 만들고, 가장 큰 원소를 꺼내 배열의 끝에 놓는 과정을 반복한다(힙 정렬의 핵심은 배열을 힙으로 변환하고, 힙에서 요소를 하나씩 꺼내어 정렬하는 것이다).
특징
- 시간 복잡도: O(n log n)
- 공간 복잡도: O(1) - 제자리 사용
- 불안정 정렬
장점
- 추가 메모리 사용이 적음
- 항상 O(n log n)의 시간 복잡도
단점
- 구현이 상대적으로 복잡
- 안정적이지 않음
예제 및 문제 풀이
문제: 주어진 배열 [12, 11, 13, 5, 6, 7]을 힙 정렬을 사용하여 오름차순으로 정렬하시오.
풀이
package algorithm.sort;
/* Heap Sort(힙 정렬)
* 특징
* 시간 복잡도: O(n log n)
* 공간 복잡도: O(1) 제자리 정렬
* 불안정 정렬
*
* 장점
* 추가적인 메모리 사용이 적음, 항상 O(n log n)의 시간 복잡도
*
* 단점
* 구현이 상대적으로 복잡, 안정적이지 않음
*
* 예제
* 주어진 배열 [12, 11, 13, 5, 6, 7]을 힙 정렬을 사용하여 오름차순으로 정렬하시오.*/
import java.util.Arrays;
// 풀이
public class HeapSort {
// 힙 정렬 함수
public static 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--) {
// 루트와 현재 끝 요소를 교환
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// 줄어든 힙을 힙으로 유지
heapify(arr, i, 0);
}
}
private static 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) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
// 영향을 받는 서브트리 힙을 재귀적으로 힙으로 유지
heapify(arr, n, largest);
}
}
// 메인 함수
public static void main(String[] args) {
int[] arr = {12, 11, 13, 5, 6, 7};
heapSort(arr); // 힙 정렬 호출
System.out.println(Arrays.toString(arr)); // 정렬된 배열 출력
}
}
힙 정렬의 전체 과정
- 배열을 힙으로 변환: 배열을 최대 힙으로 변환한다. 이를 위해 배열의 중간부터 시작하여 각 노드에 대해 heapify를 호출한다.
- 힙에서 요소를 하나씩 꺼내어 정렬: 힙의 루트(가장 큰 값)를 배열의 끝으로 이동시키고, 남은 힙에 대해 heapify를 호출하여 힙 속성을 유지한다. 이 과정을 반복하여 배열을 정렬한다.
heapify 함수
heapify 함수는 주어진 배열에서 특정 인덱스를 루트로 하는 서브트리를 힙 속성을 만족하도록 재구성하는 함수로 여기서 힙은 최대 힙(max heap) 또는 최소 힙(min heap)을 말한다.
최대 힙에서는 부모 노드가 자식 노드보다 크거나 같고, 최소 힙에서는 부모 노드가 자식 노드보다 작거나 같아야 한다.
heapify 함수의 동작
heapify 함수는 주어진 인덱스에서 시작하여 해당 인덱스를 루트로 하는 서브트리를 최대 힙 속성을 만족하도록 재구성한다.
private static void heapify(int[] arr, int n, int i) {
int largest = i; // 1. 루트를 가장 큰 값으로 초기화
int left = 2 * i + 1; // 왼쪽 자식
int right = 2 * i + 2; // 오른쪽 자식
// 2. 왼쪽 자식이 루트보다 큰 경우
if (left < n && arr[left] > arr[largest])
largest = left;
// 3. 오른쪽 자식이 현재 가장 큰 값보다 큰 경우
if (right < n && arr[right] > arr[largest])
largest = right;
// 4. 가장 큰 값이 루트가 아닌 경우
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
// 영향을 받는 서브트리를 재귀적으로 힙으로 유지
heapify(arr, n, largest);
}
}- 루트 초기화: 주어진 인덱스를 루트로 초기화한다.
- 왼쪽 자식 확인: 왼쪽 자식의 인덱스를 계산하고, 배열의 범위 내에 있는지 확인한다.
- 왼쪽 자식이 루트보다 크면 largest를 왼쪽 자식의 인덱스로 업데이트한다.
- 오른쪽 자식 확인: 오른쪽 자식의 인덱스를 계산하고, 배열의 범위 내에 있는지 확인한다.
- 오른쪽 자식이 현재 largest보다 크다면, largest를 오른쪽 자식의 인덱스로 업데이트한다.
- 루트 교환: largest가 초기 루트 인덱스와 다르다면, 배열의 값을 교환한다. 그런 다음, 영향을 받는 서브트리를 재귀적으로 힙 속성을 유지하도록 한다.
버블 정렬(Bubble Sort)
버블 정렬(Bubble Sort)은 가장 간단한 정렬 알고리즘 중 하나로, 인접한 두 원소를 비교하여 교환하는 방식으로 정렬한다. 배열의 끝까지 반복하며, 더 이상 교환이 필요 없을 때까지 계속한다.
특징
- 시간 복잡도: O(n ^2)
- 공간 복잡도: O(1)
- 안정 정렬
장점
- 구현이 매우 간단
- 적은 데이터에 대해서는 효율적
단점
- 매우 비효율적(큰 데이터셋에서는 비효율적)
예제 및 문제 풀이
문제: 주어진 배열 [64, 34, 25, 12, 22, 11, 90]을 버블 정렬을 사용하여 오름차순으로 정렬하시오.
풀이
package algorithm.sort;
/* Bubble Sort(버블 정렬)
* 특징
* 시간 복잡도: O(n^2)
* 공간 복잡도: O(1)
* 안정 정렬
*
* 장점
* 구현이 매우 간단, 적은 데이터에 대해서는 효율적
*
* 단점
* 매우 비효율적(큰 데이터셋에서는 비효율적)
*
* 예제
* 주어진 배열 [64, 34, 25, 12, 22, 11, 90]을 버블 정렬을 사용하여 오름차순으로 정렬하시오.*/
import java.util.Arrays;
// 풀이
public class BubbleSort {
// 버블 정렬 함수
public static void bubbleSort(int[] arr) {
int n = arr.length;
// 배열의 모든 요소를 반복
for (int i = 0; i < n - 1; i++) {
// 인접한 요소들을 비교하고 교환
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// 교환
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
// 메인 함수
public static void main(String[] args) {
int[] arr = {64, 34, 25, 12, 22, 11, 90};
bubbleSort(arr); // 버블 정렬 호출
System.out.println(Arrays.toString(arr)); // 정렬된 배열 출력
}
}
버블 정렬의 동작 방식
버블 정렬은 배열의 각 요소를 반복적으로 비교하고, 인접한 요소들이 잘못된 순서에 있을 경우 교환하여 가장 큰(또는 작은) 요소를 점진적으로 배열의 끝으로 이동시키는 방식으로 동작한다.
이 과정은 물방울(bubble)이 물 위로 떠오르는 것처럼 가장 큰 값이 배열의 끝으로 이동하는 모습과 유사하여 "버블 정렬"이라고 불린다.
이중 for문의 사용 이유
- 첫 번째 for문:
- 배열의 모든 요소를 반복하여, 전체 배열을 여러 번 순회한다.
- i는 현재 정렬 패스의 인덱스를 나타내며, n-1-i는 이미 정렬된 요소들을 제외한 나머지 요소들을 처리한다.
- 두 번째 for문:
- 배열의 인접한 요소들을 비교하기 위해 사용된다.
- j는 현재 비교하고 있는 인덱스를 나타내며, n-1-i까지 반복한다. 이렇게 하면 각 패스에서 가장 큰 요소가 올바른 위치로 이동한 후 다시 비교되지 않도록 한다.
if 문의 사용 이유
- 두 인접한 요소를 비교하여, 앞의 요소가 뒤의 요소보다 크면 교환한다.
- 이 과정이 반복되면서 배열의 가장 큰 요소가 배열의 끝으로 이동하게 된다.
- 모든 요소에 대해 이러한 비교 및 교환을 반복하면 배열이 정렬된다.
동작 예시
배열 [64, 34, 25, 12, 22, 11, 90]의 버블 정렬 과정
- 첫 번째 패스 (i=0):
- [64, 34, 25, 12, 22, 11, 90]
- 64와 34를 비교하고 교환 → [34, 64, 25, 12, 22, 11, 90]
- 64와 25를 비교하고 교환 → [34, 25, 64, 12, 22, 11, 90]
- 64와 12를 비교하고 교환 → [34, 25, 12, 64, 22, 11, 90]
- 64와 22를 비교하고 교환 → [34, 25, 12, 22, 64, 11, 90]
- 64와 11를 비교하고 교환 → [34, 25, 12, 22, 11, 64, 90]
- 64와 90을 비교하고 교환하지 않음
- 첫 번째 패스 후 가장 큰 값 90이 배열의 끝으로 이동
- 두 번째 패스 (i=1):
- [34, 25, 12, 22, 11, 64, 90]
- 34와 25를 비교하고 교환 → [25, 34, 12, 22, 11, 64, 90]
- 34와 12를 비교하고 교환 → [25, 12, 34, 22, 11, 64, 90]
- 34와 22를 비교하고 교환 → [25, 12, 22, 34, 11, 64, 90]
- 34와 11를 비교하고 교환 → [25, 12, 22, 11, 34, 64, 90]
- 두 번째 패스 후 두 번째로 큰 값 64가 배열의 끝에서 두 번째로 이동
- 계속 반복:
- 이 과정을 반복하여 배열의 모든 요소가 정렬될 때까지 수행
삽입 정렬(Insertion Sort)
배열을 순회하면서 정렬된 부분과 정렬되지 않은 부분으로 나누고, 정렬되지 않은 부분의 첫 번째 원소를 적절한 위치에 삽입하여 정렬한다.
특징
- 시간 복잡도: O(n ^2)
- 공간 복잡도: O(1)
- 안정 정렬
장점
- 구현이 간단하고 직관적
- 대부분의 경우 작은 데이터셋에 대해 매우 효율적
- 거의 정렬된 데이터에 대해서는 매우 효율적 - O(n)의 시간 복잡도
단점
- 큰 데이터셋에서는 비효율적
예제 및 문제 풀이
문제: 주어진 배열 [12, 11, 13, 5, 6]을 삽입 정렬을 사용하여 오름차순으로 정렬하시오.
풀이
package algorithm.sort;
/* Insert Sort(삽입 정렬)
* 특징
* 시간 복잡도: O(n^2)
* 공간 복잡도: O(1)
* 안정 정렬
*
* 장점
* 구현이 간단하고 직관적, 대부분의 경우 작은 데이터셋에 대해 매우 효율적, 거의 정렬된 데이터에 대해서는 매우 효율적
*
* 단점
* 큰 데이터셋에서는 비효율적
*
* 예제
* 주어진 배열 [12, 11, 13, 5, 6]을 삽입 정렬을 사용하여 오름차순으로 정렬하시오.*/
import java.util.Arrays;
// 풀이
public class InsertSort {
// 삽입 정렬 함수
public static void insertSort(int[] arr) {
int n = arr.length;
// 배열의 각 요소를 반복
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
// key보다 큰 요소들을 한 칸씩 뒤로 이동
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
// key를 올바른 위치에 삽입
arr[j + 1] = key;
}
}
// 메인 함수
public static void main(String[] args) {
int[] arr = {12, 11, 13, 5, 6};
insertSort(arr); // 삽입 정렬 호출
System.out.println(Arrays.toString(arr)); // 정렬된 배열 출력
}
}
Key?
삽입 정렬(Insertion Sort)은 배열의 각 요소를 순차적으로 비교하여 적절한 위치에 삽입하는 방식으로 동작하는 정렬 알고리즘이다.
이 알고리즘에서 key는 현재 정렬할 요소를 나타내며, 이 요소를 앞의 정렬된 부분 배열에서 적절한 위치에 삽입하는 역할을 한다.
삽입 정렬의 동작 방식
- 배열의 두 번째 요소부터 시작하여 각 요소를 key로 선택한다.
- key를 앞의 정렬된 부분 배열과 비교하여 적절한 위치를 찾는다.
- key보다 큰 요소들은 한 칸씩 뒤로 이동시킨다.
- key를 찾은 위치에 삽입한다.
- 이 과정을 배열의 끝까지 반복하여 전체 배열을 정렬한다.
Key의 역할
- key는 현재 정렬할 요소를 나타내며, 정렬된 부분 배열에 삽입될 위치를 찾기 위해 사용된다.
- key를 통해 현재 요소와 앞의 정렬된 요소들을 비교하면서 정렬을 진행한다.
삽입 정렬의 동작 과정
배열 [12, 11, 13, 5, 6]을 삽입 정렬하는 과정
- 초기 배열: [12, 11, 13, 5, 6]
- 첫 번째 패스 (i=1):
- key = 11
- 11을 앞의 정렬된 부분 배열 [12]와 비교
- 12가 11보다 크므로 12를 한 칸 뒤로 이동 → [12, 12, 13, 5, 6]
- key = 11을 적절한 위치에 삽입 → [11, 12, 13, 5, 6]
- 두 번째 패스 (i=2):
- key = 13
- 13을 앞의 정렬된 부분 배열 [11, 12]와 비교
- 13은 이미 적절한 위치에 있음 → [11, 12, 13, 5, 6]
- 세 번째 패스 (i=3):
- key = 5
- 5를 앞의 정렬된 부분 배열 [11, 12, 13]와 비교
- 13이 5보다 크므로 13을 한 칸 뒤로 이동 → [11, 12, 13, 13, 6]
- 12가 5보다 크므로 12를 한 칸 뒤로 이동 → [11, 12, 12, 13, 6]
- 11이 5보다 크므로 11을 한 칸 뒤로 이동 → [11, 11, 12, 13, 6]
- key = 5을 적절한 위치에 삽입 → [5, 11, 12, 13, 6]
- 네 번째 패스 (i=4):
- key = 6
- 6을 앞의 정렬된 부분 배열 [5, 11, 12, 13]와 비교
- 13이 6보다 크므로 13을 한 칸 뒤로 이동 → [5, 11, 12, 13, 13]
- 12가 6보다 크므로 12를 한 칸 뒤로 이동 → [5, 11, 12, 12, 13]
- 11이 6보다 크므로 11을 한 칸 뒤로 이동 → [5, 11, 11, 12, 13]
- key = 6을 적절한 위치에 삽입 → [5, 6, 11, 12, 13]
선택 정렬(Selection Sort)
선택 정렬(Selection Sort)은 단순하지만 비효율적인 정렬 알고리즘으로, 배열에서 가장 작은 (또는 가장 큰) 요소를 선택하여 배열의 앞쪽부터 차례대로 정렬하는 방식으로 동작한다. 이 과정은 반복되며, 배열의 모든 요소가 정렬될 때까지 계속된다.
특징
- 시간 복잡도: O(n ^2)
- 공간 복잡도: O(1) - 제자리 정렬
- 불안정 정렬: 같은 값의 요소들이 순서가 바뀔 수 있음
장점
- 간단한 구현: 선택 정렬은 알고리즘이 매우 직관적이고 구현이 간단하다.
- 적은 메모리 사용: 제자리 정렬 알고리즘으로, 추가적인 메모리 공간을 거의 사용하지 않는다.
- 작은 데이터셋에 적합: 작은 크기의 리스트를 정렬할 때는 그 단순함 덕분에 이해하고 사용하기 쉽다.
단점
- 비효율적: 시간 복잡도가 O(n^2)로, 큰 데이터셋에 대해 매우 비효율적이다.
- 불안정 정렬: 동일한 값의 요소들이 원래의 순서를 유지하지 않을 수 있다.
- 실제로 데이터가 많은 경우 사용되지 않음: 선택 정렬은 학습용으로는 좋지만, 실전에서는 다른 더 효율적인 정렬 알고리즘(예: 퀵 정렬, 병합 정렬, 힙 정렬 등)을 사용하는 것이 일반적이다.
예제 및 문제 풀이
문제: 주어진 배열 [12, 11, 13, 5, 6]을 삽입 정렬을 사용하여 오름차순으로 정렬하시오.
풀이
package algorithm.sort;
/* Selection Sort(선택 정렬)
* 특징
* 시간 복잡도: O(n^2)
* 공간 복잡도: O(1) - 제자리 정렬
* 안정성: 불안정 정렬 - 같은 값의 요소들이 순서가 바뀔 수 있음
*
* 장점
* 간단한 구현, 적은 메모리 사용, 작은 데이터셋에 적합
*
* 단점
* 비효율적, 불안정 정렬, 실제로 데이터가 많은 경우 사용되지 않음
*
* 예제
* 주어진 배열 [64, 25, 12, 22, 11]을 선택 정렬을 사용하여 오름차순으로 정렬하시오.*/
import java.util.Arrays;
// 풀이
public class SelectionSort {
// 선택 정렬 함수
public static void selectionSort(int[] arr) {
int n = arr.length;
// 배열의 모든 요소를 순회
for (int i = 0; i < n - 1; i++) {
// 현재 위치에서 가장 작은 요소를 찾음
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// 가장 작은 요소를 현재 위치와 교환
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
// 메인 함수
public static void main(String[] args) {
int[] arr = {64, 25, 12, 22, 11};
selectionSort(arr); // 선택 정렬 호출
System.out.println(Arrays.toString(arr)); // 정렬된 배열 출력
}
}
동작 과정 설명
- 초기 배열: [64, 25, 12, 22, 11]
- 첫 번째 패스 (i=0):
- i=0에서 시작하여 가장 작은 요소를 찾음
- minIndex = 0 (현재 최소값: 64)
- j=1: 25 < 64, minIndex = 1
- j=2: 12 < 25, minIndex = 2
- j=3: 22 < 12, minIndex = 2
- j=4: 11 < 12, minIndex = 4
- 가장 작은 요소 11을 현재 위치 64와 교환
- 배열 상태: [11, 25, 12, 22, 64]
- 두 번째 패스 (i=1):
- i=1에서 시작하여 가장 작은 요소를 찾음
- minIndex = 1 (현재 최소값: 25)
- j=2: 12 < 25, minIndex = 2
- j=3: 22 < 12, minIndex = 2
- j=4: 64 < 12, minIndex = 2
- 가장 작은 요소 12를 현재 위치 25와 교환
- 배열 상태: [11, 12, 25, 22, 64]
- 세 번째 패스 (i=2):
- i=2에서 시작하여 가장 작은 요소를 찾음
- minIndex = 2 (현재 최소값: 25)
- j=3: 22 < 25, minIndex = 3
- j=4: 64 < 22, minIndex = 3
- 가장 작은 요소 22를 현재 위치 25와 교환
- 배열 상태: [11, 12, 22, 25, 64]
- 네 번째 패스 (i=3):
- i=3에서 시작하여 가장 작은 요소를 찾음
- minIndex = 3 (현재 최소값: 25)
- j=4: 64 < 25, minIndex = 3
- 배열 상태는 변하지 않음: [11, 12, 22, 25, 64]
이 과정을 통해 전체 배열이 정렬된다. 각 패스마다 가장 작은 요소를 선택하고 현재 위치와 교환하여 배열을 정렬한다. 선택 정렬은 단순하고 이해하기 쉽지만, 시간 복잡도가 O(n^2)로 효율적이지 않기 때문에 큰 데이터셋에는 적합하지 않다.
'항해 99 > Java' 카테고리의 다른 글
| 자바 - 탐색 알고리즘, 그래프 알고리즘 (0) | 2024.08.22 |
|---|---|
| Java - Nested, Inner Class (0) | 2024.08.14 |
| Java - 날짜와 시간 (0) | 2024.07.26 |
| Java - ENUM (0) | 2024.07.18 |
| Java - Wrapper, Class, System, Math, Random (0) | 2024.06.13 |
