[Python] Insertion Sort: 삽입정렬

안녕하세요. 우주신 입니다.

오늘은 삽입 정렬(Insertion Sort)에 대해 포스팅하겠습니다.

알고리즘을 배울 때, 가장 먼저 접하게 되는 친숙한 삽입 정렬입니다.

삽입 정렬은 말 그대로 데이터의 삽입을 통해 정렬을 완성하는 알고리즘 입니다.

현재 위치에서, 이미 정렬된 이전 배열들의 데이터를 차례대로 비교하여 자신의 위치를 찾아 그 위치에 삽입하는 방식 입니다.

시간 복잡도는 최악의 경우 O(n^2)이고, 최선의 경우(이미 정렬되어 있는 경우)에는 O(n) 이므로 Big-O (n^2) 입니다.

5 3 4 6 1 2

3 5 4 6 1 2

3 4 5 6 1 2

1 3 4 5 6 2

1 2 3 4 5 6

파이썬 코드를 통해 자세히 알아보겠습니다.

우선, 데이터를 리스트로 입력 받겠습니다.

입력 받은 데이터를 띄어쓰기 기준으로 구분하여 이를 정수형으로 리스트에 저장하는 코드 입니다.

위의 코드가 헷갈리시는 분들은 똑같은 기능을 하는 밑의 코드를 참고해주세요.

다음으로는 삽입 정렬 알고리즘 입니다.

j가 비교하려는 값의 위치를 담고 있고,

key는 그 위치에 있는 값을 담고 있습니다.

i는 j의 바로 이전 값을 가리키는 위치 입니다. i의 값을 하나씩 감소시키며 반복문을 도는데,

이 때 i의 위치에 있는 값이 key보다 더 크면 i+1 자리로 값을 옮기고 key보다 값이 작으면 반복문을 빠져나와 오른쪽 자리에 위치합니다.

코드는 간단해서 한줄한줄 보시면 쉽게 이해가실겁니다.

마지막으로 결과 값을 출력 했고 깔끔하게 정렬되서 나오는 것을 확인할 수 있습니다.

끝

우 주 신