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

게시물How to Write Insertion Sort in Go은 Qvault에 처음 등장했습니다.

삽입 정렬은 한 번에 한 항목씩 최종 정렬 목록을 작성합니다. 퀵 정렬 또는 merge sort 과 같은 고급 알고리즘보다 큰 목록에서 훨씬 덜 효율적입니다. 삽입 정렬은 카드 놀이를 손에 들고 있는 것처럼 작동하는 간단한 알고리즘입니다. 슬라이스는 먼저 정렬된 섹션과 정렬되지 않은 섹션으로 분할된 다음 정렬되지 않은 섹션의 값이 정렬된 섹션의 올바른 위치에 삽입됩니다.

삽입 정렬 알고리즘의 전체 예

func insertionSort(arr []int) []int {
    for i := 0; i < len(arr); i++ {
        for j := i; j > 0 && arr[j-1] > arr[j]; j-- {
            arr[j], arr[j-1] = arr[j-1], arr[j]
        }
    }
    return arr
}
<small id="shcb-language-1"><span>Code language:</span> <span>Go</span> <span>(</span><span>go</span><span>)</span></small>

보시다시피 insertionSort() 함수는 중첩된 for 루프에서 전체 슬라이스를 반복하여 시작합니다. 내부 for 루프의 작업은 각 반복에 대해 하나의 값을 소비하고 인덱스i 앞의 모든 요소인 정렬된 출력 목록을 늘리는 것입니다. 반복할 때마다 삽입 정렬은 입력 데이터에서 하나의 요소를 제거하고 정렬된 첫 번째 섹션 내에서 해당 요소가 속한 위치를 찾아 거기에 삽입합니다. 입력 요소가 남지 ​​않을 때까지 반복합니다.

코드에서 삽입 정렬 사용

func main() {

    fmt.Println(insertionSort([]int{5,3,2,1,0,4))
    // prints
    // [0, 1, 2, 3, 4, 5]
}

<small id="shcb-language-2"><span>Code language:</span> <span>Go</span> <span>(</span><span>go</span><span>)</span></small>

삽입 정렬을 사용하는 이유는 무엇입니까?

삽입 정렬의 Big O 복잡성은 O(n^2) 입니다. 이것이 최악의 복잡성이기 때문입니다. 삽입 정렬의 외부 루프는 n번 실행되는 반면 내부 루프는 입력에 따라 다릅니다. 최악의 경우(역 정렬 배열) 내부 루프도 실행됩니다n. 최상의 경우(정렬된 배열) 내부 루프가 즉시 중단되어 전체 복잡성이 O(n) 가 됩니다.

bubble sort 과 같이 알고리즘은 범용 프로덕션 용도로는 너무 느리지만 훌륭한 학습 도구가 될 수 있습니다. 다음은 삽입 정렬의 몇 가지 추가 속성입니다.

간단한 구현, 쓰기 쉬움

매우 작은 데이터 세트의 경우 빠름

버블 정렬과 같은 다른 단순 정렬 ​​알고리즘보다 빠름

적응형: 부분적으로 정렬된 데이터 세트의 경우 더 빠름

안정적: 키가 같은 요소의 상대적 순서를 변경하지 않습니다

.

인플레이스: 일정한 양의 메모리만 필요함

온라인: 목록을 받는 대로 정렬할 수 있습니다

.

일부 프로덕션 정렬 구현에서는 특정 임계값(10개와 같이 매우 작음) 아래의 매우 작은 입력에 대해 병합 정렬을 사용합니다. 삽입 정렬은 다음과 같은 이유로 더 빠른 일부 알고리즘보다 매우 작은 목록에 더 좋습니다.

재귀 오버헤드가 없습니다

.

작은 메모리 공간

위에서 설명한 대로 안정적인 정렬입니다

.

조치를 취하고 코딩을 할 준비가 되셨습니까?

Try out our coding courses for free

Join our Discord community

질문이나 의견이 있으십니까?

질문이나 의견이 있으면 트위터에서 나를 팔로우하고 연락하십시오. 기사에서 실수를 한 경우 반드시 let me know 수정하여 수정할 수 있도록 해주세요!