삽입 정렬 (insertion sort)
이해하기 쉽고, 장황하지 않은 자료를 기반으로 강의를 진행합니다.
4. 대표적인 정렬2: 삽입 정렬 (insertion sort)¶
1. 삽입 정렬 (insertion sort) 란?¶
- 삽입 정렬은 두 번째 인덱스부터 시작
- 해당 인덱스(key 값) 앞에 있는 데이터(B)부터 비교해서 key 값이 더 작으면, B값을 뒤 인덱스로 복사
- 이를 key 값이 더 큰 데이터를 만날때까지 반복, 그리고 큰 데이터를 만난 위치 바로 뒤에 key 값을 이동
직접 눈으로 보면 더 이해가 쉽다: https://visualgo.net/en/sorting¶
출처: https://commons.wikimedia.org/wiki/File:Insertion-sort-example.gif
2. 어떻게 코드로 만들까? (결국 프로그래밍으로 일반화할 수 있도록 만드는 것)¶
알고리즘 연습 방법에 기반해서 단계별로 생각해봅니다.
프로그래밍 연습
데이터가 두개 일때 동작하는 삽입 정렬 알고리즘을 함수로 만들어보세요
프로그래밍 근육을 키우는 방법
데이터가 두개 일때 동작하는 삽입 정렬 알고리즘을 함수로 만들어보세요
프로그래밍 근육을 키우는 방법
프로그래밍 연습
데이터가 세개 일때 동작하는 선택 정렬 알고리즘을 함수로 만들어보세요
프로그래밍 근육을 키우는 방법
데이터가 세개 일때 동작하는 선택 정렬 알고리즘을 함수로 만들어보세요
프로그래밍 근육을 키우는 방법
프로그래밍 연습
데이터가 네개 일때 동작하는 선택 정렬 알고리즘을 함수로 만들어보세요
프로그래밍 근육을 키우는 방법
데이터가 네개 일때 동작하는 선택 정렬 알고리즘을 함수로 만들어보세요
프로그래밍 근육을 키우는 방법
본 자료와 같이 IT 기술을 잘 정리하여, 온라인 강의로 제공하고 있습니다
체계적으로 전문가 레벨까지 익힐 수 있도록 온라인 강의 로드맵을 제공합니다
- 데이터가 네 개 일때 (데이터 갯수에 따라 복잡도가 떨어지는 것은 아니므로, 네 개로 바로 로직을 이해해보자.)
- 예: data_list = [9, 3, 2, 5]
- 처음 한번 실행하면, key값은 9, 인덱스(0) - 1 은 0보다 작으므로 끝: [9, 3, 2, 5]
- 두 번째 실행하면, key값은 3, 9보다 3이 작으므로 자리 바꾸고, 끝: [3, 9, 2, 5]
- 세 번째 실행하면, key값은 2, 9보다 2가 작으므로 자리 바꾸고, 다시 3보다 2가 작으므로 끝: [2, 3, 9, 5]
- 네 번째 실행하면, key값은 5, 9보다 5이 작으므로 자리 바꾸고, 3보다는 5가 크므로 끝: [2, 3, 5, 9]
- 예: data_list = [9, 3, 2, 5]
3. 알고리즘 구현¶
- for stand in range(len(data_list)) 로 반복
- key = data_list[stand]
- for num in range(stand, 0, -1) 반복
- 내부 반복문 안에서 data_list[stand] < data_list[num - 1] 이면,
- data_list[num - 1], data_list[num] = data_list[num], data_list[num - 1]
- 내부 반복문 안에서 data_list[stand] < data_list[num - 1] 이면,
In [ ]:
def insertion_sort(data_list):
for stand in range(len(data_list)):
key = data_list[stand]
for num in range(stand, 0, -1):
if key < data_list[num - 1]:
data_list[num - 1], data_list[num] = data_list[num], data_list[num - 1]
else:
break
return data_list
In [ ]:
# 데이터 준비: data_list 10개 만들기
from random import *
rand_data_list = list()
for num in range(10):
rand_data_list.append(randint(1, 100))
In [ ]:
insertion_sort(rand_data_list)
본 자료와 같이 IT 기술을 잘 정리하여, 온라인 강의로 제공하고 있습니다
체계적으로 전문가 레벨까지 익힐 수 있도록 온라인 강의 로드맵을 제공합니다
4. 알고리즘 분석¶
- 반복문이 두 개 O($n^2$)
- 최악의 경우, $\frac { n * (n - 1)}{ 2 }$
- 완전 정렬이 되어 있는 상태라면 최선은 O(n)
프로그래밍 연습
지금 설명한 삽입 정렬을 지금 다시 스스로 작성해보세요
지금 설명한 삽입 정렬을 지금 다시 스스로 작성해보세요
- 이해가 안가면, 이 코드를 보면서 이해하기: https://goo.gl/XKBXuk