-
선택 정렬
이번에는 선택 정렬과는 조금 느낌이 다릅니다!선택 정렬이 전체에서 최솟값을 "선택" 하는 거 였다면,
삽입 정렬은 전체에서 하나씩 올바른 위치에 "삽입" 하는 방식입니다!선택 정렬은 현재 데이터의 상태와 상관없이 항상 비교하고 위치를 바꾸지만,
삽입 정렬은 필요할 때만 위치를 변경하므로 더 효율적인 방식입니다!이미 키 순으로 정렬된 사람들이 일렬로 쭉~ 서 있는데,
다음 원소가 그 정렬된 사람들 사이를 비집고 들어가면서
아 여기가 내 자리구나! 하면서 삽입하며 정렬하는 방식입니다.
한 번 예시를 통해 봐볼게요!
[4, 6, 2, 9, 1] # 정렬되지 않은 배열
1단계 : [4, 6, 2, 9, 1]
4는 현재 정렬되어 있는 부대원입니다.
그럼 이제 새로운 신병인 6을 받습니다.
4, 6 이 되는데 4 < 6 이므로 그대로 냅둡니다.
[4, 6, 2, 9, 1] 이렇게요!
자, 그러면 이제 한 바퀴를 돌렸죠?
이 과정에서 새로운 부대원인 4, 6은 현재 정렬된 상태입니다!
이처럼, 삽입 정렬은 한 바퀴가 돌 때마다 정렬된 상태가 됩니다.
끝까지 한 번 반복해볼게요!
2단계 : [4, 6, 2, 9, 1]
4, 6 은 현재 정렬되어 있는 부대원입니다.
그럼 이제 새로운 신병인 2를 받습니다.
4, 6, 2 가 되는데 6 > 2 이므로 둘을 변경합니다!
4, 2, 6 가 되는데 4 > 2 이므로 둘을 변경합니다!
[2, 4, 6, 9, 1] 이렇게요!
3단계 : [2, 4, 6, 9, 1]
2, 4, 6 은 현재 정렬되어 있는 부대원입니다.
그럼 이제 새로운 신병인 9를 받습니다.
2, 4, 6, 9 가 되는데 6 < 9 이므로 그대로 냅둡니다.
[2, 4, 6, 9, 1] 이렇게요!
4단계 : [2, 4, 6, 9, 1]
2, 4, 6, 9 은 현재 정렬되어 있는 부대원입니다.
그럼 이제 새로운 신병인 1을 받습니다.
2, 4, 6, 9, 1 가 되는데 9 > 1 이므로 둘을 변경합니다!
2, 4, 6, 1, 9 가 되는데 6 > 1 이므로 둘을 변경합니다!
2, 4, 1, 6, 9 가 되는데 4 > 1 이므로 둘을 변경합니다!
2, 1, 4, 6, 9 가 되는데 2 > 1 이므로 둘을 변경합니다!
[1, 2, 4, 6, 9] 이렇게요!
자, 모두 정렬이 되었습니다! 어떠신가요? 감이 좀 오시나요?-
❓ Q.
다음과 같이 숫자로 이루어진 배열이 있을 때, 오름차순으로 삽입 정렬을 이용해서 정렬하시오.input = [4, 6, 2, 9, 1] def insertion_sort(array): # 이 부분을 채워보세요! return insertion_sort(input) print(input) # [1, 2, 4, 6, 9] 가 되어야 합니다! print("정답 = [4, 5, 7, 7, 8] / 현재 풀이 값 = ",insertion_sort([5,8,4,7,7])) print("정답 = [-1, 3, 9, 17] / 현재 풀이 값 = ",insertion_sort([3,-1,17,9])) print("정답 = [-3, 32, 44, 56, 100] / 현재 풀이 값 = ",insertion_sort([100,56,-3,32,44]))-
💡 내 코드
input = [4, 6, 2, 9, 1] def insertion_sort(array): # 이 부분을 채워보세요! return insertion_sort(input) print(input) # [1, 2, 4, 6, 9] 가 되어야 합니다! print("정답 = [4, 5, 7, 7, 8] / 현재 풀이 값 = ",insertion_sort([5,8,4,7,7])) print("정답 = [-1, 3, 9, 17] / 현재 풀이 값 = ",insertion_sort([3,-1,17,9])) print("정답 = [-3, 32, 44, 56, 100] / 현재 풀이 값 = ",insertion_sort([100,56,-3,32,44])) -
🚩 해결방법
위에서 이야기했던 로직 그대로 코드에 옮기면 됩니다!우선, 반복되는 구조라서 반복문을 써야 하는데, 어떤 식으로 반복하고 있나요?
1번째 : [4, 6, 2, 9, 1]
← 비교!
2번째 : [4, 6, 2, 9, 1]
← ← 비교!
3번째 : [2, 4, 6, 9, 1]
← ← ← 비교!
4번째 : [2, 4, 6, 9, 1]
← ← ← ← 비교!즉, 1만큼 비교했다가, 1개씩 늘어나면서 반복하게 됩니다.
이 반복문을 구현하려면 아래처럼 작성하면 됩니다!for i in range(1, 5): # Q. 여기서 왜 range(5) 가 아니라 range(1, 5) 일까요? for j in range(i): # A. 삽입 정렬의 0 번째 인덱스는 정렬된 상태라고 print(i - j) # 판단할 수 있기 때문에, 첫 번째 인덱스를 비교하지 않고 넘어갑니다.내부 반복문 안에서, 만약
array[i - j - 1] > array[i - j] 라면 두 값을 변경해주고,
아니라면 나가면 됩니다!나가는 이유는? 이미 앞에 있는 원소들이 정렬이 되었으므로
더 비교할 이유가 없기 때문입니다.위의 예시 중 3단계에 해당합니다.
3단계 : [2, 4, 6, 9, 1]
신병인 9는 앞의 부대원인 6과 비교하지만 6 < 9 이기 때문에 그대로 냅둬도 됩니다.
이후에 9와 4를 비교할 필요가 있을까요? 없습니다!
앞에 원소들은 이미 6보다 낮은 숫자들로 정렬되어 있을테니까요!input = [4, 6, 2, 9, 1] def insertion_sort(array): n = len(array) for i in range(1, n): for j in range(i): if array[i - j - 1] > array[i - j]: array[i - j - 1], array[i - j] = array[i - j], array[i - j - 1] else: break return array insertion_sort(input) print(input) print("정답 = [4, 5, 7, 7, 8] / 현재 풀이 값 = ",insertion_sort([5,8,4,7,7])) print("정답 = [-1, 3, 9, 17] / 현재 풀이 값 = ",insertion_sort([3,-1,17,9])) print("정답 = [-3, 32, 44, 56, 100] / 현재 풀이 값 = ",insertion_sort([100,56,-3,32,44]))
-
