[백준 2751] 수 정렬하기 2

 

줄의 개수가 최대 1000000 이라서 선택, 거품, 삽입 정렬 등의 느린 정렬방법으로는 풀 수 없다.

 

병합(합병) 정렬, 힙 정렬, 퀵 정렬 등으로 풀 수 있는데, 언급한 3가지 정렬 방법으로 모두 구현해 보겠다.

 

 

1. 병합 정렬(Merge Sort)

 

public class Main {
    
    static int temp[];
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int n;
        n = Integer.parseInt(br.readLine());
        int a[] = new int[n];
        temp = new int[n];
        
        for(int i=0; i<n; i++)
            a[i] = Integer.parseInt(br.readLine());
        
        divide(a, 0, n-1);
        for(int i=0; i<n; i++) {
            bw.write(a[i] + "\n");
            bw.flush();
        }
        br.close();
        bw.close();
    }
    
    public static void divide(int a[], int left, int right) {
        if(left < right) {
            int mid = (left + right)/2;
            divide(a, left, mid);
            divide(a, mid+1, right);
            merge(a, left, mid, right);
        }
    }
    
    public static void merge(int a[], int left, int mid, int right) {
        int leftFirst = left;
        int rightFirst = mid+1;
        
        int leftSeq = left;
        while(leftFirst <= mid && rightFirst <= right) {
            if(a[leftFirst] <= a[rightFirst])
                temp[leftSeq++] = a[leftFirst++];
            else
                temp[leftSeq++] = a[rightFirst++];
        }
        if(leftFirst > mid) {
            for(int i=rightFirst; i<=right; i++)
                temp[leftSeq++] = a[i];
        } else {
            for(int i=leftFirst; i<=mid; i++)
                temp[leftSeq++] = a[i];
        }
        for(int i=left; i<=right; i++)
            a[i] = temp[i];
    }
}

 

1. Divide 분할

2. Conquer 정복

3. Combine 병합

 

세 단계로 진행되는 정렬 방식이다. 리스트 길이를 반으로 쪼개면서

정렬한 부분 배열을 임시 배열에 저장했다가 원래 배열에 붙여넣는다.

 

 

 

2. 퀵 정렬(Quick Sort)

 

public class Main {
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int n = Integer.parseInt(br.readLine());
        int a[] = new int[n];
        for(int i=0; i<n; i++)
            a[i] = Integer.parseInt(br.readLine());
        
        quickSort(a, 0, n-1);
        
        for(int i=0; i<n; i++)
            bw.write(a[i] + "\n");
        
        bw.flush();
        br.close();
        bw.close();
    }
    
    public static void quickSort(int a[], int left, int right) {
        if(left < right) {
            int p = partition(a, left, right);
            quickSort(a, left, p-1);
            quickSort(a, p+1, right);
        }
    }
    
    public static int partition(int a[], int left, int right) {
        int mid = (left + right)/2;
        swap(a, left, mid);
        
        int pivot = a[left];
        int i = left, j = right;
        
        while(i < j) {
            while(pivot < a[j]) {
                j--;
            }
            while(i < j && pivot >= a[i]) {
                i++;
            }
            swap(a, i, j);
        }
        a[left] = a[i];
        a[i] = pivot;
        return i;
    }
    
    public static void swap(int a[], int x, int y) {
        int temp = a[y];
        a[y] = a[x];
        a[x] = temp;
    }
}

 

퀵정렬은 피벗을 첫번째 수로 둘 경우 최악일때 O(n^2) 이 될 수 있다.

피벗을 배열의 가운데 수로 정하여 재귀를 돌렸다.

 

 

 

3. 힙 정렬(Heap Sort)

 

public class Main {
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int n = Integer.parseInt(br.readLine());
        Heap h = new Heap(n+1);
        for(int i=0; i<n; i++) {
            int k = Integer.parseInt(br.readLine());
            h.insert_min_heap(k);
        }
        for(int i=h.size-1; i>=0; i--)
            bw.write(h.delete_min_heap() + "\n");
        bw.flush();
        br.close();
        bw.close();
    }
}

class Heap {
    
    int heap[];
    int size;
    
    public Heap(int size) {
        heap = new int[size];
    }
    
    public void insert_min_heap(int n) {
        heap[++size] = n;
        for(int i=size; i>1; i/=2) {
            if(heap[i/2] > heap[i])
                swap(i/2, i);
            else break;
        }
    }
    
    public int delete_min_heap() {
        if(size == 0) return 0;
        
        int root = heap[1];
        heap[1] = heap[size];
        size--;
        
        for(int i=1; i*2<=size;) {
            if(heap[i] < heap[i*2] && heap[i] < heap[i*2+1]) break;
            else if(heap[i*2] < heap[i*2+1]) {
                swap(i, i*2);
                i = i*2;
            } else {
                swap(i, i*2+1);
                i = i*2+1;
            }
        }
        return root;
    }
    
    public void swap(int a, int b) {
        int temp = heap[a];
        heap[a] = heap[b];
        heap[b] = temp;
    }
}

 

오름차순으로 정렬해야 하므로 최소힙으로 구성한 모습이다.