AlgorithmSort

insertion sort

algorithm, insertion sort, python
  • insertion sort(삽입 정렬)
  • Comparison sort의 한 종류
  • 두 수를 비교해서 정렬하는 방법
  • O(n^2)
  • Comparison sort 중에 그나마 나음
  • simple sort
  • 두 번째 자료부터 시작하여 그 앞 자료들과 비교하면서 삽입할 위치를 지정
  • 지정한 후, 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬하는 방식

  • 처음 key 값은 두번째 자료부터 시작한다.

    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
    import random

    def insertion_sort(li):
       
        n = len(li)
        
        for i in range(1, n):
            ref_idx = li[i]
            
            for j in range(i-1, -2, -1):
                if j == -1:
                    break
                    
                elif li[j] > li[j+1]:
                    li[j], li[j+1] = li[j+1], li[j]
     
                else:
                    break
                    
            ref_idx = li[j+1]
              
      
    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)
            
            insertion_sort(data)
            print(data)
Share