더 빠르게 정렬할 수는 없을까?
기존의 정렬의 시간 복잡도는 O(n^2) 걸리지만
오늘 배울 합병 정렬과 퀵 정렬은 시간 복잡도가 O(n log n)이 걸리게 된다.
두 정렬은 모두 재귀를 사용하게 된다.
재귀 함수 디자인의 과정
1. 작성하려는 함수의 역할을 말로 명확하게 정의한다.
2. 함수가 기저 조건에서 제대로 동작하게 작성한다.
3. 함수가 제대로 동작한다고 가정하고 함수를 완성한다.
4. 함수를 완성한 후, 기저 조건으로 수렴함을 보인다.
합병 정렬
배열을 절반으로 나누어 각각을 정렬한 후, 합친다.
T(n) = n개의 숫자를 합병 정렬할 때의 시간 복잡도
1. 왼쪽 합병 정렬 = T(n/2)
2. 오른쪽 합병 정렬. = T(n/2)
3. 합친다. = O(n)
점화식 = T(n) =2*T(n/2)+O(n)
따라서 T(n) = O(n log n)이라는 시간 복잡도를 가지게 된다.
합병 정렬 구현 코드
import java.util.Scanner;
//합병정리
public class Main {
static int n;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
int[] arr = new int[n];
for (int i=0;i<n;i++){
arr[i] = sc.nextInt();
}
mergeSort(arr,0,n-1);
for (int i=0;i<n;i++){
System.out.printf("%d ",arr[i]);
}
}
static void mergeSort(int[] arr, int start, int end){
//원소가 1개남을때
if (start>=end)return;
else {
// 왼쪽 절반을 합병정렬
// 오른쪽 절반을 합병정렬
// 합침
int mid = (start+end)/2;
mergeSort(arr,start,mid);
mergeSort(arr,mid+1,end);
//시작부터 미드, 미드부터 끝은 정렬됨
merging(arr,start,mid,mid+1,end);
}
}
static void merging(int[] arr, int s1,int e1,int s2,int e2){
//arr의 s1~e1이 왼쪽절반, s2~e2가 오른쪽 절반일때,
//이둘을 합쳐서 arr의 s1~e2를 정렬된 결과로 만드는 함수
int p,q;
int[] temp =new int[n];
int tempindex =0;
p=s1;
q=s2;
while (p<=e1&&q<=e2){
if (arr[p]<=arr[q]){
temp[tempindex++]=arr[p];
p++;
}
else {
temp[tempindex++]=arr[q];
q++;
}
}
if (p>e1){
for (int i=q;i<=e2;i++){
temp[tempindex++]= arr[i];
}
}
else{
for (int i=p;i<=e1;i++){
temp[tempindex++]=arr[i];
}
}
//temp는 완성됨
//arr[s1~e2]까지 temp를 복사
for (int i=s1;i<=e2;i++){
arr[i] = temp[i-s1];
}
}
}위 코드를 분석해보자.
배열에 값을 넣고, 재귀 함수를 만든다.
기저 조건은 원소가 1개 이하로 남았을 때이다.
왼쪽 절반을 합병 정렬하고, 오른쪽 절반을 합병 정렬하고 합치는 과정이 필요하다.
절반을 나누는 것은 (start+end)/2로 한다.
합치는 매서드 merging을 보자.
p와 q는 두 개로 나눈 배열의 현재 index를 나타낸다.
예를 들어 나눈 값이 1 3 5 5 || 2 4 6 8이라고 해보자.
처음 p는 1을 나타내고, q는 2를 나타낸다.
두배 열에서 작은 값을 차례대로 temp에 넣게 된다.
그러면 1 2 3 4 5 5에서 반복문은 끝나게 된다.
p가 인덱스를 넘어섰기 때문이다.
그래서 이후 남아있는 값들을 temp 배열에 넣어준다.
퀵 정렬
원소를 하나 정하여, 해당 원소보다 작은 수들과 큰 수들로 나눈다.
1. pivot의 위치를 확정시킨다.
2. pivot의 왼쪽과 오른쪽의 자리가 바뀌지 않는다.
T(n) = n개의 숫자를 퀵 정렬로 정렬하는 데 걸리는 시간
1. pivot을 정한다. = O(1)
2. 작거나 같은 값과 큰 값을 분류한다. =. O(n)
3. 각각을 퀵 정렬한다. -> pivot이 원소의 개수를 절반으로 나눈다고 가정한다. T(n) = 2T(n/2) +O(n)
퀵 정렬은 평균적으로 T(n) = O(n log n)의 시간 복잡도를 갖게 된다.
최악의 경우에는 O(n^2)이 걸리게 된다.
퀵 정렬의 구현 코드
import java.util.Arrays;
import java.util.Scanner;
//퀵정렬
public class Main{
static int n;
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
n =sc.nextInt();
int[] arr = new int[n];
for (int i=0;i<n;i++){
arr[i] = sc.nextInt();
}
quickSort(arr,0,n-1);
System.out.println(Arrays.toString(arr));
}
static void quickSort(int arr[],int start, int end){
//arr를 스타트 부터 엔드까지 퀵정렬하는 함수
if (start>=end)return;
int pivot = arr[start];
int[] left = new int[n];
int[] right = new int[n];
int leftcount = getLeft(arr,start+1,end,pivot,left);
int rightcount = getRight(arr,start+1,end,pivot,right);
for (int i=0;i<leftcount;i++){
arr[start+i] = left[i];
}
arr[start+leftcount]=pivot;
for (int i=0;i<rightcount;i++){
arr[start+leftcount+1+i] = right[i];
}
quickSort(arr,start,+start+leftcount-1);
quickSort(arr,start+leftcount+1,end);
}
static int getLeft(int arr[] , int start, int end, int pivot, int result[]){
//arr의 스타트부터 엔드까지 숫자들중에서
//pivot보다 작거나 작은 값을 result에 대입
//또한 큰수의 개수도 반환
int index =0;
for (int i=start;i<=end;i++){
if (arr[i]<=pivot){
result[index++]= arr[i];
}
}
return index;
}
static int getRight(int arr[] , int start, int end, int pivot, int result[]){
//arr의 스타트부터 엔드까지 숫자들중에서
//pivot보다 큰 값을 result에 대입
//또한 작은 수의 개수도 반환
int index =0;
for (int i=start;i<=end;i++){
if (arr[i]>pivot){
result[index++]= arr[i];
}
}
return index;
}
}위 코드를 분석해보자.
배열에 값을 넣는다.
arr를 시작점부터 끝까지 퀵 정렬하는 재귀 함수를 만든다.
기저 조건은 원소가 1개 이하로 남았을 때이다.
우선 pivot을 선정한다.
이후 pivot을 기준으로 왼쪽과 오른쪽으로 나눈다.
왼쪽의 경우에는 pivot보다 작거나 같은 경우에 해당하고,
오른쪽의 경우에는 큰 경우에 해당한다.
왼쪽과 오른쪽을 나눈 다음 배열에 값을 넣고, 개수도 반환해준다.
개수도 반환해주는 이유는 arr를 pivot기준으로 정렬하기 위함이다.
이를 반복하면 원소가 1개 이하로 남게 되는 데, 이는 정렬이 되었다는 것이다.
개선점이나 오류가 있다면, 댓글 부탁드립니다.
