AlgorithmSort

merge sort

algorithm, merge sort, python
  • merge sort(합병 정렬)
  • Comparison sort의 한 종류
  • 두 수를 비교해서 정렬하는 방법
  • divide and conquer(분할 정복 알고리즘)
  • O(nlogn)
    1. 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다.
    2. 그렇지 않을 경우에는 정렬되지 않는 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
    3. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
    4. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.
      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
      import random

      def merge(li, start, mid, end):
          """
          쪼개진 두 개 리스트 조각에서
          left_idx, right_idx를 비교해서
          작은 값을 올리고 다음 칸으로 이동
          둘 중 하나가 범위를 벗어날 때
          """
          left_idx = start
          right_idx = mid + 1
          temp = []
         
          while left_idx <= mid and right_idx <= end:
              if li[left_idx] < li[right_idx]:
                  temp.append(li[left_idx])
                  left_idx += 1
              else:
                  temp.append(li[right_idx])
                  right_idx += 1
                  
          while left_idx <= mid:
              temp.append(li[left_idx])
              left_idx += 1
              
          while right_idx <= end:
              temp.append(li[right_idx])
              right_idx += 1
              
          li[start:end+1] = temp

          
      def merge_sort(li, start, end):
          # base case
          if start >= end:
              return
        
          mid = (start + end) // 2
          
          merge_sort(li, start, mid)
          merge_sort(li, mid + 1, end)
          
          merge(li, start, mid, 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)
              
              merge_sort(data, 0, len(data) - 1)
              print(data)
Share