- Тойм
- Ерөнхий алгоритм
- Псевдокод
- Зураг
- C++ Жишээ
- Java Example
- Complexity Analysis Of The Insertion Sort Algorithm
- Conclusion
Сонгодог жишээнүүдээр оруулах эрэмбэлэхийг гүнзгий харах.
Оруулах эрэмбэлэх нь бидний гарт хөзөр тоглох байдлаар харж болох эрэмбэлэх арга юм. Бидний ямар ч картыг тавцанд оруулах эсвэл арилгах арга, оруулах эрэмбэлэх нь ижил төстэй байдлаар ажилладаг.
Оруулах эрэмбэлэх алгоритм нь Bubble сорт болон Сонголтоор эрэмбэлэх аргуудаас илүү үр дүнтэй боловч бусад аргуудаас үр ашиг багатай байдаг. Quicksort, Merge sort гэх мэт.
Тойм
Оруулах эрэмбэлэх техникт бид хоёр дахь элементээс эхэлж, эхний элементтэй харьцуулж, тавьдаг. зохих газар. Дараа нь бид дараагийн элементүүдэд энэ процессыг гүйцэтгэдэг.
Бид элемент бүрийг өмнөх бүх элементүүдтэй нь харьцуулж, элементийг зохих байрлалд нь байрлуулж эсвэл оруулдаг. Оруулах эрэмбэлэх арга нь цөөн тооны элемент бүхий массивуудад илүү тохиромжтой. Энэ нь холбосон жагсаалтыг эрэмбэлэхэд бас тустай.
Холбогдсон жагсаалт нь дараагийн элемент рүү заагчтай (дангаар нь холбосон жагсаалт бол) болон өмнөх элемент рүү (давхар холбогдсон жагсаалт бол) мөн заагчтай байна. ). Тиймээс холбосон жагсаалтад оруулах эрэмбэлэх аргыг хэрэгжүүлэхэд илүү хялбар болсон.
Энэ зааварт Оруулах эрэмбийн талаар бүгдийг судалъя.
Ерөнхий алгоритм
Алхам 1 : K = 1-ээс N-1 хүртэл 2-5-р алхамуудыг давтана
Алхам 2 : температурыг тохируулна = A[K]
3-р алхам : J = K тохируулна– 1
Алхам 4 : Температур =A[J]
A[J + 1] = A[J]
0 тохируулах үед давт>тогтоох J = J – 1[дотоод давталтын төгсгөл]
5-р алхам : тохируулах A[J + 1] = temp
[ давталтын төгсгөл]
Алхам 6 : гарах
Тиймээс оруулах эрэмбэлэх техникт бид эхний элементийг үргэлж эрэмбэлсэн гэж үздэг тул хоёр дахь элементээс эхэлнэ. . Дараа нь хоёр дахь элементээс сүүлчийн элемент хүртэл бид элемент бүрийг өмнөх бүх элементүүдтэй нь харьцуулж, тухайн элементийг зохих байрлалд нь оруулдаг.
Псевдокод
Псевдо код оруулах эрэмбийг доор өгөв.
procedure insertionSort(array,N ) array – array to be sorted N- number of elements begin int freePosition int insert_val for i = 1 to N -1 do: insert_val = array[i] freePosition = i //locate free position to insert the element whilefreePosition> 0 and array[freePosition -1] >insert_val do: array [freePosition] = array [freePosition -1] freePosition = freePosition -1 end while //insert the number at free position array [freePosition] = insert_val end for end procedure
Дээр өгөгдсөн бол Оруулах эрэмбэлэх псевдо код, дараа нь бид энэ аргыг дараах жишээнд харуулах болно.
Зураг
Ангилах массив нь дараах байдалтай байна:
Одоо дамжуулалт бүрээр бид одоогийн элементийг өмнөх бүх элементүүдтэй нь харьцуулж үздэг. Тиймээс эхний дамжуулалтад бид хоёр дахь элементээс эхэлнэ.
Тиймээс N тооны элемент агуулсан массивыг бүрэн ангилахын тулд N тооны дамжуулалт шаардлагатай.
Дээрх дүрслэлийг хүснэгт хэлбэрээр нэгтгэн дүгнэж болно:
| Дагалдах | Эрэмбэгүй жагсаалт | харьцуулалт | Ангилсанжагсаалт |
|---|---|---|---|
| 1 | {12,3,5,10,8,1} | {12,3} | {3,12,5,10,8,1} |
| 2 | {3,12,5,10,8,1} | {3,12,5} | {3,5,12,10,8,1} |
| 3 | { 3,5,12,10,8,1} | {3,5,12,10} | {3,5,10,12,8,1} |
| 4 | {3,5,10,12,8,1} | {3,5,10,12,8} | {3,5,8,10,12,1} |
| 5 | {3,5,8,10,12,1} | {3,5,8,10,12,1} | {1,3,5,8,10,12} |
| 6 | {} | {} | {1,3,5,8,10,12} |
Үүнд харуулав. Дээрх жишээн дээр бид эхний элементийг үргэлж эрэмбэлсэн гэж үздэг тул 2-р элементээс эхэлнэ. Тиймээс бид хоёр дахь элементийг эхнийхтэй нь харьцуулж эхэлж, хоёр дахь элемент нь эхнийхээс бага байвал байрлалыг солино.
Энэ харьцуулалт болон солих процесс нь хоёр элементийг зохих байранд нь байрлуулна. Дараа нь бид гурав дахь элементийг өмнөх (эхний болон хоёр дахь) элементүүдтэй харьцуулж, гурав дахь элементийг зохих газарт нь байрлуулах ижил процедурыг гүйцэтгэдэг.
Ийм байдлаар, дамжуулалт бүрт нэг элементийг байрлуулна. түүний газар. Эхний дамжуулалтын хувьд бид хоёр дахь элементийг оронд нь байрлуулна. Тиймээс ерөнхийдөө N элементийг зохих байранд нь байрлуулахын тулд бидэнд N-1 дамжуулалт хэрэгтэй.
Дараа нь бид C++ хэл дээр Insertion эрэмбэлэх техникийн хэрэгжилтийг үзүүлэх болно.
C++ Жишээ
#include using namespace std; int main () { int myarray[10] = { 12,4,3,1,15,45,33,21,10,2}; cout"\nInput list is \n"; for(int i=0;i10;i++) { cout ="" Output:
Input list is
12 4 3 1 15 45 33 21 10 2
Sorted list is
1 2 3 4 10 12 15 21 33 45
Next, we will see the Java implementation of the Insertion sort technique.
Java Example
public class Main { public static void main(String[] args) { int[] myarray = {12,4,3,1,15,45,33,21,10,2}; System.out.println("Input list of elements ..."); for(int i=0;i10;i++) { System.out.print(myarray[i] + " "); } for(int k=1; k=0 && temp = myarray[j]) { myarray[j+1] = myarray[j]; j = j-1; } myarray[j+1] = temp; } System.out.println("\nsorted list of elements ..."); for(int i=0;i10;i++) { System.out.print(myarray[i] + " "); } } } Output:
Input list of elements …
12 4 3 1 15 45 33 21 10 2
sorted list of elements …
1 2 3 4 10 12 15 21 33 45
In both the implementations, we can see that we begin sorting from the 2nd element of the array (loop variable j = 1) and repeatedly compare the current element to all its previous elements and then sort the element to place it in its correct position if the current element is not in order with all its previous elements.
Insertion sort works the best and can be completed in fewer passes if the array is partially sorted. But as the list grows bigger, its performance decreases. Another advantage of Insertion sort is that it is a Stable sort which means it maintains the order of equal elements in the list.
Complexity Analysis Of The Insertion Sort Algorithm
From the pseudo code and the illustration above, insertion sort is the efficient algorithm when compared to bubble sort or selection sort. Instead of using for loop and present conditions, it uses a while loop that does not perform any more extra steps when the array is sorted.
However, even if we pass the sorted array to the Insertion sort technique, it will still execute the outer for loop thereby requiring n number of steps to sort an already sorted array. This makes the best time complexity of insertion sort a linear function of N where N is the number of elements in the array.
Thus the various complexities for Insertion sort technique are given below:
Worst case time complexity O(n 2 ) Best case time complexity O(n) Average time complexity O(n 2 ) Space complexity O(1)
In spite of these complexities, we can still conclude that Insertion sort is the most efficient algorithm when compared with the other sorting techniques like Bubble sort and Selection sort.
Conclusion
Insertion sort is the most efficient of all the three techniques discussed so far. Here, we assume that the first element is sorted and then repeatedly compare every element to all its previous elements and then place the current element in its correct position in the array.
In this tutorial, while discussing Insertion sort we have noticed that we compare the elements using an increment of 1 and also they are contiguous. This feature results in requiring more passes to get the sorted list.
In our upcoming tutorial, we will discuss “Shell sort” which is an improvement over the Selection sort.
In shell sort, we introduce a variable known as “increment” or a “gap” using which we divide the list into sublists containing non-contiguous elements that “gap” apart. Shell sort requires fewer passes when compared to Insertion sort and is also faster.
In our future tutorials, we will learn about two sorting techniques, “Quicksort” and “Mergesort” which use “Divide and conquer” strategy for sorting data lists.