[자료구조] 고급 정렬 - 병합 정렬, 퀵 정렬, 힙 정렬, 셸 정렬이란?
👾병합 정렬(Merge Sort)이란?
- 분할(Divide)
- 정복(Conquer)
- 병합(Merge)
병합 정렬 알고리즘 예제
병합 정렬 알고리즘 코드(JAVA)
public class MergeSort {
public static void mergeSort(int arr[]) {
if (arr.length <= 1) {
return;
}
int mid = arr.length/2; //배열의 중간 값 저장
int left[] = new int[mid]; //배열을 반으로 나눈 후 왼쪽 값
int right[] = new int[arr.length-mid]; //배열을 반으로 나눈 후 오른쪽 값
//배열을 두개의 배열로 저장
for (int i=0; i<mid; i++) {
left[i] = arr[i];
}
for (int i=mid; i<arr.length; i++) {
right[i-mid] = arr[i];
}
//왼쪽 배열 재귀적으로 정렬
mergeSort(left);
mergeSort(right);
merge(arr, left, right);
int i = 0, j = 0, t = 0;
while(i < left.length && j < right.length) {
//왼쪽 배열i번째가 오른쪽 배열i번째 보다 작을 경우
if(left[i] <= right[j]) {
//왼쪽 배열 i+1번째가 arr 배열 i+1번째로 들어간다.
arr[t++] = left[i++];
}
else {
arr[t++] = right[j++];
}
}
}
public static void merge(int[] arr, int[] left, int[] right) {
int i = 0, j = 0, t = 0;
while(i < left.length && j < right.length) {
//왼쪽 배열i번째가 오른쪽 배열i번째 보다 작을 경우
if(left[i] <= right[j]) {
//왼쪽 배열 i+1번째가 arr 배열 i+1번째로 들어간다.
arr[t++] = left[i++];
}
else {
arr[t++] = right[j++];
}
}
//위에 while문이 끝났을 때
//left가 right보다 클 경우 j가 계속 +1씩 추가되면서 right배열만 arr문에 들어가 있을 것이다.
//그때 남은 left배열을 arr 배열에 넣어 주기 위해서 while문을 또 돌려준다.
while (i< left.length) {
arr[t++] = left[i++];
}
//right가 left보다 클 경우엔 right배열에 남으니 while문을 통해 남은 배열들을 arr배열에 넣어준다.
while (j< right.length) {
arr[t++] = right[j++];
}
}
public static void main(String[] args) {
MergeSort sort = new MergeSort();
int arr[] = {31, 3, 65, 73, 8, 11, 20, 29, 48, 15};
mergeSort(arr);
for(int i=0; i<arr.length; i++) {
System.out.print(arr[i]+" ");
}
}
}- 병합정렬의 시간 복잡도는 O(n log n)입니다. 안정적인 정렬 알고리즘이라는 장점이 있습니다.
- 단점은 임시 배열을 사용하므로 추가 공간이 필요하다는 점입니다.
✈️퀵 정렬(Quick Sort)이란?
- 퀵 정렬(Quick Sort)은 분할 정복(Divide and Conquer) 방식을 사용하여 정렬을 수행하는 알고리즘입니다.
- 평균적으로 매우 빠른 실행 속도를 가지며, 널리 사용되는 정렬 알고리즘 중 하나입니다.
퀵 정렬 알고리즘 예제
퀵 정렬 알고리즘 코드(JAVA)
public class QuickSort {
//자리를 교체해주는 메소드
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void quickSort(int[] arr, int low, int high) {
//만약 low가 high보다 작을 경우
if(low < high) {
//pivot의 인덱스를 가지고 오기
int pivotIndex = partition(arr, low, high);
//pivot을 기준으로 왼쪽과 오른쪽 부분 배열을 재귀적으로 정렬
quickSort(arr, low, pivotIndex - 1);
quickSort(arr, pivotIndex+1, high);
}
}
public static int partition(int[] arr, int low, int high) {
//피벗을 배열의 첫번째 요소로 선택
int pivot = arr[high];
//피벗을 기준으로 작은 요소들은 왼쪽으로, 큰 요소들은 오른쪽이로 이동
int i = low - 1;
for(int j = low; j < high; j++) {
if(arr[j] < pivot) {
i++;
//자리 교체
swap(arr, i, j);
}
}
swap(arr, i+1, high);
return i+1;
}
public static void main(String[] args) {
int arr[] = {6,4,9,5,3};
quickSort(arr, 0, arr.length - 1);
//arr출력
for(int num:arr) {
System.out.println(num);
}
}
}- 퀵 정렬은 분할 정복 방식을 사용하기 때문에 매우 빠른 실행 속도를 가집니다.
- 평균적으로 시간 복잡도는 O(n log n)이며, 최악의 경우에는 O(n^2)입니다.
- 그러나 퀵 정렬은 대부분의 경우에 매우 효율적이며, 다른 정렬 알고리즘보다 우수한 성능을 보입니다.
🌟힙 정렬(Heap Sort)이란?
- 힙 정렬(Heap Sort)은 힙(Heap) 자료구조를 기반으로 정렬을 수행하는 알고리즘입니다.
- 힙은 완전 이진 트리(Complete Binary Tree)의 일종으로, 힙 속성(Heap Property)을 유지하는 자료구조입니다.
- 힙 속성을 이용하여 배열을 정렬하는 방법으로, 빠른 실행 속도와 효율적인 메모리 사용을 특징으로 합니다.
힙 정렬 알고리즘 예제
힙 정렬 알고리즘 코드(JAVA)
public class HeapSort {
public static void heap(int[] arr, int n, int i) {
//현재 노드를 가장 큰 값으로 설정
int largest = i;
//왼쪽 자식 노드의 인덱스
int left = 2*i+1;
//오른쪽 자식 노드의 인덱스
int right = 2*i+2;
//왼쪽 자식이 힙 범위 내에서 현재 노드보다 크면 larger값을 업데이트
if(left<n && arr[left]>arr[largest]) {
largest = left;
}
//오른쪽 자식이 힙 범위 내에서 현재 노드보다 크다면 largest값을 업데이트
if(right<n && arr[right]>arr[largest]) {
largest = right;
}
//largest값이 업데이트가 되었다면 현재 노드와 largest 노드를 교환
if(largest != i) {
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
//교환 후에도 힙 속성을 유지하기 위해 재귀적으로 heep작업을 수행
heap(arr, n, largest);
}
}
public static void main(String[] args) {
int arr[] = {6,5,1,10,7};
int n = arr.length;
//초기 힙 구성
for(int i=n/2-1; i>=0; i--) {
//힙 속성을 유지하기 위해 heap작업을 수행
heap(arr, n, i);
}
//힙에서 요소를 하나씩 꺼내어 정렬
for(int i=n-1; i>0; i--) {
//가장 큰 요소와 마지막 요소를 교환
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heap(arr, i, 0);
}
//arr출력
String []in = {"1번째","2번째","3번재","4번째","5번째"};
for(int num:arr) {
System.out.println(num + " ");
}
}
}- 힙 정렬의 시간 복잡도는 O(n log n)입니다.
- 평균적으로 다른 비교 기반 정렬 알고리즘과 동일한 시간 복잡도를 가지지만, 최악의 경우에도 O(n log n)의 실행시간입니다.
- 그러나 힙 정렬은 추가적인 메모리 공간을 사용하여 힙을 구성해야 한다는 단점이 있습니다.
🦝셸 정렬(Shell Sort)이란?
- 셸 정렬(Shell Sort)은 삽입 정렬(Insertion Sort)을 개선한 정렬 알고리즘입니다.
- 삽입 정렬의 단점을 보완하여 더욱 효율적인 정렬을 수행할 수 있습니다.
- 정렬해야 할 리스트의 각 k번째 요소를 추출해서 부분 리스트를 만듭니다.(k는 홀수로 하는 것이 좋습니다.)
- k의 간격이 1이 될때까지 반복합니다.
셸 정렬 알고리즘 예제
쉘 정렬 알고리즘 코드(JAVA)
public class ShellSort {
public static void main(String[] args) {
int arr[] = {6,5,1,10,7};
int n = arr.length;
//셸 정렬의 간격을 결정
int gap = n/2;
while(gap > 0) {
//간격에 따라 부분 배열을 생성하여 삽입 정렬을 수행
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;
}
//간격을 절반으로 줄인다.
gap /= 2;
}
//arr출력
String []in = {"1번째","2번째","3번재","4번째","5번째"};
for(int num:arr) {
System.out.println(num + " ");
}
}
}- 셸 정렬의 시간 복잡도는 최선의 경우에는 O(n log n)이지만, 최악의 경우에는 O(n^2)입니다.
- 그러나 평균적으로 O(n log n) 이하의 성능을 보이기 때문에 대체로 빠른 정렬 알고리즘 중 하나로 알려져 있습니다.