[2750] 수 정렬하기

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

입력

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

출력

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

생각

어차피 기본적인 정렬 문제라서 가장 시간복잡도가 괜찮은 퀵정렬을 구현해보겠다.

처음 코드

using System.Text;

namespace BaekJoon
{
    public class P2750
    {
        int partition(int[] list, int left, int right)
        {
            int pivot, temp;
            int low, high;

            low = left;
            high = right;
            pivot = list[left];
            while (low < high)
            {
                while (low <= right && list[low] < pivot)
                {
                    low++;
                }

                while (high >= left && list[high] > pivot)
                {
                    high--;
                } 

                if (low < high)
                {
                    temp = list[low];
                    list[low] = list[high];
                    list[high] = temp;

                    if (list[low] == list[high])
                        high--;
                }
            } 

            return high;

        }

        void quickSort(int[] list, int left, int right)
        {
            if(left < right)
            {
                int q = partition(list, left, right);

                quickSort(list, left, q - 1);
                quickSort(list, q + 1, right);
            }
        }
        

        static void Main(string[] args)
        {
            P2750 p2750 = new ();
            int n = int.Parse(Console.ReadLine());
            int[] list = new int[n];
            for(int i = 0; i < n; i++)
            {
                list[i]= int.Parse(Console.ReadLine());
            }
            p2750.quickSort(list, 0, n - 1);
            for (int i = 0; i < n; i++)
                Console.WriteLine(list[i]);
            
        }    

    }
}

결과