[백준] 2751 수 정렬하기 2 - 파이썬 / 퀵 정렬

2751번: 수 정렬하기 2

---

import sys
n = int(input())
lst = [int(sys.stdin.readline()) for _ in range(n)]

lst.sort()
for n in lst: print(n)

사실 파이썬 내장 함수 sort 쓰면 통과되는 문제, 설명에서도 내장 함수 쓰라고 하고.. (단, input 사용하면 시간 초과)

 

파이썬의 sort는 병합정렬과 삽입정렬을 적절히 섞은 알고리즘이라고 하고 시간복잡도는 O(NlogN)이라고 한다. 

(근데 어디서는 또 sort는 퀵 정렬 기반이라고 한다.)

 

스택 오버 플로우에서 다음과 같다고 하니까 이걸 믿을란다.

Timsort is a hybrid sorting algorithm, derived from merge sort and insertion sort.

 

퀵 정렬을 파이썬으로 구현해보고 싶어서 예전에 C로 짰던 퀵 정렬 코드를 파이썬으로 옮겼다.

def partition(lst, p, r): 
  i, j = p - 1, p
  while (j < r):
    if (lst[j] < lst[r]):
      lst[i + 1], lst[j] = lst[j], lst[i + 1]
      i, j = i + 1, j + 1
    else: j += 1
  lst[i + 1], lst[j] = lst[j], lst[i + 1]
  return i + 1

def quickSort(lst, p, r):
  if p < r:
    q = partition(lst, p, r)
    quickSort(lst, p, q - 1)
    quickSort(lst, q + 1, r)

import sys
n = int(input())
lst = [int(sys.stdin.readline()) for _ in range(n)]

quickSort(lst, 0, n - 1)
for n in lst: print(n)

근데 직접 짠 코드나 인터넷 검색해서 나오는 파이썬 퀵 정렬 코드로 제출하면 시간 초과난다. 

 

이유는 아래 링크 참고

글 읽기 - ★☆★☆★ [필독] 수 정렬하기 2 FAQ ★☆★☆★

 

간단하게 요약하자면 퀵 정렬은 정렬이나 역정렬이 된 값들이 입력될 경우 시간 복잡도가 최악의 경우가 되기 때문..

퀵 정렬 사용을 권장하지 않는다고 한다.