Implementation (Part 2)
Coddy의 삽입 정렬 - DSA 시리즈 코스 레슨 — 9개 중 6번째.
시나리오: [5, 2, 9, 1, 5] 정렬하기
1단계: 초기 상태
- 원본 배열: [5, 2, 9, 1, 5]
- 이것을 우리가 손에 든 카드(또는 숫자 배열)라고 상상해 보세요.
2단계: 첫 번째 요소 (i=1, key=2)
- 두 번째 카드(요소)부터 시작합니다: key = 2.
- 2를 5(지금까지 정렬된 유일한 요소)와 비교합니다.
- 2가 더 작으므로, 5를 오른쪽으로 옮기고 그 자리에 2를 삽입합니다.
- 업데이트된 배열: [2, 5, 9, 1, 5]
3단계: 두 번째 요소 (i=2, key=9)
- 다음 카드로 이동합니다: key = 9.
- 9를 5와 비교합니다.
- 9가 더 크므로, 옮길 필요가 없습니다.
- 업데이트된 배열: [2, 5, 9, 1, 5] (변경 없음)
4단계: 세 번째 요소 (i=3, key=1)
- 다음 카드로 이동합니다: key = 1.
- 1을 9와 비교한 다음, 5와 비교합니다.
- 9와 5를 오른쪽으로 옮겨 1이 들어갈 공간을 만듭니다.
- 업데이트된 배열: [1, 2, 5, 9, 5]
5단계: 네 번째 요소 (i=4, key=5)
- 다음 카드로 이동합니다: key = 5.
- 5를 9와 비교합니다.
- 5가 더 작으므로, 옮길 필요가 없습니다.
- 업데이트된 배열: [1, 2, 5, 9, 5] (변경 없음)
6단계: 다섯 번째 요소 (i=5, key=5)
- 마지막 카드로 이동합니다: key = 5.
- 5를 9와 비교합니다.
- 5가 더 작으므로, 옮길 필요가 없습니다.
- 업데이트된 배열: [1, 2, 5, 5, 9]
최종 결과:
- 정렬된 배열: [1, 2, 5, 5, 9]
각 단계에서 우리는 카드(요소)를 하나씩 집어 들어 정렬된 카드들과 비교하고, 필요한 경우 다른 카드들을 옮기면서 올바른 위치에 배치합니다. 전체 배열이 정렬될 때까지 이 과정을 반복합니다.
챌린지
쉬움이제 각 요소에 대해 정렬을 수행하는 내부 루프를 구현하세요.
insertionSort 함수 내부의 정렬을 완성하세요.
함수는 또한 마지막에 배열의 요소를 하나씩 줄바꿈하여 출력해야 합니다.
이전 레슨과 힌트를 참고하세요 :)
직접 해보기
def insertionSort(arr):
for i in range(1, len(arr)):
key = arr[i]
print(key)
삽입 정렬 - DSA 시리즈의 모든 레슨
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity