[백준 2751] 수 정렬하기 2 with 파이썬

요구사항

수의 개수가 1 ≤ N ≤ 1,000,000개 일 때, 정렬하기

 

참고

퀵 정렬 구현하여 문제 풀이를 진행하였다.

퀵 정렬은 피벗을 기준으로 왼쪽에는 작은 값 오른족에는 큰 값을 오게 만들어 재귀를 통해 정렬하는 것이다

 

풀이

import sys 
arr=[]
n=int(input())
for i in range(n):
    arr.append(int(sys.stdin.readline().rstrip()))
def QuickSort(left, right, arr):
    #left 가 클 경우 종료
    if(left>=right):
        return
    i = left
    j = right
    pivot = arr[(left+right)//2]
    #i, j가 교차 하면 종료

    while(i<=j):
        #i가 작은 거라면 통과 아니라면 멈춘다 -> 교환해야함
        while(arr[i] <pivot):
            i+=1
        #j가 큰 거라면 통과 아니라면 멈춘다 -> 교환해야함
        while(arr[j] >pivot):
            j-=1
        if(i<=j):
            temp=arr[i]
            arr[i]=arr[j]
            arr[j]=temp
            i+=1
            j-=1
        
    QuickSort(left,j,arr)
    QuickSort(i,right,arr)


QuickSort(0, n - 1, arr)
for i in range(n):
    print(arr[i])

풀이(파이썬 스럽게)

import sys 
arr=[]
n=int(input())
#한 줄에 1개 있는 int값 입력 받고
arr= [int(sys.stdin.readline()) for i in range(n)]
#리스트를 정렬한 것을 int->str로 바꾸어 조인으로 char으로 바꾼다
sys.stdout.write("\n".join(map(str, sorted(arr))))