7-7: 문자열 정렬

문자열 정렬 ( str7.cpp )

 

문제

---

n개의 문자열이 주어질 때, 이 문자열을 사전순으로 빠른 순서대로 정렬하는 프로그램을 작성하시오.

 

입력

---

첫 번째 줄에 문자열의 개수 n이 주어진다 ( 1 ≤ n ≤ 100 ) 그 후 n개의 줄에 대하여 정렬하고자 하는 문자열이 주어진다 ( 1 ≤ 문자열의 길이 ≤ 100 )

 

출력

---

문자열을 사전순으로 빠른 순서대로 정렬한 결과를 출력한다.

 

예제 입력

9
acid
apple
banana
acquire
cat
crop
crab
power
cat

예제 출력

acid
acquire
apple
banana
cat
cat
crab
crop
power

import java.util.Scanner;

public class str7 {

    /**
     *
     * 문제:
     *
     n개의 문자열이 주어질 때, 이 문자열을 사전순으로 빠른 순서대로 정렬하는 프로그램을 작성하시오.


     *
     *
     * 입력:
     *
     *
     * 출력:
     *
     *
     * 예제 입력:
     *
     9
     acid
     apple
     banana
     acquire
     cat
     crop
     crab
     power
     cat
     * 예제 출력:
     acid
     acquire
     apple
     banana
     cat
     cat
     crab
     crop
     power
     *
     * @param args
     */

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        sc.nextLine();
        String[] arr = new String[N];
        for (int i=0; i<arr.length; i++){
            arr[i] = sc.nextLine();
        }

        quickSort(arr);

        for(int i=0; i<arr.length; i++){
            System.out.println(arr[i]);
        }
    }

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

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

        String 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(String[] arr, int leftIndex, int rightIndex, String pivot) {
        while (leftIndex <= rightIndex){
            while (arr[leftIndex].compareTo(pivot) <0){
                leftIndex++;
            }

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

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

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


}