2751 수정렬하기

문제

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

입력

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

출력

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

---

풀이 과정

sys.stdin.readline()으로 안받고, input()으로 받았을 때

1. 선택 정렬 → 시간 초과
2. 삽입 정렬 → 시간 초과
3. 퀵 정렬 → 시간 초과
4. 계수 정렬 → 범위 커서 시도 안함
5. sort 함수 이용 → 성공

---

코드

1. sort() 이용

import sys

array = []
n = int(sys.stdin.readline())

for i in range(n):
    array.append(int(sys.stdin.readline()))
array.sort()

for i in array:
    print(i)

2. 선택 정렬

for i in range(n-1):
    min_index = array.index(min(array[i:n]))
    array[i], array[min_index] =  array[min_index], array[i]

3. 삽입 정렬

for i in range(1, len(array)):
    while i>0:
        if array[i] < array[i-1]:
            array[i-1], array[i] = array[i], array[i-1]
            i = i-1
        else:
            break

4. 퀵 정렬

def quick_sort(array, start, end):
    if start>=end:
        return 
    
    pivot = start
    left = start+1
    right = end
    
    while left <= right:
        while left<=end and array[pivot]>=array[left]:
            left += 1
        while right>start and array[pivot]<=array[right]:
            right -= 1
        if left > right:
            array[right], array[pivot]  = array[pivot], array[right]
        else:
            array[right], array[left]  = array[left], array[right]
    quick_sort(array, start, right-1)
    quick_sort(array, right+1, end)
quick_sort(array, 0, n-1)