삽입 정렬: C를 사용한 알고리즘, C++, Java, Python 예

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

삽입 정렬은 한 번에 한 요소씩 반복하면서 요소를 올바른 위치에 배치하여 요소를 정렬하는 데 사용되는 비교 정렬 알고리즘 중 하나입니다.

각 요소는 이미 정렬된 목록에 순차적으로 삽입됩니다. 이미 정렬된 목록의 초기 크기는 XNUMX입니다. 삽입 정렬 알고리즘은 k번째 반복 후에 처음 k개 요소가 정렬되도록 보장합니다.

삽입정렬 알고리즘의 특징

삽입 정렬 알고리즘은 다음과 같은 중요한 특징을 가지고 있습니다.

• 이는 안정적인 정렬 기술이므로 동일한 요소의 상대적 순서를 변경하지 않습니다.
• 작은 데이터 세트에는 효율적이지만 큰 목록에는 효과적이지 않습니다.
• 삽입 정렬은 적응형이므로 부분적으로 정렬된 경우 총 단계 수가 줄어듭니다. 배열 효율적으로 사용할 수 있도록 입력으로 제공됩니다.

삽입 방법 Opera일?

삽입 정렬 알고리즘에서 삽입 연산은 정렬되지 않은 요소를 정렬하는 데 사용됩니다. 이미 정렬된 목록에 새 요소를 삽입하는 데 도움이 됩니다.

삽입 작업의 의사 코드:

N개 요소로 구성된 목록 A를 생각해 보세요.

A[N-1] is the element to be inserted in the sorted sublist A[0..N-2].
For i = N-1 to 1:
if A[i] < A[i-1], then swap A[i] and A[i-1]
else Stop   

위의 예에서는 이미 정렬된 목록에 새 요소 6이 삽입됩니다.

단계 1) A[5]의 왼쪽 인접 요소인 9 > 6과 비교하여 9와 6의 위치를 ​​바꿉니다. 이제 요소 6이 A[4]로 이동됩니다.

단계 2) 이제 A[4]와 A[3]을 비교하여 A[3] > A[4]를 확인하고 다시 6과 8의 위치를 ​​바꿉니다.

단계 3) 이제 A[3] > A[2]이 2과 3의 위치를 ​​바꾸므로 A[7]과 A[6]를 비교합니다.

단계 4) A[1]과 A[2]를 비교하고 A[1] < A[2]이므로 왼쪽 인접 요소가 더 이상 더 크지 않습니다. 이제 6이 올바르게 삽입되었다고 결론을 내리고 여기서 알고리즘을 중지합니다.

삽입 정렬의 작동 방식

위에서 논의한 삽입 연산은 삽입 정렬의 중추입니다. 삽입 프로시저는 모든 요소에서 실행되고, 결국 정렬된 목록을 얻습니다.

위의 예시 그림은 데이터 구조에서 삽입 정렬이 작동하는 모습을 보여줍니다. 처음에는 정렬된 하위 목록에 단 하나의 요소(4)만 있습니다. A[1](즉, 3)을 삽입한 후 정렬된 하위 목록의 크기는 2로 늘어납니다.

C++ 삽입정렬 프로그램

#include <iostream>
using namespace std;

int main(){
    //unsorted list
    int unsorted[] = {9,8,7,6,5,4,3,3,2,1};
    
    //size of list
    int size_unsorted = sizeof(unsorted) / sizeof(unsorted[0]); 

    //printing unsorted list
    cout << "\nUnsorted: ";
    for(int i = 0 ; i < size_unsorted ; i++){
        cout << unsorted[i] << " ";
    } 

    int current_element,temp;

    for(int i = 1; i < size_unsorted; i++){        
        current_element = unsorted[i];
        for(int j = i-1; j >= 0 && unsorted[j] > current_element; j--){
            //swapping if current element is lesser
            temp = unsorted[j+1];
            unsorted[j+1] = unsorted[j];
            unsorted[j] = temp;
        }
    }

    //printing sorted list
    cout << "\nSorted: ";
    for(int i = 0 ; i < size_unsorted ; i++){
        cout << unsorted[i] << " ";
    } 

    return 0;
}

출력:

Unsorted: 9 8 7 6 5 4 3 3 2 1 
Sorted: 1 2 3 3 4 5 6 7 8 9

삽입 정렬을 위한 C 코드

#include <stdio.h>
int main() {
    //unsorted list
    int unsorted[] = {9,8,7,6,5,4,3,3,2,1};

    //size of list
    int size_unsorted = sizeof(unsorted) / sizeof(unsorted[0]);

    //printing unsorted list
    printf("\nUnsorted: ");
    for(int i = 0 ; i < size_unsorted ; i++){
        printf("%d ", unsorted[i]);
    }

    int current_element, temp;

    for(int i = 1; i < size_unsorted; i++){
        current_element = unsorted[i];
        for(int j = i-1; j >= 0 && unsorted[j] > current_element; j--){
            //swapping if current element is lesser
            temp = unsorted[j+1];
            unsorted[j+1] = unsorted[j];
            unsorted[j] = temp;
        }
    }

    //printing sorted list
    printf("\nSorted: ");
    for(int i = 0 ; i < size_unsorted ; i++){
        printf("%d ", unsorted[i]);
    }

    return 0;
}

출력:

Output:
Unsorted: 9 8 7 6 5 4 3 3 2 1 
Sorted: 1 2 3 3 4 5 6 7 8 9

Python 삽입정렬 프로그램

#unsorted list
unsorted = [9,8,7,6,5,4,3,3,2,1]

#size of list
size_unsorted = len(unsorted)

#printing unsorted list
print("\nUnsorted: ", end="")
for i in range(size_unsorted):
    print(unsorted[i], end=" ")

for i in range(1, size_unsorted):
    current_element = unsorted[i]
    j = i - 1
    while j >= 0 and unsorted[j] > current_element:
        #swapping if current element is lesser
        unsorted[j+1], unsorted[j] = unsorted[j], unsorted[j+1]
        j -= 1

#printing sorted list
print("\nSorted: ", end="")
for i in range(size_unsorted):
    print(unsorted[i], end=" ")

출력:

Unsorted: 9 8 7 6 5 4 3 3 2 1 
Sorted: 1 2 3 3 4 5 6 7 8 9

삽입 정렬의 속성

삽입 정렬의 중요한 속성은 다음과 같습니다.

• 온라인 : 삽입 정렬은 요소를 받은 대로 정렬할 수 있습니다. 즉, 요소 ​​목록을 이미 정렬하고 목록에 요소를 더 추가한 경우 전체 정렬 절차를 다시 실행할 필요가 없습니다. 대신 새로 추가된 요소만 반복하면 됩니다.
• 내부: 삽입 정렬 알고리즘의 공간 복잡도는 일정하며 추가 공간이 필요하지 않습니다. 이 알고리즘은 요소를 제자리에서 정렬합니다.
• 안정된: 삽입 정렬에서는 값이 같으면 요소를 교환하지 않습니다. 예를 들어 두 요소 x와 y가 동일하고 정렬되지 않은 목록에서는 x가 y 앞에 나타나고, 정렬된 목록에서는 x가 y 앞에 나타납니다. 이는 삽입 정렬을 안정적으로 만듭니다.
• 적응 형 : A 정렬 알고리즘 입력 요소 또는 요소의 하위 집합이 이미 정렬되어 있는 경우 시간이 덜 걸리면 적응적입니다. 위에서 논의했듯이 삽입 정렬의 최상의 실행 시간은 O(N)이고 최악의 실행 시간은 O(N^2)입니다. 삽입 정렬은 적응형 정렬 알고리즘 중 하나입니다.

삽입 정렬의 복잡성

공간 복잡성

삽입 정렬은 요소를 정렬하는 데 추가 공간이 필요하지 않으며 공간 복잡도는 일정합니다. 즉, O(1)입니다.

시간 복잡성

삽입 정렬은 각 요소를 동시에 반복하므로 N개의 요소를 정렬하려면 N-1개의 패스가 필요합니다. 각 패스에서 요소가 이미 정렬되어 있으면 스왑을 XNUMX개 만들고, 요소가 내림차순으로 정렬되어 있으면 스왑을 만들 수 있습니다.

• 패스 1의 경우 필요한 최소 스왑은 1이고 필요한 최대 스왑은 XNUMX입니다.
• 패스 2의 경우 필요한 최소 스왑은 2이고 필요한 최대 스왑은 XNUMX입니다.
• 패스 N의 경우 필요한 최소 스왑은 XNUMX이고 필요한 최대 스왑은 N입니다.
• 최소 스왑은 0이므로 N번 패스를 반복하는 경우 최적의 시간 복잡도는 O(N)입니다.
• 총 최대 스왑은 (1+2+3+4+..+N) i. N(N+1)/2이고, 최악의 시간 복잡도는 O(N^2)입니다.

삽입 정렬의 중요한 시간 복잡도는 다음과 같습니다.

• 최악의 경우 복잡성: O(n2): 배열이 오름차순인데 내림차순으로 정렬하는 것이 최악의 시나리오입니다.
• 최고의 사례 복잡성: O(n): 최상의 경우 복잡성은 배열이 이미 정렬되어 있고, 외부 루프가 n번 실행되는 반면 내부 루프는 전혀 실행되지 않을 때 발생합니다. 비교 횟수는 n번뿐입니다. 따라서 이 경우 복잡성은 선형적입니다.
• 평균 케이스 복잡도: O(n2): 배열의 요소가 오름차순도 내림차순도 아닌 뒤죽박죽된 순서로 나타날 때 발생합니다.

제품 개요

• 삽입 정렬은 비교를 기반으로 하는 정렬 알고리즘 방법입니다.
• 이는 안정적인 정렬 기술이므로 동일한 요소의 상대적 순서를 변경하지 않습니다.
• 각 요소에 대해 삽입 연산을 사용하여 정렬된 하위 목록에 요소를 삽입합니다.
• 삽입 정렬은 내부 정렬 알고리즘입니다.
• 삽입 정렬의 최악 및 평균 시간 복잡도는 2차, 즉 O(N^XNUMX)입니다.
• 삽입 정렬에는 보조 공간이 필요하지 않습니다.