삽입 정렬 알고리즘 : Go-lang 및 Python 구현.

삽입 정렬 알고리즘

배열 기반 시퀀스의 경우. 배열의 첫 번째 요소부터 시작합니다. 단일 요소만 있는 배열
요소 자체는 이미 기본적으로 정렬되어 있습니다.

이제 동일한 유형의 임의의 두 번째 요소를 추가하겠습니다(이 경우 정수 사용). 배열에 추가하는 두 번째 요소가 이전에 추가한 첫 번째 요소보다 작으면 더 작은 두 번째 요소가 되도록 교체합니다. 더 큰 첫 번째 요소가 두 번째 위치로 강등되는 동안 첫 번째 위치로 이동합니다.

이제 추가하려는 세 번째 요소를 추가하겠습니다. 이미 두 개의 요소로 채워진 배열의 올바른 위치에 이 세 번째 요소를 고정하려면 이 세 번째 요소를 이미 배열을 채우고 있는 두 개의 요소와 비교해야 합니다.

이렇게 될 것입니다.

1 - 이 세 번째 요소가 두 번째 요소보다 작습니까? 그렇다면 두 번째 위치로 이동하고 이전에 두 번째 위치를 차지했던 요소가 세 번째 위치로 강등됩니다. 두 번째 위치 요소보다 작지 않은 경우(즉, 세 개의 배열 요소 중 가장 큰 경우 세 번째 위치를 차지하도록 합니다)

2 - 세 번째 요소가 두 번째 요소보다 작은 경우 원래 두 번째 요소를 대체한 후 이제 두 번째 위치를 차지합니다. 이제 첫 번째 요소와 비교하여 첫 번째 요소보다 작으면 가장 작은 요소인 첫 번째 위치로 이동하여 원래 가장 작은 요소를 두 번째 위치로 대체합니다.

3 - 배열에 새로 추가될 때마다 위의 단계를 반복하여 해당 요소의 올바른 위치를 찾습니다.

위의 설명 알고리즘을 아래 의사 코드로 표현할 수 있습니다.

Algorithm InsertSort(Arr):
    input: an Array Arr of n comparable elements
    Output: The array Arr with elements rearranged in nondecreasing order
    for k from 1 to n - 1 do
        Insert Arr[k] at its proper location within Arr[0],Arr[1],...Arr[k]

파이썬에서 이 알고리즘의 구현은 다음과 같습니다.

def InsertSort(Arr):
    for k in range(1, len(Arr)):
        currval = Arr[k]
        j = k
        while j > 0 and Arr[j-1] > currval:
            Arr[j] = Arr[j-1]
            j -= 1
        Arr[j] = currval    
    return Arr

위의 코드에서 우리는 외부 루프를 사용하여 각 요소를 차례로 고려하고 내부 루프는 새로 고려된 요소를 해당 요소에 상대적인 적절한 위치로 이동합니다.
(정렬된) 왼쪽에 있는 요소의 하위 배열입니다.

위의 파이썬 구현은 줄마다 줄, 논리 논리를 Go-lang으로 번역할 때 아래 코드가 됩니다.
또한 go-lang 함수에 대한 입력은 슬라이스입니다. Go-lang에서 슬라이스는 필요에 따라 확장 및 축소할 수 있는 동적 배열의 세그먼트입니다. 배열과 마찬가지로 슬라이스는 색인을 생성할 수 있으며 길이가 있습니다. 슬라이스 용량 및 길이 속성이 있습니다.

func InsertSort(Arr []int) []int{
    var x = len(items)
    for n := 1;n < x;n++ {
        v := n
        for v > 0 {
            if Arr[v-1] > Arr[v] {
               Arr[v-1], Arr[v] = Arr[v], Arr[v-1]
            }
         v = v - 1
        }
    }
   return Arr
}

안녕 나중에 보자.