8-6: Advanced 정렬하기

Advanced 정렬하기

 

문제

---

서로 다른 n개의 정수가 주어질 때, 이를 1초안에 오름차순으로 정렬하는 프로그램을 작성하시오.  

입력

---

첫 번째 줄에 n이 주어진다. ( 1 ≤ n ≤ 100,000 ) 두번째 줄에 n개의 정수가 주어진다.  

출력

---

첫 번째 줄에 n개의 숫자를 합병정렬을 이용하여 오름차순으로 정렬한 결과를 출력한다.

 

예제 입력

10
2 5 3 4 8 7 -1 9 10 2

예제 출력

-1 2 2 3 4 5 7 8 9 10

Quicksort:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class quicksort {

    /**
     *
     * 문제: 숫자박스에는 자연수들이 적혀있는 종이들이 N장 들어있다. 숫자 M개가 주어졌을 때, 이 숫자가 적혀있는 숫자가 상자 안에 있는지 아닌지를 구하는 프로그램을 작성하시오.
     *
     *
     * 입력:
     *
     * 첫째 줄에 윤성이가 가지고 있는 숫자 정보의 개수 N (1 ≤ N ≤ 300,000)이가 주어진다. 둘째 줄에는 숫자 정보들이 주어진다. 숫자는 1,000,000이하의 정수이다. 두 숫자 카드에 같은 숫자가 적혀있는 경우는 없다.
     *
     * 셋째 줄에는 M (1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 윤성이가 숫자 박스에 있는지 아닌지를 구해야 할 M개의 숫자가 주어지며, 이 숫자는 공백으로 구분되어져 있다. 이숫자도 1,000,000이하의 정수이다.
     *
     *
     * 출력:
     *
     *
     * 예제 입력:
     *
     *
     * 예제 출력:
     *
     *
     * @param args
     */

    public static int[] myNums;

    public static void main(String[] args) throws IOException {
//        Scanner sc = new Scanner(System.in);
//        int N = sc.nextInt();

        InputStreamReader reader = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(reader);

        int N = Integer.parseInt(br.readLine());
        myNums = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int i=0; i<N ;i++){
            myNums[i] = Integer.parseInt(st.nextToken());
        }

        quickSort(myNums);

        for (int i=0; i<myNums.length; i++){
            System.out.print(myNums[i]+" ");
        }

    }



    private static void quickSort(int[] arr) {
        quickSort(arr, 0, arr.length-1);
    }

    private static void quickSort(int[] arr, int leftIndex, int rightIndex) {
        if (leftIndex >= rightIndex) return;

        int pivot = arr[(leftIndex+rightIndex)/2];

        int index = partition(arr, leftIndex, rightIndex, pivot);

        quickSort(arr, leftIndex, index-1);
        quickSort(arr, index, rightIndex);
    }

    private static int partition(int[] arr, int leftIndex, int rightIndex, int pivot) {
        while (leftIndex <= rightIndex){
            while (arr[leftIndex] < pivot){
                leftIndex++;
            }

            while (arr[rightIndex] > pivot){
                rightIndex--;
            }

            if (leftIndex <= rightIndex){
                swap(arr, leftIndex, rightIndex);
                leftIndex++;
                rightIndex--;
            }
        }
        return leftIndex;
    }

    private static void swap(int[] arr, int a, int b){
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}