[python] 백준 2750번 수 정렬하기1 : 퀵소트(QuickSort)

 

문제)

2750번: 수 정렬하기

 

알고리즘)

[알고리즘] 퀵 정렬 (Quick Sort)

 

위 개념은 JAVA언어로 구현되어 있는데 파이썬 언어로 바꾸어 실행한 결과, 메모리초과가 발생했다. 원인은 파악하는 중이다. 그래서 원리는 같지만 조금 다른 방식으로 코드를 구현해보았다.

 

피벗을 맨좌측 0으로 두었고 왼쪽리스트와 오른쪽리스트를 생성하여 재귀호출로 진행했다.  리스트 속 아이템 개수가 한 개 이하가 되면 종료된다. 오히려 이 방법이 직관적이고 좋다.

 

코드) 

 

- 일반적인 풀이 

# BOJ 재귀호출 깊이가 1000이 한계이므로 재귀호출 깊이 늘려주기
import sys
sys.setrecursionlimit(10**6)

# 입력받기
n = int(input())
inputList = []

for i in range(n) :
  inputList.append(int(input()))

# 퀵소트 함수
def quickSort(tmpList) :
  # 더 이상 정렬할 값이 없는 경우
  if len(tmpList) <= 1 :
    return tmpList

  pivot = tmpList[0] # 피벗
  left, right = [], [] # 왼쪽, 오른쪽 리스트 생성
  
  for item in tmpList[1:] :
    if item < pivot : left.append(item) # pivot보다 작은 경우, left에 삽입
    else : right.append(item) # pivot보다 큰 경우, right에 삽입

  return quickSort(left) + [pivot] + quickSort(right) # 반환

# 퀵소트 함수 호출
resultList = quickSort(inputList)

#출력
for i in range(n) :
  print(resultList[i])

 

- 파이썬 문법을 활용한 풀이

# BOJ 재귀호출 깊이가 1000이 한계이므로 재귀호출 깊이 늘려주기
import sys
sys.setrecursionlimit(10**6)

# 입력받기
n = int(input())
inputList = []

for i in range(n) :
  inputList.append(int(input()))

# 퀵소트 함수
def quickSort(tmpList) :
  # 더 이상 정렬할 값이 없는 경우
  if len(tmpList) <= 1 :
    return tmpList
  
  pivot = tmpList[0] # 피벗
  
  #파이썬에서 가능한 리스트 생성 방법 
  left = [ item for item in tmpList[1:] if item < pivot]
  right = [ item for item in tmpList[1:] if item > pivot]

  return quickSort(left) + [pivot] + quickSort(right) # 반환

# 퀵소트 함수 호출
resultList = quickSort(inputList)

#출력
for i in range(n) :
  print(resultList[i])

 

 

---

 

 

참고자료

[Python] Quick sort. 파이썬에서 간단히 퀵 정렬 구현