[Python] 백준, 1427(정렬)

https://www.acmicpc.net/problem/1427

1427번: 소트인사이드

이번에 사용한 정렬 알고리즘은 퀵정렬이다. 사실 어떤 정렬 알고리즘의 효율이 더 좋은지는 아직 시간 복잡도에 대한 이해가 부족하여 잘 모르겠지만, 우선은 다양한 알고리즘들을 실제로 사용해보는 것도 좋지 않을까라는 것에 의의를 두기로 한다.

 

보통의 정렬 알고리즘과 달리 이 문제는 내림차순을 요구하기 때문에 일반적인 풀이와는 미묘하게 다르다. 어느 부분을 수정해야하는지 사고하는 것도 의외로 단순하지만 재밌는 경험이었다.

 

# PYTHON CODE

import sys
 
s = list(map(int, sys.stdin.readline().rstrip()))
 
def quick_sort(s, left, right):
    pl, pr = left, right
    x = s[(pl + pr) // 2]
 
    while pl <= pr:
        while s[pl] > x: pl += 1
        while s[pr] < x: pr -= 1
        if pl <= pr:
            s[pl], s[pr] = s[pr], s[pl]
            pl += 1
            pr -= 1
 
    if left < pr: quick_sort(s, left, pr)
    if pl < right: quick_sort(s, pl, right)
 
quick_sort(s, 0 ,len(s) - 1)
 
for i in s:
    print(i, end='')