[알고리즘] 고급 정렬알고리즘
병합 정렬알고리즘
하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두개의 정렬 된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 알고리즘
- 배열을 반반으로 나눈다
- 각각 독립적으로 정렬한다
- 병합한다 (정렬완료)
병합 정렬에서 실제로 정렬이 이루어지는 시점은 2개의 리스트를 병합하는 단계이다.
퀵 정렬알고리즘
정렬 알고리즘 중 가장 많이 사용되는 알고리즘
기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작
분할 정복 알고리즘이다
- 리스트 안에 있는 한 요소를 선택한다. 이렇게 고른 원소를 피벗(pivot) 이라고 한다
- 피벗을 기준으로 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮겨지고 피벗보다 큰 요소들은 모두 피벗의 오른쪽으로 옮겨진다
- 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬한다
- 분할된 부분 리스트에 대하여 순환 호출을 이용하여 정렬을 반복한다
- 부분 리스트에서도 다시 피벗을 정하고 피벗을 기준으로 2개의 부분 리스트로 나누는 과정을 반복한다
- 부분 리스트들이 더 이상 분할이 불가능할 때까지 반복한다
퀵 정렬(quick sort)알고리즘의 구체적 개념
하나의 리스트를 피벗(pivot)을 기준으로 두 개의 비균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다.
퀵 정렬은 다음의 단계들로 이루어진다.
- 분할(Divide): 입력 배열을 피벗을 기준으로 비균등하게 2개의 부분 배열(피벗을 중심으로 왼쪽: 피벗보다 작은 요소들, 오른쪽: 피벗보다 큰 요소들)로 분할한다.
- 정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출 을 이용하여 다시 분할 정복 방법을 적용한다.
- 결합(Combine): 정렬된 부분 배열들을 하나의 배열에 합병한다.
순환 호출이 한번 진행될 때마다 최소한 하나의 원소(피벗)는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.
import java.util.*;
public class Main {
public static void quickSort(int[] arr, int start, int end) {
if (start >= end) return; // 원소가 1개인 경우 종료
int pivot = start; // 피벗은 첫 번째 원소
int left = start + 1;
int right = end;
while (left <= right) {
// 피벗보다 큰 데이터를 찾을 때까지 반복
while (left <= end && arr[left] <= arr[pivot]) left++;
// 피벗보다 작은 데이터를 찾을 때까지 반복
while (right > start && arr[right] >= arr[pivot]) right--;
// 엇갈렸다면 작은 데이터와 피벗을 교체
if (left > right) {
int temp = arr[pivot];
arr[pivot] = arr[right];
arr[right] = temp;
}
// 엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체
else {
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
}
// 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
quickSort(arr, start, right - 1);
quickSort(arr, right + 1, end);
}
public static void main(String[] args) {
int n = 10;
int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};
quickSort(arr, 0, n - 1);
for(int i = 0; i < n; i++) {
System.out.print(arr[i] + " ");
}
}
}
힙 정렬알고리즘
최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법
내림차순 정렬 - 최대 힙
오름차순 정렬 - 최소 힙
자료구조 힙(heap)
완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조
최댓값, 최솟값을 쉽게 추출할 수 있는 자료구조
과정
- 정렬해야 할 n개의 요소들로 최대 힙(완전 이진 트리 형태)을 만든다.
- 내림차순을 기준으로 정렬
- 그 다음으로 한 번에 하나씩 요소를 힙에서 꺼내서 배열의 뒤부터 저장하면 된다.
- 삭제되는 요소들(최댓값부터 삭제)은 값이 감소되는 순서로 정렬되게 된다.
기수 정렬알고리즘
계수 정렬(Counting Sort) 와 마찬가지로 비교연산을 수행하지 않아 조건이 맞는 상황에서 빠른 정렬 속도를 보장하는 알고리즘
데이터의 각 자릿수를 낮은 자리수에서부터 가장 큰 자리수까지 올라가면서 정렬을 수행
자릿수가 존재하지 않는 데이터를 기수정렬로 정렬하는 것은 불가능
현재 가지고 있는 데이터 중 가장 큰 자릿수가 100의 자리일때
- 각 데이터들의 1의 자리를 비교해서 같은 데이터끼리 모은다
- 1의 자리가 작은 데이터들이 앞에 위치하게 되고 큰 숫자들이 뒤에 위치하게 된다(오름차순 기준)
- 이때 같은 자릿수에 여러 데이터가 있을 경우에는 입력된 순서(나열된 순서)로 데이터를 모은다
- 2번까지 과정을 마치면 1의 자리가 가장 작은 숫자부터 가장 큰 숫자 순으로 데이터들이 정렬된다
- 10의 자리가 같은 데이터끼리 오름차순으로 나열한다
- 10보다 작은 숫자들은 배열에 위치했던 순서대로 새로운 정렬의 제일 앞에 위치하게 된다
- 100의 자리가 같은 데이터끼리 오름차순으로 나열한다
- 100보다 작은 숫자들은 배열의 제일 앞에서부터 순서대로 채운다
- 데이터들의 최대 자릿수가 100으 자리이기 때문에 더 이상 진행하지 않고 종료한다
계수 정렬알고리즘
Օ(n+데이터의 최대값 k)의 속도가 보장되는 정렬 알고리즘
배열 내에 특정한 값이 몇번 등장했는지에 따라 정렬을 수행하기 때문에 비교연산이 사용되지 않는다
- 입력받은 배열 A의 요소값들의 등장횟수를 저장할 배열 B와 최종적으로 정렬된 값들을 담을 배열 C를 준비한다
- 입력받은 배열에서 값을 하나씩 꺼내서 해당 값을 배열 B의 인덱스로 사용해 B의 요소 값을 하나 증가시킨다
- B가 완성되면 B의 각 요소들을 누적합으로 갱신한다
- A의 가장 뒤에서 부터 값을 하나씩 꺼내서 해당값을 B의 인덱스로 사용하고 참조된 B의 값을 배열 C의 인덱스로 사용해서