Quick Sort 파이썬 구현

1. 소스코드

import random def QuickSort(list):     if len(list) <= 1:         return list     pivot = list[0]     left = [i for i in list[1:] if i <= pivot]     right = [i for i in list[1:] if i > pivot]     return QuickSort(left) + [pivot] + QuickSort(right) def main():     N = 10  #리스트 원소 개수     list = [random.randint(0,100) for i in range(N)]     print(' list=  ', list)     list = QuickSort(list)     print('sorted= ', list)     return main()

 

2. 고찰

1) Quick Sort 함수

재귀로 구현하였다. 입력 list가 들어오면 해당 리스트에서 pivot을 하나 선택한다.

pivot과 비교하여 작거나 같은 숫자는 left리스트에, 큰 숫자는 right리스트에 저장한다.

그 후 left리스트에 대해서 다시 Quick Sort하고, pivot과 right리스트에 대해서 Quick Sort한 리스트를 리턴한다.

재귀함수에서는 종료조건이 중요한데, 입력 리스트의 길이가 1보다 작거나 같은 경우, 입력리스트 그대로 리턴하도록 하였다.

 

2) 랜덤 정수 리스트 생성

list = [random.randint(랜덤정수 범위 최소, 최대) for i in range(리스트 원소 개수)]

이때 뽑히는 랜덤 정수들은 최소 <= 정수 <= 최대 의 범위이다. 즉 최소, 최대값을 둘 다 포함하는 범위이다.