파이썬 삽입 정렬(Insertion Sort) 작성 방법 완벽 가이드

파이썬 삽입 정렬은 게임 카드를 정리하는 것과 비슷하게 동작합니다. 삽입 정렬을 사용하려면 정렬된 리스트와 정렬되지 않은 리스트 두 개를 만들고, 정렬되지 않은 리스트의 각 항목을 올바른 위치에 배치될 때까지 비교합니다. 삽입 정렬은 파이썬에서 널리 사용되는 기본 알고리즘 중 하나입니다.

손에 든 카드를 정렬해 본 적이 있나요? 그것이 바로 파이썬 삽입 정렬의 개념을 이해하는 가장 좋은 비유입니다. 요소가 몇 개 되지 않는 리스트를 정렬할 때 삽입 정렬은 아주 유용한 선택입니다.

삽입 정렬은 배열에서 매 반복마다 정렬되지 않은 요소를 올바른 위치에 삽입하는 방식으로 동작합니다.

이 가이드에서는 삽입 정렬이 무엇인지, 어떻게 동작하는지 살펴보고, 예제와 함께 파이썬으로 삽입 정렬을 구현하는 방법까지 단계별로 알아보겠습니다.

파이썬 삽입 정렬이란?

삽입 정렬은 하나의 리스트를 '정렬된 부분'과 '정렬되지 않은 부분'이라는 두 개의 하위 리스트로 나눕니다. 그런 다음 정렬되지 않은 리스트의 각 요소를 비교하며, 리스트의 모든 항목이 정렬될 때까지 이 과정을 반복합니다.

삽입 정렬 알고리즘은 정렬된 항목을 정렬된 하위 리스트로 옮기고, 정렬되지 않은 하위 리스트에서는 제거합니다. 두 하위 리스트는 사실 같은 배열의 일부이며, 어떤 항목이 정렬되었는지 구분하는 역할을 합니다.

삽입 정렬은 카드 게임에서 손에 든 카드를 정렬하는 방식에 비유할 수 있습니다.

카드 목록을 하나씩 훑어가며 서로 비교하게 됩니다. 정렬된 카드는 손의 왼쪽에 위치하고, 정렬되지 않은 카드는 오른쪽에 있다가 모두 정렬될 때까지 기다립니다.

파이썬 삽입 정렬은 어떻게 동작하나요?

이제 본격적으로 삽입 정렬 알고리즘을 사용해 배열을 정렬해 보겠습니다. 다음과 같은 정렬되지 않은 배열이 있다고 가정해 봅시다:

삽입 정렬에서 첫 번째 요소는 이미 정렬된 것으로 간주합니다. 두 번째 요소는 별도의 변수에 저장되는데, 우리는 이 변수를 current_number라고 부르겠습니다.

이제 current_number를 배열의 첫 번째 위치에 있는 항목과 비교해야 합니다. current_number가 첫 번째 요소보다 크면 그 자리에 그대로 있고, 그렇지 않으면 첫 번째 요소 앞으로 이동합니다.

4는 9보다 크지 않으므로 두 요소의 자리가 바뀝니다.

리스트의 처음 두 요소가 정렬되었습니다. 다음으로 current_number의 값을 리스트의 세 번째 항목으로 변경하고, 왼쪽에 있는 모든 항목과 비교합니다.

current_number는 3이 됩니다. 다음을 비교해야 합니다:

• 3이 9보다 큰가요? 아니요, 따라서 3은 9 앞에 삽입됩니다.
• 3이 4보다 큰가요? 아니요, 따라서 3은 4 앞으로 이동합니다.

이제 리스트는 다음과 같습니다:

이 과정은 리스트가 정렬될 때까지 반복됩니다. 리스트에는 값이 네 개뿐이므로 비교는 한 번만 더 수행하면 됩니다. 다음 반복에서 5가 current_number가 됩니다.

• 5가 9보다 큰가요? 아니요, 따라서 5는 9 앞으로 이동합니다.

5는 정렬된 리스트의 마지막 숫자이므로 더 이상 비교할 필요가 없습니다. 이 반복이 끝나면 배열은 완전히 정렬됩니다:

정말 간단하죠! 삽입 정렬 과정 내내 정렬된 값들은 항상 리스트의 왼쪽에 유지되었고, 정렬되지 않은 값들은 오른쪽에 있었습니다.

리스트의 각 반복마다 current_number를 모든 정렬되지 않은 항목과 비교했습니다. 이 과정은 리스트가 완전히 정렬될 때까지 반복됩니다.

파이썬으로 삽입 정렬 작성하기

종이 위에서 삽입 정렬을 살펴보는 것만으로는 부족합니다. 이제 실제로 파이썬으로 삽입 정렬을 구현해 보겠습니다.

정렬 함수 작성하기

먼저 정렬을 수행하는 파이썬 함수를 작성합니다:

def sortNumbers(toSort):
	for number in range(1, len(toSort)):
		current_number = toSort[number]
		i = number - 1

		while i >= 0 and current_number < toSort[i]:
			toSort[i + 1] = toSort[i]
			i -= 1

		toSort[i + 1] = current_number

이 코드가 어떻게 동작하는지 살펴보겠습니다. sortNumbers 함수 안에는 리스트의 모든 숫자를 순회하는 파이썬 for 루프가 있습니다. 그런 다음 리스트의 첫 번째 요소를 파이썬 변수 current_number에 할당하여 정렬된 값으로 설정합니다.

정렬되지 않은 파이썬 리스트(current_number 이후의 모든 항목)의 모든 항목을 순회하면서, current_number를 왼쪽의 각 숫자와 비교합니다. 이 과정이 끝나면 current_number의 값을 리스트에서 그 다음 요소로 설정합니다.

메인 프로그램 작성하기

이제 삽입 정렬을 실행하는 메인 프로그램을 작성해야 합니다:

numbers = [9, 4, 3, 5]
sortNumbers(numbers)

print(numbers)

코드 실행 결과는 다음과 같습니다:

[3, 4, 5, 9]

리스트가 오름차순으로 성공적으로 정렬되었습니다! 여기까지 잘 따라오셨다면 축하드립니다.

파이썬 삽입 정렬: 내림차순 정렬

삽입 정렬은 숫자를 내림차순으로 정렬할 수도 있습니다. 이를 위해서는 while 루프의 '작다'(<) 연산자를 '크다'(>) 연산자로 바꾸면 됩니다:

while i >= 0 and current_number > toSort[i]:

위 예제 코드에서 이 줄로 대체하면 리스트의 항목들이 역순으로 정렬됩니다.

삽입 정렬은 언제 사용해야 할까요?

삽입 정렬은 리스트의 데이터가 거의 정렬되어 있거나, 작은 리스트를 정렬할 때 가장 적합합니다. 큰 리스트를 정렬할 때는 더 효율적인 알고리즘이 있습니다. 예를 들어 병합 정렬(merge sort)이나 퀵 정렬(quick sort)이 더 빠릅니다.

참고로 삽입 정렬은 버블 정렬(bubble sort)보다 빠릅니다.

어떤 경우에도 삽입 정렬을 알아두면 유용합니다. 삽입 정렬을 구현하는 방법을 알면 활용할 수 있는 정렬 알고리즘이 하나 더 늘어나는 셈입니다.

삽입 정렬은 다른 정렬 알고리즘보다 덜 복잡합니다. 삽입 정렬 작성법을 익히면 병합 정렬처럼 더 복잡한 정렬 알고리즘을 배우는 데 한 걸음 더 가까워집니다.

파이썬 삽입 정렬: 시간 복잡도 분석

모든 알고리즘과 마찬가지로 최선, 최악, 평균 복잡도를 고려하는 것이 중요합니다. 이를 통해 알고리즘이 주어진 작업(여기서는 리스트 정렬)을 얼마나 효과적으로 수행하는지 파악할 수 있습니다.

최악의 경우와 평균 복잡도는 O(n²)입니다. 즉, 정렬해야 할 값이 늘어날수록 알고리즘의 실행 속도가 지수적으로 느려집니다.

최선의 경우 복잡도는 O(n)입니다. 이는 이미 정렬된 리스트에 알고리즘을 실행할 때 발생합니다. 알고리즘은 항목들이 정렬되어 있음을 확인한 후 실행을 종료합니다.

알고리즘 복잡도를 표현하는 방법에 대해 더 알고 싶다면 Big O 표기법(Big O Notation) 관련 시리즈 글을 참고하세요.

결론

삽입 정렬은 카드 게임에서 손에 든 카드를 정렬하는 것과 같습니다. 정렬된 항목의 리스트와 정렬할 항목의 리스트, 두 개의 리스트를 유지하고, 정렬되지 않은 항목들을 하나씩 살펴가며 모두 정렬될 때까지 위치를 조정합니다.

더 많은 파이썬 프로그래밍 학습 자료가 필요하신가요? 파이썬 학습 방법에 대한 핵심 팁과 온라인 강좌, 도서 등 다양한 리소스 목록을 확인해 보세요.