삽입 정렬을 위한 Python 프로그램
삽입 정렬은 우리가 손에 들고 있는 카드를 정렬하는 방식으로 작동하는 간단한 정렬 알고리즘입니다.
삽입 정렬을 위한 Python 프로그램
insertSort 함수는 배열 arr을 입력으로 사용합니다. 먼저 배열의 길이(n)를 계산합니다. 길이가 0 또는 1이면 요소가 0 또는 1인 배열이 이미 정렬된 것으로 간주되므로 함수는 즉시 반환됩니다.
두 개 이상의 요소가 있는 배열의 경우 함수는 두 번째 요소부터 시작하여 배열을 반복합니다. 현재 요소(키라고 함)를 가져와서 그 앞에 있는 배열의 정렬된 부분에 있는 요소와 비교합니다. 키가 정렬된 부분의 요소보다 작은 경우 함수는 해당 요소를 오른쪽으로 이동하여 키를 위한 공간을 만듭니다. 이 프로세스는 키의 올바른 위치를 찾을 때까지 계속되며 그런 다음 해당 위치에 키가 삽입됩니다.
제공된 예제에서는 삽입 정렬 알고리즘을 사용한 정렬 프로세스를 보여줍니다. 초기 배열 [12, 11, 13, 5, 6]에는 insertSort 함수가 적용됩니다. 정렬 후 배열은 [5, 6, 11, 12, 13]이어야 합니다. 코드는 정렬된 배열을 최종 출력으로 인쇄합니다.
파이썬
def> insertionSort(arr):> > n> => len> (arr)> # Get the length of the array> > > if> n <> => 1> :> > return> # If the array has 0 or 1 element, it is already sorted, so return> > for> i> in> range> (> 1> , n):> # Iterate over the array starting from the second element> > key> => arr[i]> # Store the current element as the key to be inserted in the right position> > j> => i> -> 1> > while> j>> => 0> and> key # Move elements greater than key one position ahead arr[j+1] = arr[j] # Shift elements to the right j -= 1 arr[j+1] = key # Insert the key in the correct position # Sorting the array [12, 11, 13, 5, 6] using insertionSort arr = [12, 11, 13, 5, 6] insertionSort(arr) print(arr)> |
산출:
Sorted array is: [5, 6, 11, 12, 13]
시간 복잡도: O(N 2 )
보조 공간: O(1)
전체 기사를 참조하세요. 삽입 정렬 상세 사항은!
