[알고리즘] 퀵정렬

오늘은 퀵정렬에 대해 알아보려고 한다.
퀵정렬은 기준값을 정하고 그 값과 비교하여 더 작은 원소는 기준값의 왼쪽에 큰 값은 기준값의 오른쪽에 배치하여 이 과정을 반복하여 정렬을 완성하는 알고리즘 이다.

1. 기준값을 정한다.

   pivot = data[0]

2. 기준값보다 작은 원소는 기준값의 왼쪽에 배치한다.

   left = list()
   for number in range(1, len(data)):
       if number < pivot:
           left.append(number)

3. 기준값보다 큰 원소는 기준값의 오른쪽에 배치한다.

   right = list()
   for number in range(1, len(data)):
       if number >= pivot:
           right.append(number)

4. 위의 과정들을 반복하여 정렬을 완성한다.

   def quick_sort1(data):
       if len(data) <= 1:
           return data
       pivot = data[0]
       left,right = list(), list()
       for i in range(1, len(data)):
           if pivot >= data[i]:
                left.append(data[i])
           else:
                right.append(data[i])
       return quick_sort1(left) + [pivot] + quick_sort1(right)

또 다른 방법으로 구현 가능하다.

def quick_sort2(data):
   if len(data) <= 1:
       return data
   pivot = data[0]
   left = [number for number in data[1:] if number < pivot]
   right = [number for number in data[1:] if number >= pivot]
   return quick_sort2(left) + [pivot] + quick_sort2(right)