General Algorithm<\/p>\n\n\n\n
Step 1<\/strong>: For i = 0 to N-1 repeat Step 2<\/p>\n\n\n\n Step 2<\/strong>: For J = i + 1 to N \u2013 I repeat<\/p>\n\n\n\n Step 3<\/strong>: if A[J] > A[i]<\/p>\n\n\n\n Swap A[J] and A[i]<\/p>\n\n\n\n [End of Inner for loop]<\/p>\n\n\n\n [End if Outer for loop]<\/p>\n\n\n\n Step 4<\/strong>: Exit<\/p>\n\n\n\n Here is a pseudo-code for bubble sort algorithm, where we traverse the list using two iterative loops.<\/p>\n\n\n\n In the first loop, we start from the 0th element and in the next loop, we start from an adjacent element. In the inner loop body, we compare each of the adjacent elements and swap them if they are not in order. At the end of each iteration of the outer loop, the heaviest element bubbles up at the end.<\/p>\n\n\n\n Pseudocode<\/strong><\/p>\n\n\n\n Procedure bubble_sort (array , N) Array entirely sorted.<\/p>\n\n\n\n The above illustration can be summarized in a tabular form as shown below:<\/strong><\/p>\n\n\n\n As shown in the illustration, with every pass, the largest element bubbles up to the last thereby sorting the list with every pass. As mentioned in the introduction, each element is compared to its adjacent element and swapped with one another if they are not in order.<\/p>\n\n\n\n Thus as shown in the illustration above, at the end of the first pass, if the array is to be sorted in ascending order, the largest element is placed at the end of the list. For the second pass, the second largest element is placed at the second last position in the list and so on.<\/p>\n\n\n\n When we reach N-1 (where N is a total number of elements in the list) passes, we will have the entire list sorted.<\/p>\n\n\n\n <\/p>\n\n\n\n The selection sort technique first selects the smallest element in the array and swaps it with the first element in the array.<\/p>\n\n\n\n Next, it swaps the second smallest element in the array with the second element and so on. Thus for every pass, the smallest element in the array is selected and put in its proper position until the entire array is sorted.<\/p>\n\n\n\n Selection sort is quite a straightforward sorting technique as the technique only involves finding the smallest element in every pass and placing it in the correct position.<\/p>\n\n\n\n Selection sort works efficiently when the list to be sorted is of small size but its performance is affected badly as the list to be sorted grows in size.<\/p>\n\n\n\n Hence we can say that selection sort is not advisable for larger lists of data.<\/p>\n\n\n\n General Algorithm<\/p>\n\n\n\n The General Algorithm for selection sort is given below:<\/p>\n\n\n\n Selection Sort (A, N)<\/strong><\/p>\n\n\n\n Step 1<\/strong>: Repeat Steps 2 and 3 for K = 1 to N-1<\/p>\n\n\n\n Step 2<\/strong>: Call routine smallest(A, K, N,POS)<\/p>\n\n\n\n Step 3<\/strong>: Swap A[K] with A [POS]<\/p>\n\n\n\n [End of loop]<\/p>\n\n\n\n Step 4<\/strong>: EXIT<\/p>\n\n\n\n Routine smallest (A, K, N, POS)<\/strong><\/p>\n\n\n\n Pseudocode For Selection Sort<\/p>\n\n\n\n Procedure selection_sort(array,N)<\/p>\n\n\n\n array \u2013 array of items to be sorted<\/p>\n\n\n\n N \u2013 size of array<\/p>\n\n\n\n begin<\/p>\n\n\n\n for <\/strong>I = 1 to N-1<\/p>\n\n\n\n begin<\/p>\n\n\n\n set min = i<\/p>\n\n\n\n for <\/strong>j = i+1 to N<\/p>\n\n\n\n begin<\/p>\n\n\n\n if <\/strong>array[j] < array[min] then<\/p>\n\n\n\n min = j;<\/p>\n\n\n\n end if<\/strong><\/p>\n\n\n\n end for<\/strong><\/p>\n\n\n\n \/\/swap the minimum element with current element<\/p>\n\n\n\n if <\/strong>minIndex != I then<\/p>\n\n\n\n swap array[min[] and array[i]<\/p>\n\n\n\n end if<\/strong><\/p>\n\n\n\n end for<\/strong><\/p>\n\n\n\n end procedure<\/p>\n\n\n\n An example to illustrate this selection sort algorithm is shown below.<\/p>\n\n\n\n Illustration<\/p>\n\n\n\n From the illustration, we see that with every pass the next smallest element is put in its correct position in the sorted array. From the above illustration, we see that in order to sort an array of 5 elements, four passes were required. This means in general, to sort an array of N elements, we need N-1 passes in total.<\/p>\n\n\n\n <\/p>\n\n\n\n Insertion sort is a sorting technique which can be viewed in a way which we play cards at hand. The way we insert any card in a deck or remove it, insertion sorts works in a similar way.<\/p>\n\n\n\n Insertion sort algorithm technique is more efficient than the Bubble sort and Selection sort techniques but is less efficient than the other techniques like Quicksort and Merge sort.<\/p>\n\n\n\n In the insertion sort technique, we start from the second element and compare it with the first element and put it in a proper place. Then we perform this process for the subsequent elements.<\/p>\n\n\n\n We compare each element with all its previous elements and put or insert the element in its proper position. Insertion sort technique is more feasible for arrays with a smaller number of elements. It is also useful for sorting linked lists.<\/p>\n\n\n\n Linked lists have a pointer to the next element (in case of a singly linked list) and a pointer to the previous element as well (in case of a doubly linked list). Hence it becomes easier to implement insertion sort for a linked list.<\/p>\n\n\n\n Let us explore all about Insertion sort in this tutorial.<\/em><\/strong><\/p>\n\n\n\n General Algorithm<\/p>\n\n\n\n Step 1<\/strong>: Repeat Steps 2 to 5 for K = 1 to N-1<\/p>\n\n\n\n Step 2<\/strong>: set temp = A[K]<\/p>\n\n\n\n Step 3<\/strong>: set J = K \u2013 1<\/p>\n\n\n\n Step 4<\/strong>: Repeat while temp <=A[J]<\/p>\n\n\n\n set A[J + 1] = A[J]<\/p>\n\n\n\n set J = J \u2013 1<\/p>\n\n\n\n [end of inner loop]<\/p>\n\n\n\n Step 5<\/strong>: set A[J + 1] = temp<\/p>\n\n\n\n [end of loop]<\/p>\n\n\n\n Step 6<\/strong>: exit<\/p>\n\n\n\n Thus, in the insertion sort technique, we start from the second element as we assume that the first element is always sorted. Then from the second element to the last element, we compare each element to all of its previous elements and the put that element in the proper position.<\/p>\n\n\n\n Pseudocode<\/p>\n\n\n\n The pseudo code for insertion sort is given below.<\/strong><\/p>\n\n\n\n procedure insertionSort(array,N )<\/p>\n\n\n\n array \u2013 array to be sorted<\/p>\n\n\n\n N- number of elements<\/p>\n\n\n\n begin<\/p>\n\n\n\n int <\/strong>freePosition<\/p>\n\n\n\n int <\/strong>insert_val<\/p>\n\n\n\n for <\/strong>i = 1 to N -1 do<\/strong>:<\/p>\n\n\n\n insert_val = array[i]<\/p>\n\n\n\n freePosition = i<\/p>\n\n\n\n \/\/locate free position to insert the element<\/p>\n\n\n\n whilefreePosition> 0 and array[freePosition -1] >insert_val do<\/strong>:<\/p>\n\n\n\n array [freePosition] = array [freePosition -1]<\/p>\n\n\n\n freePosition = freePosition -1<\/p>\n\n\n\n end while<\/strong><\/p>\n\n\n\n \/\/insert the number at free position<\/p>\n\n\n\n array [freePosition] = insert_val<\/p>\n\n\n\n end for<\/strong><\/p>\n\n\n\n end procedure<\/p>\n\n\n\n Given above is the pseudo code for Insertion sort, next, we will illustrate this technique in the following example.<\/p>\n\n\n\n Illustration<\/p>\n\n\n\n The array to be sorted is as follows:<\/p>\n\n\n\n Now for each pass, we compare the current element to all its previous elements. So in the first pass, we start with the second element.<\/p>\n\n\n\n Thus we require N number of passes to completely sort an array containing N number of elements.<\/p>\n\n\n\n The above illustration can be summarized in a tabular form:<\/strong><\/p>\n\n\n\n As shown in the above illustration, we begin with the 2nd element as we assume that the first element is always sorted. So we begin with comparing the second element with the first one and swap the position if the second element is less than the first.<\/p>\n\n\n\n This comparison and swapping process positions two elements in their proper places. Next, we compare the third element to its previous (first and second) elements and perform the same procedure to place the third element in the proper place.<\/p>\n\n\n\n In this manner, for each pass, we place one element in its place. For the first pass, we place the second element in its place. Thus in general, to place N elements in their proper place, we need N-1 passes.<\/p>\n\n\n\n <\/p>\n\n\n\n Shell sort is often termed as an improvement over insertion sort. In insertion sort, we take increments by 1 to compare elements and put them in their proper position.<\/p>\n\n\n\n In shell sort, the list is sorted by breaking it down into a number of smaller sublists. It\u2019s not necessary that the lists need to be with contiguous elements. Instead, shell sort technique uses increment i, which is also called \u201cgap\u201d and uses it to create a list of elements that are \u201ci\u201d elements apart.<\/p>\n\n\n\n The general algorithm for shell sort is given below.<\/strong><\/p>\n\n\n\n shell_sort (A, N)<\/p>\n\n\n\n where A \u2013 list to be sorted; N \u2013 gap_size<\/p>\n\n\n\n set gap_size = N, flag = 1<\/p>\n\n\n\n while gap_size > 1 or flag = 1, repeat<\/p>\n\n\n\n begin<\/p>\n\n\n\n set flag = 0<\/p>\n\n\n\n set gap_size = (gap_size + 1)\/2<\/p>\n\n\n\n end<\/p>\n\n\n\n for i = 0 to i< (N-gap_size) repeat<\/p>\n\n\n\n begin<\/p>\n\n\n\n if A[i + gap_size] > A[i]<\/p>\n\n\n\n swap A[i + gap_size], A[i]<\/p>\n\n\n\n set flag = 0<\/p>\n\n\n\n end<\/p>\n\n\n\n end<\/p>\n\n\n\n Thus in the above algorithm, we first set N which is the gap for sorting the array A using shell sort. In the next step, we divide the array into sub-arrays by using the gap. Then in the next step, we sort each of the sub-arrays so that at the end of the loop we will get a sorted array.<\/p>\n\n\n\n Next, let us consider a detailed example to better understand the shell sort using a pictorial representation.<\/p>\n\n\n\n Illustration<\/p>\n\n\n\n Let us illustrate the Shell sort with an Example.<\/strong><\/p>\n\n\n\n Consider the following array of 10 elements.<\/p>\n\n\n\n If we provide a gap of 3, then we will have the following sub-lists with each element that is 3 elements apart. We then sort these three sublists.<\/p>\n\n\n\n The sorted sub-lists and the resultant list that we obtain after combining the three sorted sublists are shown below.<\/p>\n\n\n\n The above array that we have obtained after merging the sorted subarrays is nearly sorted. Now we can perform insertion sort on this list and sort the entire array. This final step is shown below for your reference.<\/p>\n\n\n\n As seen above, after performing shell sort and merging the sorted sublists, we only required three moves to completely sort the list. Thus we can see that we can significantly reduce the number of steps required to sort the array.<\/p>\n\n\n\n <\/p>\n\n\n\n Shell sort is often termed as an improvement over insertion sort. In insertion sort, we take increments by 1 to compare elements and put them in their proper position.<\/p>\n\n\n\n In shell sort, the list is sorted by breaking it down into a number of smaller sublists. It\u2019s not necessary that the lists need to be with contiguous elements. Instead, shell sort technique uses increment i, which is also called \u201cgap\u201d and uses it to create a list of elements that are \u201ci\u201d elements apart.<\/p>\n\n\n\n The general algorithm for shell sort is given below.<\/strong><\/p>\n\n\n\n shell_sort (A, N)<\/p>\n\n\n\n where A \u2013 list to be sorted; N \u2013 gap_size<\/p>\n\n\n\n set gap_size = N, flag = 1<\/p>\n\n\n\n while gap_size > 1 or flag = 1, repeat<\/p>\n\n\n\n begin<\/p>\n\n\n\n set flag = 0<\/p>\n\n\n\n set gap_size = (gap_size + 1)\/2<\/p>\n\n\n\n end<\/p>\n\n\n\n for i = 0 to i< (N-gap_size) repeat<\/p>\n\n\n\n begin<\/p>\n\n\n\n if A[i + gap_size] > A[i]<\/p>\n\n\n\n swap A[i + gap_size], A[i]<\/p>\n\n\n\n set flag = 0<\/p>\n\n\n\n end<\/p>\n\n\n\n End<\/p>\n\n\n\n Thus in the above algorithm, we first set N which is the gap for sorting the array A using shell sort. In the next step, we divide the array into sub-arrays by using the gap. Then in the next step, we sort each of the sub-arrays so that at the end of the loop we will get a sorted array.<\/p>\n\n\n\n Next, let us consider a detailed example to better understand the shell sort using a pictorial representation.<\/p>\n\n\n\n Illustration<\/p>\n\n\n\n Let us illustrate the Shell sort with an Example.<\/strong><\/p>\n\n\n\n Consider the following array of 10 elements.<\/p>\n\n\n\n If we provide a gap of 3, then we will have the following sub-lists with each element that is 3 elements apart. We then sort these three sublists.<\/p>\n\n\n\n The sorted sub-lists and the resultant list that we obtain after combining the three sorted sublists are shown below.<\/p>\n\n\n\n The above array that we have obtained after merging the sorted subarrays is nearly sorted. Now we can perform insertion sort on this list and sort the entire array. This final step is shown below for your reference.<\/p>\n\n\n\n As seen above, after performing shell sort and merging the sorted sublists, we only required three moves to completely sort the list. Thus we can see that we can significantly reduce the number of steps required to sort the array.<\/p>\n\n\n\n The choice of increment to create sub-lists is a unique feature of shell sort.<\/p>\n","protected":false},"excerpt":{"rendered":" Bubble Sort Bubble Sort is the simplest of the sorting techniques. In the bubble sort technique, each of the elements in the list is compared to its adjacent element. Thus if there are n elements in list A, then A[0] is compared to A[1], A[1] is compared to A[2] and so on. After comparing if […]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":[],"_links":{"self":[{"href":"https:\/\/xcodeph.net\/index.php\/wp-json\/wp\/v2\/pages\/564"}],"collection":[{"href":"https:\/\/xcodeph.net\/index.php\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/xcodeph.net\/index.php\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/xcodeph.net\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/xcodeph.net\/index.php\/wp-json\/wp\/v2\/comments?post=564"}],"version-history":[{"count":4,"href":"https:\/\/xcodeph.net\/index.php\/wp-json\/wp\/v2\/pages\/564\/revisions"}],"predecessor-version":[{"id":589,"href":"https:\/\/xcodeph.net\/index.php\/wp-json\/wp\/v2\/pages\/564\/revisions\/589"}],"wp:attachment":[{"href":"https:\/\/xcodeph.net\/index.php\/wp-json\/wp\/v2\/media?parent=564"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
array \u2013 list of items to be sorted
N \u2013 size of array
begin
swapped = false
repeat
for I = 1 to N-1
if array[i-1] > array[i] then
swap array[i-1] and array[i]
swapped = true
end if
end for
until not swapped
end procedure<\/p>\n\n\n\n![\"\"](\"https:\/\/xcodeph.net\/wp-content\/uploads\/2021\/07\/image-3.png\")
<\/figure>\n\n\n\n![\"\"](\"https:\/\/xcodeph.net\/wp-content\/uploads\/2021\/07\/image.png\")
<\/figure>\n\n\n\n![\"\"](\"https:\/\/xcodeph.net\/wp-content\/uploads\/2021\/07\/image-2.png\")
<\/figure>\n\n\n\n![\"\"](\"https:\/\/xcodeph.net\/wp-content\/uploads\/2021\/07\/image-1.png\")
<\/figure>\n\n\n\nSELECTION SORT<\/h2>\n\n\n\n
if smallestElem > A [J]
set smallestElem = A [J]
set POS = J
[if end]
[End of loop]<\/li>![\"Selection](\"https:\/\/xcodeph.net\/wp-content\/uploads\/2021\/07\/image-7.png\")
<\/figure>\n\n\n\n![\"Pass2\"](\"https:\/\/xcodeph.net\/wp-content\/uploads\/2021\/07\/image-6.png\")
<\/figure>\n\n\n\n![\"Pass3\"](\"https:\/\/xcodeph.net\/wp-content\/uploads\/2021\/07\/image-4.png\")
<\/figure>\n\n\n\n![\"Pass4\"](\"https:\/\/xcodeph.net\/wp-content\/uploads\/2021\/07\/image-5.png\")
<\/figure>\n\n\n\n<\/figure>\n\n\n\n Insertion Sort<\/strong><\/h2>\n\n\n\n
![\"array](\"https:\/\/xcodeph.net\/wp-content\/uploads\/2021\/07\/image-8.png\")
<\/figure>\n\n\n\n![\"Insertion](\"https:\/\/xcodeph.net\/wp-content\/uploads\/2021\/07\/image-10.png\")
<\/figure>\n\n\n\n![\"\"](\"https:\/\/xcodeph.net\/wp-content\/uploads\/2021\/07\/image-9.png\")
<\/figure>\n\n\n\nShell Sort<\/h2>\n\n\n\n
![\"array](\"https:\/\/xcodeph.net\/wp-content\/uploads\/2021\/07\/image-14.png\")
<\/figure>\n\n\n\n![\"sub-lists\"](\"https:\/\/xcodeph.net\/wp-content\/uploads\/2021\/07\/image-12.png\")
<\/figure>\n\n\n\n![\"sorted](\"https:\/\/xcodeph.net\/wp-content\/uploads\/2021\/07\/image-11.png\")
<\/figure>\n\n\n\n![\"The](\"https:\/\/xcodeph.net\/wp-content\/uploads\/2021\/07\/image-13.png\")
<\/figure>\n\n\n\nSHELL SORT<\/h2>\n\n\n\n
![\"array](\"https:\/\/xcodeph.net\/wp-content\/uploads\/2021\/07\/image-15.png\")
<\/figure>\n\n\n\n![\"sub-lists\"](\"https:\/\/xcodeph.net\/wp-content\/uploads\/2021\/07\/image-18.png\")
<\/figure>\n\n\n\n![\"sorted](\"https:\/\/xcodeph.net\/wp-content\/uploads\/2021\/07\/image-17.png\")
<\/figure>\n\n\n\n![\"The](\"https:\/\/xcodeph.net\/wp-content\/uploads\/2021\/07\/image-16.png\")
<\/figure>\n\n\n\n