이번 포스팅에서는 삽입정렬 알고리즘에 대해 알아보겠습니다. 삽입 정렬의 작업 절차도 간단합니다. 이 기사는 학생들이 시험에서 문제로 삽입 유형을 직면할 수 있기 때문에 학생들에게 매우 도움이 되고 흥미로울 것입니다. 따라서 주제에 대해 토론하는 것이 중요합니다.
삽입 정렬은 손에 들고 있는 카드를 정렬하는 것과 유사하게 작동합니다. 첫 번째 카드는 카드 게임에서 이미 정렬되어 있다고 가정하고 정렬되지 않은 카드를 선택합니다. 선택한 정렬되지 않은 카드가 첫 번째 카드보다 크면 오른쪽에 배치됩니다. 그렇지 않으면 왼쪽에 배치됩니다. 마찬가지로, 정렬되지 않은 모든 카드를 가져와 정확한 위치에 놓습니다.
삽입 정렬에도 동일한 접근 방식이 적용됩니다. 삽입 정렬의 기본 아이디어는 먼저 하나의 요소를 가져와서 정렬된 배열을 통해 반복하는 것입니다. 사용이 간편하지만 평균 및 최악의 경우 삽입 정렬의 시간 복잡도가 높기 때문에 대용량 데이터 세트에는 적합하지 않습니다. 에2) , 여기서 n은 항목 수입니다. 삽입 정렬은 힙 정렬, 퀵 정렬, 병합 정렬 등과 같은 다른 정렬 알고리즘보다 효율성이 떨어집니다.
삽입 정렬에는 다음과 같은 다양한 장점이 있습니다.
- 간단한 구현
- 소규모 데이터 세트에 효율적
- 적응형, 즉 이미 실질적으로 정렬된 데이터 세트에 적합합니다.
이제 삽입정렬 알고리즘을 살펴보자.
연산
삽입 정렬을 수행하는 간단한 단계는 다음과 같습니다.
1 단계 - 요소가 첫 번째 요소인 경우 이미 정렬되어 있다고 가정합니다. 1을 반환합니다.
타이프스크립트 화살표 기능
2 단계 - 다음 요소를 선택하고 별도로 저장합니다. 열쇠.
3단계 - 이제 비교해 보세요. 열쇠 정렬된 배열의 모든 요소를 포함합니다.
4단계 - 정렬된 배열의 요소가 현재 요소보다 작으면 다음 요소로 이동합니다. 그렇지 않으면 배열의 더 큰 요소를 오른쪽으로 이동합니다.
5단계 - 값을 삽입하세요.
6단계 - 배열이 정렬될 때까지 반복합니다.
삽입정렬 알고리즘의 작동
이제 삽입 정렬 알고리즘의 작동 방식을 살펴보겠습니다.
삽입 정렬 알고리즘의 작동을 이해하기 위해 정렬되지 않은 배열을 살펴보겠습니다. 예제를 통해 삽입 정렬을 이해하는 것이 더 쉬울 것입니다.
배열의 요소는 다음과 같습니다.
처음에는 삽입 정렬에서 처음 두 요소를 비교합니다.
여기서 31은 12보다 큽니다. 이는 두 요소가 이미 오름차순으로 정렬되어 있음을 의미합니다. 따라서 현재로서는 12가 정렬된 하위 배열에 저장되어 있습니다.
이제 다음 두 요소로 이동하여 비교해 보세요.
여기서 25는 31보다 작습니다. 따라서 31은 올바른 위치에 있지 않습니다. 이제 31을 25로 바꿉니다. 스와핑과 함께 삽입 정렬은 정렬된 배열의 모든 요소를 검사합니다.
현재 정렬된 배열에는 단 하나의 요소(예: 12)만 있습니다. 따라서 25는 12보다 큽니다. 따라서 정렬된 배열은 교체 후에도 정렬된 상태를 유지합니다.
이제 정렬된 배열의 두 요소는 12와 25입니다. 다음 요소인 31과 8로 이동합니다.
31과 8은 모두 정렬되지 않았습니다. 그러니 바꿔보세요.
교체한 후에는 요소 25와 8이 정렬 해제됩니다.
그러니 바꿔보세요.
이제 요소 12와 8은 정렬되지 않았습니다.
그러니 그것들도 바꿔보세요.
이제 정렬된 배열에는 8, 12, 25의 세 가지 항목이 있습니다. 다음 항목인 31, 32로 이동합니다.
따라서 이미 정렬되어 있습니다. 이제 정렬된 배열에는 8, 12, 25 및 31이 포함됩니다.
다음 요소인 32와 17로 이동합니다.
17은 32보다 작습니다. 따라서 서로 바꿔보세요.
스와핑하면 31과 17이 정렬되지 않습니다. 그러니 그것들도 바꿔보세요.
이제 교체하면 25와 17이 정렬되지 않습니다. 따라서 다시 Swap을 수행하십시오.
이제 배열이 완전히 정렬되었습니다.
삽입 정렬의 복잡성
이제 최선의 경우, 평균적인 경우, 최악의 경우 삽입 정렬의 시간 복잡도를 살펴보겠습니다. 삽입 정렬의 공간 복잡도도 살펴보겠습니다.
1. 시간 복잡도
| 사례 | 시간 복잡도 |
|---|---|
| 최선의 경우 | 에) |
| 평균 사례 | 에2) |
| 최악의 경우 | 에2) |
2. 공간 복잡성
| 공간 복잡도 | 오(1) |
| 안정적인 | 예 |
- 삽입정렬의 공간복잡도는 O(1)이다. 삽입정렬에서는 Swap을 위해 별도의 변수가 필요하기 때문이다.
삽입정렬 구현
이제 다양한 프로그래밍 언어의 삽입 정렬 프로그램을 살펴보겠습니다.
프로그램: C언어에서 삽입정렬을 구현하는 프로그램을 작성해보세요.
#include void insert(int a[], int n) /* function to sort an aay with insertion sort */ { int i, j, temp; for (i = 1; i <n; i++) { temp="a[i];" j="i" - 1; while(j>=0 && temp <= 17 a[j]) * move the elements greater than temp to one position ahead from their current position* { a[j+1]="a[j];" j="j-1;" } void printarr(int a[], int n) function print array i; for (i="0;" i < n; i++) printf('%d ', a[i]); main() a[]="{" 12, 31, 25, 8, 32, }; n="sizeof(a)" sizeof(a[0]); printf('before sorting are -
'); printarr(a, n); insert(a, printf('
after return 0; pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/03/insertion-sort-algorithm-18.webp" alt="Insertion Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement insertion sort in python.</p> <pre> def insertionSort(a): # Function to implement insertion sort for i in range(1, len(a)): temp = a[i] # Move the elements greater than temp to one position #ahead from their current position j = i-1 while j >= 0 and temp <a[j] : a[j + 1]="a[j]" j="j-1" def printarr(a): # function to print the array for i in range(len(a)): (a[i], end=" " ) a="[70," 15, 2, 51, 60] print('before sorting elements are - ') printarr(a) insertionsort(a) print('
after < pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/03/insertion-sort-algorithm-19.webp" alt="Insertion Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement insertion sort in C++ language.</p> <pre> #include using namespace std; void insert(int a[], int n) /* function to sort an aay with insertion sort */ { int i, j, temp; for (i = 1; i <n; i++) { temp="a[i];" j="i" - 1; while(j>=0 && temp <= 2 a[j]) * move the elements greater than temp to one position ahead from their current position* { a[j+1]="a[j];" j="j-1;" } void printarr(int a[], int n) function print array i; for (i="0;" i < n; i++) cout << a[i] <<' '; main() a[]="{" 89, 45, 35, 8, 12, }; n="sizeof(a)" sizeof(a[0]); cout<<'before sorting are - '<<endl; printarr(a, n); insert(a, cout<<'
after return 0; pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/03/insertion-sort-algorithm-20.webp" alt="Insertion Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement insertion sort in C# language.</p> <pre> using System; class Insertion { static void insert(int[] a) /* function to sort an aay with insertion sort */ { int i, j, temp; int n = a.Length; for (i = 1; i <n; i++) { temp="a[i];" j="i" - 1; while(j>=0 && temp <= 12 a[j]) * move the elements greater than temp to one position ahead from their current position* { a[j+1]="a[j];" j="j-1;" } static void printarr(int[] a) function print array int i; n="a.Length;" for (i="0;" i < n; i++) console.write(a[i] + ' '); main() int[] a="{" 98, 54, 53, 18, 21, }; console.write('before sorting are -
'); printarr(a); insert(a); console.write('
after pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/03/insertion-sort-algorithm-21.webp" alt="Insertion Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement insertion sort in Java.</p> <pre> public class Insert { void insert(int a[]) /* function to sort an aay with insertion sort */ { int i, j, temp; int n = a.length; for (i = 1; i <n; i++) { temp="a[i];" j="i" - 1; while(j>=0 && temp <= 22 a[j]) * move the elements greater than temp to one position ahead from their current position* { a[j+1]="a[j];" j="j-1;" } void printarr(int a[]) function print array int i; n="a.length;" for (i="0;" i < n; i++) system.out.print(a[i] + ' '); public static main(string[] args) a[]="{" 92, 50, 5, 20, 11, }; insert i1="new" insert(); system.out.println('
before sorting are - i1.printarr(a); i1.insert(a); system.out.println('
after system.out.println(); pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/03/insertion-sort-algorithm-22.webp" alt="Insertion Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement insertion sort in PHP.</p> <pre> <?php $a = array( 92, 50, 5, 20, 11, 22 ); function printArray($a) { for($i = 0; $i < 6; $i++) { print_r($a[$i]); echo ' '; } } echo 'Before sorting array elements are - <br>'; printArray($a); for ($i = 1; $i = 0 && $temp <= $a[$j]) * move the elements greater than temp to one position ahead from their current position* { $a[$j+1]="$a[$j];" $j="$j-1;" } echo ' <br> After sorting array elements are - <br>'; printArray($a); ?> </=></pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/03/insertion-sort-algorithm-23.webp" alt="Insertion Sort Algorithm"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <p>This article was not only limited to the algorithm. We have also discussed the algorithm's complexity, working, and implementation in different programming languages.</p> <hr></=></n;></pre></=></n;></pre></=></n;></pre></a[j]></pre></=></n;> 산출:
이것이 기사의 전부입니다. 이 기사가 귀하에게 도움이 되고 유익한 정보가 되기를 바랍니다.
이 글은 알고리즘에만 국한된 것이 아닙니다. 또한 알고리즘의 복잡성, 작동 및 다양한 프로그래밍 언어에서의 구현에 대해서도 논의했습니다.