[알고리즘] 삽입 정렬

삽입 정렬은 정렬이 안된 배열의 원소를 차례대로 앞에 이미 정렬이 완료 된 원소들과 비교하여 자신의 자리를 찾아 삽입하여 정렬하는 알고리즘 이다.

1. 정렬이 안된 배열의 두번째 원소를 바로 앞 원소와 비교한다. 더 작은 원소가 앞에 위치하도록 위치를 바꿔준다.
   [70, 31, 3, 72, 20] -> [31, 70, 3, 72, 20]

   if data[j] < data[j-1]:
       data[j], data[j-1] = data[j-1], data[j]

2. 자신보다 큰 원소를 찾기 전까지 위의 과정을 반복한다.

   for j in range(i, 0, -1):
       if data[j] < data[j-1]:
           data[j], data[j-1] = data[j-1], data[j]
       else:
           break

3. 정렬이 안된 배열의 원소를 차례대로 1번과 2번 과정을 반복한다.
   [31, 70, 3, 72, 20] -> [31, 3, 70, 72, 20]

   [31, 3, 70, 72, 20] -> [3, 31, 70, 72, 20]

   [3, 31, 70, 72, 20] -> [3, 31, 70, 20, 72]

   [3, 31, 70, 20, 72] -> [3, 31, 20, 70, 72]

   def insert(data):
       for i in range(1, len(data)):
           for j in range(i, 0, -1):
               if data[j] < data[j-1]:
                   data[j], data[j-1] = data[j-1], data[j]
               else:
                   break
       return data