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

by

알고리즘은 입력, 출력, 유한성, 명시성 및 효율성을 충족해야 합니다.

병합, 정렬

분할 정복 방법은 큰 문제를 두 개의 작은 문제로 나누어 별도로 계산한 다음 결합하는 방법을 사용합니다. 즉, 무조건 이등분하고 나중에 정렬하는 알고리즘입니다. $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);
}

힙 정렬

힙 트리 구조를 사용하는 정렬 방법입니다. 병합 정렬과 퀵 정렬처럼 $O(N*log_{2}{N})$의 시간복잡도를 갖는다

힙은 2023.03.02 – (D • A/DataStructure) – (데이터 구조) 완전 이진 트리 – 힙 입니다. 여기서

1. 모든 요소(N)를 기반으로 최대 힙을 생성합니다(최대 힙 생성 알고리즘).

  1. 자식 노드가 없는 노드를 제외하고 부모 노드는 끝에서 자식 노드와 비교됩니다.
    • 이 시점에서 부모 노드는 인덱스(자식)/2에 있으므로 모든 부모 노드는 힙 크기 인덱스의 절반까지만 존재합니다. 따라서 요소의 길이/2 인덱스에서 앞으로 이동하면 부모 노드만 선택됩니다.
  2. 자식 노드가 부모 노드보다 크면 서로 교환합니다.
  3. 한 칸씩 위로 올라갑니다.

2. 최대 힙의 루트, 즉 최대값을 마지막 요소로 바꿉니다.

3. 마지막 요소, 즉 최대값이 아닌 요소로 최대 힙을 생성합니다(최대 힙 삭제 알고리즘).

  1. 루트 노드부터 부모 노드를 자식 노드와 비교하여 더 큰 값으로 교환합니다.
  2. 교환되는 시점에서 다시 자식노드와 비교하여 더 큰 값으로 교환한다.
  3. 자식 노드 아래에 더 큰 값이 없을 때까지 이 프로세스를 반복합니다.

4. 2단계와 3단계를 반복하여 정렬합니다.

Heapsort는 Heapify 알고리즘을 사용합니다. 힙 구조를 한 번 생성하려면 높이만 재실행하면 되기 때문에 시간 복잡도는 $O(logN)$입니다. Heapify를 한 번 반복할 때 각 노드에 N을 곱해야 하므로 $N*logN$ 번 실행하면 정렬됩니다.

병합 정렬과 달리 힙 정렬은 추가 메모리가 필요하지 않다는 점에서 효율적입니다. 하지만 속도만 비교한다면 퀵소트가 더 빠릅니다.

정렬 카운팅

크기에 따라 숫자를 세는 알고리즘입니다. 따라서 범위 조건이 있는 경우에만 매우 빠릅니다. $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);
    }
}