지난 글에서 기본정렬에 대해서 알아보았습니다 !
이번 글에서는 고급 정렬을 정리해보겠습니다 !
( 지난번과 같이 오름차순을 기준으로설명하겠습니다. )
고급 정렬에는 병합 정렬, 퀵 정렬, 힙 정렬, 셸 정렬이 있습니다.
그럼 순서대로 개념 정리를 해보고, java 로 구현한 예시 코드도 소개하도록 하겠습니다.
병합 정렬 ( Merge Sort )
분할, 정복, 결합으로 정렬하는 알고리즘
정렬 과정
분할 : 데이터 배열을 같은 크기의 2개의 부분 배열로 분할합니다.
→ 정복 : 부분 배열의 크기가 1이 될때까지 순환 호출로 분할을 반복해서 합니다. 부분 배열의 크기가 1이 되면 부분 배열을 정렬합니다.
→ 결합 : 정렬된 부분 배열을 하나의 배열에 합병합니다.
결합할 때에는 왼쪽 부분 배열과 오른쪽 부분 배열의 맨 앞 데이터를 서로 비교하고 더 작은 쪽을 정렬될 배열 안에 차곡차곡 넣어줍니다. 왼쪽 부분 배열과 오른쪽 부분 배열에 들어있는 데이터가 없을때까지 반복해줍니다.
시간 복잡도는 O(nlogn)입니다.
퀵 정렬 ( Quick Sort )
pivot을 기준으로 부분 리스트를 정렬하는 알고리즘
정렬 과정
리스트 안의 한개의 데이터를 선택합니다. 이 데이터를 pivot이라고 부릅니다.
→ pivot을 기준으로 pivot보다 작은 데이터는 왼쪽, 큰 데이터는 오른쪽으로 나눕니다.
→ pivot을 제외한 왼쪽 배열과 오른쪽 배열을 다시 정렬해줍니다. 이때, 부분 배열에서 순환 호출을 하여 각 부분 배열에서도 pivot을 선택하고 부분 배열을 나누는 과정을 반복합니다.
→ 부분 배열의 크기가 0 혹은 1이 될때까지 반복해줍니다.
부분 배열을 나누고 나누면서 크기가 작아지면서 동시에 정렬도 진행되게 됩니다.
부분 배열의 크기가 0 혹은 1이 될때까지 반복해주다보면 정렬이 끝나게 됩니다.
시간 복잡도는 O(nlogn)입니다.
힙 정렬 ( Heap Sort )
최대 힙 트리 혹은 최소 힙 트리를 구성하여 정렬하는 알고리즘
* 힙 : 완전 이진 트리. 최대 힙( 부모 노드 키 값 >= 자식 노드 키 값 ) , 최소 힙( 부모 노드 키 값 <= 자식 노드 키 값 )
정렬 과정
정렬해야 할 n개의 데이터들로 최대 힙 트리를 만듭니다.
→ 최대 힙의 루트 노드를 배열의 마지막 값과 교환합니다. ( = 가장 큰 값을 마지막 배열에 저장 )
→ 가장 크고 마지막 배열에 있는 값을 힙에서 제거해줍니다.
→ 힙을 재구조화 시켜줍니다. ( 남은 값에서 가장 큰 값이 루트 노드로 가게됨 )
→ 위의 과정을 반복해줍니다.
시간 복잡도는 O(nlogn)입니다.
이해를 돕기 위한 최소 힙 트리와 최대 트리 예시입니다.
셸 정렬 ( Shell Sort )
삽입 정렬을 보완한 알고리즘
정렬 과정
정렬해야 할 배열을 일정한 기준에 따라 나눠줍니다
→ 연속적이지 않은 여러 개의 부분 배열을 만들어줍니다.
→ 각 부분 배열을 삽입 정렬을 이용해 정렬합니다.
→ 모든 부분 배열이 정렬된 후 전체 배열을 이전보다 적은 개수의 부분 배열로 만들어줍니다.
→ 각 부분 배열을 삽입 정렬을 이용해 정렬합니다.
→ 위의 과정을 부분 배열의 크기가 1이 될 때까지 반복합니다.
시간 복잡도는 O(nlogn)입니다.
병합 정렬
import java.util.Scanner;
public class MergeSort {
public static int[] sorted; // 임시배열
// 분할하는 코드 -> 분할하다가 배열 안의 데이터가 1개면 멈추도록
private static void mergeSort(int[] src,int left, int right) {
if( left < right ) {
int mid = (left + right) / 2;
// 재귀 ( 왼쪽 부분 리스트와 오른쪽 부분 리스트로 나누어져서 각각 또 나누고, 나누고,, 반복 )
mergeSort(src, left, mid);
mergeSort(src, mid+1, right);
int l = left; // 왼쪽 부분 배열 맨 앞 인덱스
int r = mid + 1; // 오른쪽 부분 배열 맨 앞 인덱스
int index = l; // 데이터를 정렬할 최종 배열의 인덱스( 맨앞부터 채운다 )
while(l <= mid || r <= right) { // 왼쪽 부분 배열과 오른쪽 부분 배열이 맨 끝 인덱스일때 까지만
// 오른쪽 배열이 다 정렬되어 없어지거나 왼쪽 배열 앞자리가 끝까지 간 상태에서 왼쪽 배열 데이터가 오른쪽 데이터보다 작은 경우
if(r > right || (l <= mid && src[l] < src[r])) {
// 값이 더 작은 왼쪽 배열의 맨 앞을 최종 배열 맨앞부터 채워준다
sorted[index] = src[l];
index++;
l++;
} // 반대의 경우 오른쪽 배열의 맨 앞을 최종 배열에 채워준다.
else {
sorted[index] = src[r];
index++;
r++;
}
} // 왼쪽 부분 배열과 오른쪽 부분 배열의 모든 데이터를 병합하게되면
// 맨 처음 값부터 끝까지 정렬된 값을 원래 배열에 넣어준다.
for ( int i = left; i <= right; i++) {
src[i] = sorted[i];
}
}
}
public static void printArray(int[] arr) {
for (int i=0;i<arr.length;i++)
System.out.print(arr[i]+" ");
System.out.println();
}
public static void main(String []args) {
Scanner sc = new Scanner(System.in);
System.out.println("정렬할 데이터의 갯수를 입력하시오.");
int n = sc.nextInt();
int[] src = new int[n];
for(int i = 0; i < n; i++) {
src[i] = sc.nextInt();
}
MergeSort.sorted = new int[n];
printArray(src);
// 정렬할 데이터 리스트, 시작 인덱스, 마지막 인덱스
mergeSort(src, 0, n-1);
printArray(src);
}
}
퀵 정렬
import java.util.Scanner;
public class QuickSort {
public static void quickSort(int[] arr, int left, int right) {
if (left >= right) {
return;
}
int pivot = arr[right];
int sortedIndex = left;
for (int i = left; i < right; i++) {
if (arr[i] <= pivot) {
swap(arr, i, sortedIndex);
sortedIndex++;
}
}
swap(arr, sortedIndex, right);
quickSort(arr, left, sortedIndex - 1);
quickSort(arr, sortedIndex + 1, right);
}
private static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
public static void printArray(int[] arr) {
for (int i=0;i<arr.length;i++)
System.out.print(arr[i]+" ");
System.out.println();
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("정렬할 데이터의 갯수를 입력하시오.");
int n = sc.nextInt();
int[] src = new int[n];
for(int i = 0; i < n; i++) {
src[i] = sc.nextInt();
}
printArray(src);
// 정렬할 데이터 리스트
quickSort(src, 0, src.length-1);
printArray(src);
}
}
힙 정렬
import java.util.Arrays;
import java.util.Scanner;
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 temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
// 변경된 부분을 다시 최대 힙으로 재구조화
heapify(arr, n, largest);
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("정렬할 데이터의 갯수를 입력하시오.");
int n = sc.nextInt()+1;
int[] arr = new int[n];
for(int i = 1; i < n; i++) {
arr[i] = sc.nextInt();
}
System.out.println(Arrays.toString(arr));
heapSort(arr);
System.out.println(Arrays.toString(arr));
}
}
셸 정렬
import java.util.Arrays;
import java.util.Scanner;
public class ShellSort {
public static void shellSort(int[] arr) {
int n = arr.length;
// 셸 정렬 간격(gap)을 초기화시켜준다
for (int gap = n / 2; gap > 0; gap /= 2) {
// 간격을 기준으로 삽입 정렬해준다
for (int i = gap; i < n; i++) {
int temp = arr[i];
int j = i;
while (j >= gap && arr[j - gap] > temp) {
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = temp;
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("정렬할 데이터의 갯수를 입력하시오.");
int n = sc.nextInt()+1;
int[] arr = new int[n];
for(int i = 1; i < n; i++) {
arr[i] = sc.nextInt();
}
System.out.println(Arrays.toString(arr));
shellSort(arr);
System.out.println(Arrays.toString(arr));
}
}'알고리즘' 카테고리의 다른 글
| [ 알고리즘 ] DP(Dynamic Programming) - 동적계획법 (1) | 2024.02.01 |
|---|---|
| [알고리즘] 자료구조 - 특수 정렬 ( 계수 정렬, 기수 정렬, 버킷 정렬 ) (0) | 2023.07.17 |
| [알고리즘] 자료구조 - 기본 정렬 ( 선택 정렬, 버블정렬, 삽입 정렬 ) (2) | 2023.07.16 |
| 정렬 알고리즘 (0) | 2023.03.26 |
