AlgorithmSort

quick sort

algorithm, python, quick sort
  • quick sort(퀵 정렬)
  • Comparison sort의 한 종류
  • 두 수를 비교해서 정렬하는 방법
  • divide and conquer(분할 정복 알고리즘)
  • O(nlogn)
  • 맨 앞의 데이터를 기준으로 선택했을 경우
  • 모든 데이터가 정렬되었을 때, 오히려 많은 시간이 걸리게 된다.(O(n^2))

  • 따라서 이 문제를 해결하는 방법은 기준을 선택할 때 중간 값을 기준으로 선택한다.

    1. 리스트의 중간 원소 pivot을 기준으로 pivot보다 큰 원소는 오른쪽으로 옮긴다.
    2. 리스트의 중간 원소 pivot을 기준으로 pivot보다 작은 원소는 왼쪽으로 옮긴다.
    3. pivot의 오른쪽 리스트와 왼쪽 리스트를 분할하여 재귀를 통해 다시 정렬 반복한다.

    4. 리스트의 크기가 0이나 1이 될때까지 반복한다.

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      46
      47
      48
      49
      50
      51
      52
      53
      54
      55
      56
      57
      58
      59
      60
      61
      62
      63
      import random

      # 퀵 정렬의 불균형 분할에 의해 오히려 수행시간이 더 많이 걸린다.
      # 따라서 pivot을 선택할 때 더욱 리스트를 균등하게 분할할 수 있는
      # 데이터를 선택할 수 있도록 get_pivot_index 함수를 설계
      def get_pivot_index(li, start, mid, end):
          """
          get_pivot_index(li, start, end) -> index
          리스트의 맨 처음 값, 가운데 값, 마지막 값 중에서
          중간 값을 가진 인덱스를 반환한다.
          """
          # 더 좋은 알고리즘이 있는지 다시 코딩해보기
          idx_li = [start, mid, end]
          if li[idx_li[0]] > li[idx_li[1]]:
              idx_li[0], idx_li[1] = idx_li[1], idx_li[0]
          if li[idx_li[1]] > li[idx_li[2]]:
              idx_li[1], idx_li[2] = idx_li[2], idx_li[1]
          if li[idx_li[0]] > li[idx_li[1]]:
              idx_li[0], idx_li[1] = idx_li[1], idx_li[0]
              
          return idx_li[1]


      def quick_sort(li, start, end):
          # base case
          if start > end:
              return
          
          left = start
          right = end
          mid = (start + end) // 2
          pivot_index = get_pivot_index(li, start, mid, end)
          li[pivot_index], li[mid] = li[mid], li[pivot_index]
          pivot = li[mid]
          
          while left <= right:
              while li[left] < pivot:
                  left += 1
                  
              while li[right] > pivot:
                  right -= 1
                  
              if left <= right:
                  li[left], li[right] = li[right], li[left]
                  left += 1
                  right -= 1
                  
          quick_sort(li, start, right)
          quick_sort(li, left, end)
          
          
      if __name__ == "__main__":
          
          while True:
              num_data = int(input("데이터 개수(종료: 0):"))
              if not num_data:
                  break
                 
              data = [random.randint(1, 100) for _ in range(num_data)]
              print(data)
              
              quick_sort(data, 0, len(data) - 1)
              print(data)
Share