2750번: 수 정렬하기 (acmicpc.net)
문제
N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.
입력
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.
출력
첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.
예제 입출력
풀이
정렬하는 방법은 여러가지가 있지만 이번 문제에서는 퀵 정렬 알고리즘을 직접 구현해서 해결하였다.
[#1] 정렬 알고리즘(Sort Algorithm) (tistory.com)
코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
public class Main {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
int[] arr = new int[n];
for(int i=0; i<n; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
quickSort(arr, 0, arr.length-1);
for(int result:arr) {
bw.write(result +"\n");
}
bw.flush();
bw.close();
}
public static void quickSort(int[] arr, int start, int end) {
if(start >= end) return;
int pivot = start;
int left = start +1;
int right = end;
while(left<=right) {
while(left<=end && arr[pivot] >= arr[left])
left++;
while(right>start && arr[pivot] <= arr[right])
right--;
if(left<=right) {
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}else {
int temp = arr[right];
arr[right] = arr[pivot];
arr[pivot] = temp;
}
}
quickSort(arr, start, right -1);
quickSort(arr, right +1, end);
}
}