[알고리즘] 정렬(Sort) 심화

💡알고리즘은 입력, 출력, 유한성, 명백성, 효과성을 만족해야 한다.

병합 정렬(Merge Sort)

분할 정복 방법으로 , 하나의 큰 문제를 두 개의 작은 문제로 분할한 뒤에 각자 계산하고 나중에 합치는 방법을 채택한다. 즉, 무조건 반으로 나누고 나중에 정렬하는 알고리즘이므로 $O(N*log_{2}{N})$을 항상 보장한다. 

하지만 기존의 데이터를 담을 추가 배열이 필요하다는 점에서 메모리 활용이 비효율적일 수 있다.


백준 2750

package Y2023.March.week2;

import java.util.Scanner;

public class q2750 {

    static int[] sorted;
    
    static void merge(int[] sort, int start, int mid, int end){
        int[] arr = sort.clone();
        int i = start;
        int j = mid+1;
        int k = start;
        while(k<=end){
            if(i>mid){
                sorted[k] = arr[j++];
            }else if(j>end){
                sorted[k] = arr[i++];
            }else if(arr[i]<arr[j]){
                sorted[k] = arr[i++];
            }else{
                sorted[k] = arr[j++];
            }
            k++;
        }
    }
    
    static void mergeSort(int[] arr, int start, int end){
        if(start < end){
            int mid = (start+end)/2;
            mergeSort(arr, start, mid);
            mergeSort(arr, mid+1, end);
            merge(arr, start, mid, end);
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();
        int len = sc.nextInt();
        sorted = new int[len];
        for(int i=0; i<len; i++){
            sorted[i] = sc.nextInt();
        }
        mergeSort(sorted, 0, len-1);
        for(int i=0; i<len; i++){
            sb.append(sorted[i]).append("\n");
        }
        System.out.println(sb);
}

힙 정렬(Heap Sort)

힙 트리 구조를 이용하는 정렬 방법이다. 병합정렬, 퀵정렬과 마찬가지로 $O(N*log_{2}{N})$의 시간복잡도를 가진다.
🔗힙(Heap)이란?

1. 모든 원소(N)를 기준으로 최대 힙을 만든다(최대 힙 생성 알고리즘).

   1. 자식 노드가 없는 노드를 제외하고 가장 끝의 부모 노드부터 자식 노드들과 비교한다.
      • 이때 부모 노드는 (자식 노드)/2 인덱스에 있으므로 모든 부모 노드는 힙 크기의 절반 인덱스까지만 존재한다. 따라서 원소의 길이/2 인덱스부터 앞으로 이동하면 부모 노드만 선택된다.
   2. 자식 노드가 부모 노드보다 크면 서로 교환한다.
   3. 한 칸씩 올라가며 진행한다.

2. 최대 힙의 루트 즉 최댓값을 맨 뒤 원소와 바꿔준다.

3. 맨 뒤 원소 즉, 최댓값을 제외한 나머지 원소로 최대 힙을 만든다(최대 힙 삭제 알고리즘).

   1. 루트 노드부터 시작하여 부모노드를 자식 노드들과 비교하여 더 큰 값과 교환한다.
   2. 교환한 위치에서 다시 자식 노드들과 비교하여 더 큰 값과 교환한다.
   3. 자식노드 중 더 큰 값이 없을 때까지 반복한다.

4. 2,3번의 과정을 반복하여 정렬한다.

힙 정렬은 "힙 생성 알고리즘(Heapify Algorithm)"을 이용한다. 힙 구조를 한 번 생성하려면 높이만큼만 반복하면 되기 때문에 $O(logN)$의 시간복잡도를 가진다. 그다음 각 노드를 한 번씩 Heapify를 거치면서 N만큼 곱해야 하므로 $N*logN$번 수행하면 정렬이 되는 것이다.

힙 정렬은 병합 정렬과 다르게 추가적인 메모리가 필요하지 않다는 점에서 효율적이다. 하지만 속도만 비교한다면 퀵 정렬이 더 빠르다.

계수 정렬(Counting Sort)

크기를 기준으로 개수를 세는 알고리즘이다. 때문에 범위 조건이 있는 경우에 한해서 굉장히 빠른 $O(N)$의 시간 복잡도를 가진다.

1. 최대 원소의 값을 길이로 하는 배열을 생성하고 하나씩 차례대로 해당 수에 맞는 인덱스에 개수를 +1 한다.

2. 처리가 다 끝나면 인덱스의 값 즉, 개수만큼 반복하여 출력한다.

매우 빠르지만 값 자체의 범위가 메모리에 표현할 수 있어야 한다.


백준 15688

package Y2023.March.week2;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Scanner;

public class q15688 {

    public static void main(String[] args) throws IOException {
        //Scanner sc = new Scanner(System.in);
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int len = Integer.parseInt(br.readLine());
        int[][] arr = new int[2][1000001];
        Arrays.fill(arr[0],0);
        Arrays.fill(arr[1],0);
        int in;
        for (int i = 0; i < len; i++) {
            in = Integer.parseInt(br.readLine());
            if(in<0)
                arr[0][-in]++;
            else
                arr[1][in]++;
        }
        for (int i = 1000000; i >0 ; i--) {
            if(arr[0][i]!=0)
                for(int j=0; j<arr[0][i]; j++){
                    sb.append(-i).append("\n");
                }
        }
        for (int i = 0; i < 1000001; i++) {
            if(arr[1][i]!=0)
                for(int j=0; j<arr[1][i]; j++){
                    sb.append(i).append("\n");
                }
        }
        System.out.println(sb);
    }
}