Python 삽입 정렬을 작성하는 방법

Python 삽입 정렬은 게임 카드 정렬과 유사합니다. 삽입 정렬을 사용하려면 정렬된 목록과 정렬되지 않은 목록의 두 가지 목록을 만듭니다. 해당 항목을 정렬할 때까지 정렬되지 않은 목록의 각 항목을 비교합니다. 삽입 정렬은 Python 언어의 일반적인 표준 알고리즘입니다.

손에 있는 카드 놀이를 분류해 본 적이 있습니까? 이것이 파이썬 삽입 정렬의 개념에 대해 생각하는 한 가지 방법입니다. 몇 가지 요소만으로 목록을 정렬해야 할 때 삽입 정렬이 도움이 됩니다.

삽입 정렬은 배열의 각 반복 후에 정렬되지 않은 요소를 올바른 위치에 배치합니다.

이 가이드에서는 삽입 정렬이 무엇이며 어떻게 작동하는지 설명합니다. 이 정렬 알고리즘을 시작할 수 있도록 예제를 참조하여 Python에서 삽입 정렬을 구현하는 방법을 논의할 것입니다.

Python 삽입 정렬이란 무엇입니까?

삽입 정렬은 목록을 정렬된 것과 정렬되지 않은 두 개의 하위 목록으로 나눕니다. 그런 다음 정렬되지 않은 목록의 각 요소를 비교하고 목록의 각 항목이 정렬될 때까지 계속 비교합니다.

삽입 정렬 알고리즘은 정렬된 항목을 정렬된 하위 목록으로 이동하고 정렬되지 않은 하위 목록에서 제거합니다. 두 하위 목록은 동일한 배열의 일부이지만 항목이 정렬되었는지 여부를 구별합니다.

삽입 정렬은 카드 게임에서 손에 있는 카드 세트를 정렬하는 것과 같은 방식으로 생각할 수 있습니다.

카드 목록을 하나씩 이동하고 서로 비교합니다. 정렬된 카드는 손의 왼쪽에 나타납니다. 정렬되지 않은 카드는 모두 정렬할 때까지 오른쪽에 표시됩니다.

참가자의 81%는 부트캠프에 참석한 후 기술 직업 전망에 대해 더 자신감을 느꼈다고 말했습니다. 지금 부트캠프에 참여하십시오.

부트캠프 졸업생은 부트캠프 시작부터 첫 직장을 찾는 데까지 6개월도 채 걸리지 않았습니다.

Python 삽입 정렬은 어떻게 작동합니까?

삽입 정렬 알고리즘을 사용하여 비즈니스를 시작하고 배열을 정렬해 보겠습니다. 다음 정렬되지 않은 배열을 고려하십시오.

삽입 정렬에서는 첫 번째 요소가 정렬된 것으로 간주됩니다. 두 번째 요소는 자체 변수에 저장됩니다. 이 변수를 current_number라고 합니다. .

current_number를 비교해야 합니다. 배열의 첫 번째 위치에 항목이 있습니다. 현재_번호인 경우 첫 번째 요소보다 크면 같은 위치에 유지됩니다. 그렇지 않으면 current_number가 첫 번째 요소의 맨 앞으로 이동합니다.

4는 9보다 크지 않으므로 이 두 요소는 자리를 바꿉니다.

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

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

• 3이 9보다 큽니까? 아니요, 따라서 9 앞에 3이 삽입됩니다.
• 3이 4보다 큽니까? 아니요, 따라서 3은 4보다 먼저 이동됩니다.

이제 목록은 다음과 같습니다.

이 프로세스는 목록이 정렬될 때까지 반복됩니다. 목록에는 4개의 값만 포함되어 있기 때문에 수행할 비교 세트가 하나만 더 있습니다. 다음 반복에서 5는 current_number가 됩니다.

• 5가 9보다 큽니까? 아니요, 9시 전에 5번 이동합니다.

5가 정렬된 목록의 마지막 숫자이기 때문에 더 이상 비교하지 않습니다. 이 반복 후에 배열이 정렬되었습니다.

간단합니다! 삽입 정렬에서 우리는 항상 목록의 왼쪽에 정렬된 값을 유지했습니다. 정렬되지 않은 값이 오른쪽에 나타납니다.

목록의 각 반복에 대해 current_number를 정렬되지 않은 모든 항목과 비교했습니다. 이 프로세스는 목록이 정렬될 때까지 반복되었습니다.

Python에서 삽입 정렬을 작성하는 방법

종이에 삽입 정렬을 통해 모든 것이 훌륭하고 잘 진행됩니다. 이제 핵심을 살펴보고 Python에서 삽입 정렬을 구현할 때입니다.

정렬 함수 작성

정렬을 수행하는 Python 함수를 작성하여 시작하겠습니다.

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에서 함수를 사용하여 목록의 모든 숫자를 반복하는 Python for 루프를 만듭니다. 그런 다음 목록의 첫 번째 요소를 Python 변수 current_number에 할당하여 정렬된 값으로 설정합니다. .

정렬되지 않은 Python 목록의 모든 항목(current_number 이후의 모든 항목)을 반복합니다. 그런 다음 current_number를 왼쪽에 있는 각 숫자와 비교합니다. 이러한 일이 발생하면 current_number 값을 설정합니다. 목록에서 그 뒤에 오는 요소와 동일해야 합니다.

메인 프로그램 작성

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

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

print(numbers)

코드 반환:

[3, 4, 5, 9]

우리 목록은 오름차순으로 정렬되었습니다! 여기까지 온 것을 축하합니다.

Python 삽입 정렬:내림차순

삽입 정렬은 숫자를 내림차순으로 정렬할 수 있습니다. 이를 수행하려면 while 루프에서 "보다 작음"(>) 기호를 반전하고 보다 큼 기호로 만들어야 합니다.

내가>=0이고 current_number인 동안> toSort[i]:

위의 예에서 대체된 이 코드 줄은 목록의 항목을 역순으로 정렬합니다.

언제 삽입 정렬을 사용해야 합니까?

삽입 정렬은 목록의 데이터가 거의 정렬되거나 작은 목록을 정렬할 때 가장 잘 사용됩니다. 큰 목록을 정렬하는 데 사용할 수 있는 보다 효율적인 알고리즘이 있습니다. 예를 들어 병합 정렬이나 빠른 정렬이 더 빠릅니다.

삽입 정렬은 버블 정렬보다 빠릅니다.

삽입 정렬은 어쨌든 알아두면 유용합니다. 삽입 정렬을 구현하는 방법을 알면 사용할 수 있는 다른 유형의 정렬을 얻을 수 있습니다.

삽입 정렬은 다른 정렬 알고리즘보다 덜 복잡합니다. 삽입 정렬을 작성하는 방법을 배운 후에는 병합 정렬과 같은 더 복잡한 정렬에 대해 더 많이 배우게 됩니다.

Python 삽입 정렬:복잡성 분석

모든 알고리즘과 마찬가지로 최고, 최악 및 평균 복잡성을 고려하는 것이 중요합니다. 이를 통해 알고리즘이 작업을 수행하는 데 얼마나 효과적인지(이 경우 목록 정렬)에 대한 통찰력을 얻을 수 있습니다.

최악의 경우와 평균 복잡도는 O(n2)입니다. 즉, 목록에서 정렬할 값을 더 추가하면 알고리즘이 기하급수적으로 느려집니다.

가장 좋은 시나리오는 O(n)입니다. 이것은 정렬된 목록에서 알고리즘을 실행할 때 발생합니다. 알고리즘은 항목이 정렬되었는지 확인한 다음 실행을 중지합니다.

Big O 표기법에 대한 2부작 시리즈에서 알고리즘 복잡성을 표현하는 방법에 대해 자세히 알아볼 수 있습니다.

결론

삽입 정렬은 카드 게임에서 손에 있는 카드 목록을 정렬하는 것과 같습니다. 정렬된 항목 목록과 정렬할 항목 목록의 두 가지 목록을 유지합니다. 그런 다음 정렬되지 않은 항목 목록을 살펴보고 모든 항목이 정렬될 때까지 위치를 섞습니다.

더 많은 Python 프로그래밍 언어 리소스를 찾고 있습니까? 전체 Python 학습 방법 가이드를 확인하세요. Python을 배우는 방법에 대한 최고의 팁과 온라인 과정, 책 및 기타 리소스 목록을 찾을 수 있습니다.