[백준] 2751번:수 정렬하기2 (자바)

https://www.acmicpc.net/problem/2751

이 문제는 오름차순으로 정렬만 하면 간단한 문제이지만 시간제한이 있기때문에 시간복잡도가 O(n)인 정렬을 사용해야한다.

그래서 정렬중에 평균 속도가 가장 빠른 퀵소트를 사용해서 풀었다.

<코드>

import java.util.Scanner;

// 퀵소트를 이용한 수 정렬하기2
public class Main {

    static void quickSort(int[] nums, int left, int right) {
        int pl = left;
        int pr = right;
        int x = nums[(pl + pr) / 2];

        do {
            while (nums[pl] < x) pl++;
            while (nums[pr] > x) pr--;
            if (pl <= pr)
                swap(nums, pl++, pr--);

        } while (pl <= pr);
        if (left < pr) quickSort(nums, left, pr);
        if (right > pl) quickSort(nums, pl, right);
    }

    private static void swap(int[] a, int i, int j) {
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }

    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int index = sc.nextInt();
        int[] nums = new int[index];
        for(int i=0;i<index;i++)
            nums[i]=sc.nextInt();

        quickSort(nums, 0, nums.length - 1);
        for (int n : nums)
            System.out.println(n);
    }
}

다른 정답 코드를 확인해봤는데 자바에서 제공해주는 Arrays.sort() 메소드를 사용해서 푸는것도 가능하다.

import java.util.*;
public class Main {
	public static void main (String args[]) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] num = new int[N];
		for(int i=0; i<N; i++)
			num[i] = sc.nextInt();
		Arrays.sort(num);
		for(int i=0; i<N; i++)
			System.out.println(num[i]);
	}
}