[정렬#1] 백준 2750번: 수 정렬하기 JAVA

2750번: 수 정렬하기 (acmicpc.net)

2750번: 수 정렬하기

문제

---

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

 

 

입력

---

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

 

 

출력

---

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

 

예제 입출력

---

예제 입력	예제 출력
5 5 2 3 4 1	1 2 3 4 5

 

풀이

---

정렬하는 방법은 여러가지가 있지만 이번 문제에서는 퀵 정렬 알고리즘을 직접 구현해서 해결하였다.

[#1] 정렬 알고리즘(Sort Algorithm) (tistory.com)

[#1] 정렬 알고리즘(Sort Algorithm)

 

코드

---

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);
		
	}
}