백준 2750번) 수 정렬하기

2639 단어 퀵정렬정렬정렬

문제

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

입력

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

출력

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

내가 한 구현

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

public class Main {
	public static void selectionSort(int[] arr) {

		int min;

		for (int i = 0; i < arr.length - 1; i++) {
			min = i;
			for (int j = i + 1; j < arr.length; j++) {
				if (arr[j] < arr[min])
					min = j;
			}
			int tmp = arr[i];
			arr[i] = arr[min];
			arr[min] = tmp;

		}
		for (int n : arr)
			System.out.println(n);


	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(reader.readLine());
		int[] arr = new int[N];

		for (int i = 0; i < N; i++)
			arr[i] = Integer.parseInt(reader.readLine());

		selectionSort(arr);


	}
}

다른 분께서 퀵정렬로 구현

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static StringBuilder sb = new StringBuilder();

    public static int partition(int arr[], int left, int right) {

        int pivot = arr[(left + right) / 2];
    
        while (left < right) {
            while ((arr[left] < pivot) && (left < right))
                left++;
            while ((arr[right] > pivot) && (left < right))
                right--;
    
            if (left < right) {
                int temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
            }
        }
    
        return left;
    }

    public static void quickSort(int arr[], int left, int right) {

        if (left < right) {
            int npivot = partition(arr, left, right);
    
            quickSort(arr, left, npivot - 1);
            quickSort(arr, npivot + 1, right);
        }
    
    }

    public static void main(String[] args) throws Exception {

        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 i : arr) sb.append(i).append('\n');

        System.out.println(sb);

    }
    
}

좋은 웹페이지 즐겨찾기