Sorting Algorithms: Bubble, Selection, Insertion, and Radix

Sorting

Bubble Sort In bubble sort, each element is compared with it’s adjacent element. If the first element is larger than the second one, then the positions of the elements are interchanged, otherwise it is not changed. Then next element is compared with it’s adjacent element and the same process is repeated for all the elements in the list.

Algorithm 1. Input n numbers to an array A2. Initialize i=0 and repeat through step 4 if(I < n)3. Initialize j=0 and repeat through step 4 if(j < n – I - 1)4. if(A[j]>A[j+1]) ◦ Temp=A[j] ◦ A[j]=A[j+1] ◦ A[j+1]=Temp 5. Display the sorted list6. Exit

Sort the given list using Bubble Sort:  41, 32, 22, 73, 43 Pass: I 41                     32 Swapped    32                        32                              32                         32                     41                      22 Swapped      22                              22 22                     22                     41                         41 No Swapping     41 73                     73                     73                         73                             43 43                     43                     43                         43                              73

Pass: II 32                     22 Swapped    22                               22                              22                      22                     32                      32 No Swapping      32                              32 41                     41                      41                               41 No Swapping     41 43                     43                      43                               43                              43 73                     73                      73                               73                              73

Pass: III 22                     22 No Swapping      22                                                                                 32                     32                               32 No Swapping       41                     41                                41 43                     43                                43  73                     73                                73  

Pass: IV 22                     22 No Swapping                                                                                         32                      32 41 41                                                                43                     43                                                               73                     73

Sorted array is 22 32 41 43 73

Sort 5,4,3,2,1 using Bubble Sort

Selection Sort The selection sort algorithm sorts an array by repeatedly finding theminimum element (considering ascending order) from unsorted partand putting it at the beginning

Algorithm 1. Input n numbers to an array A2. Initialize i=0 and repeat through step 4 if(I < n)3. Initialize j=i+1 and repeat through step 4 if(j < n – I)4. if(A[i]>A[j]) ◦ Temp=A[j] ◦ A[i]=A[j] ◦ A[j]=Temp 5. Display the sorted list6. Exit

Sort the given list using Bubble Sort: 41, 32, 22, 73, 43 Pass: I 41 A[0]                   22 32                            32 22 pos                     41 73                            73 43                            43

Pass: II 22 22 32 A[1]                    32 No Change 41 pos                     4173                            7343                            43

Pass: III 22 22 32                             32 41 A[2]                     41 No Change 73                            73 43                            43

Pass: IV 22 22 32                             32 41                             41 73 A[3]                    43 43 Pos                     73

Sorted List is:2232414273

Insertion Sort

Step 1: The second element of an array is compared with the elements that appearsbefore it (only first element in this case). If the second element is smaller than firstelement, second element is inserted in the position of first element. After first step,first two elements of an array will be sorted. Step 2: The third element of an array is compared with the elements that appears before it (first and second element). If third element is smaller than first element, it isinserted in the position of first element. If third element is larger than first elementbut, smaller than second element, it is inserted in the position of second element. Ifthird element is larger than both the elements, it is kept in the position as it is. Aftersecond step, first three elements of an array will be sorted. Step 3: Similarly, the fourth element of an array is compared with the elements thatappears before it (first, second and third element) and the same procedure is appliedand that element is inserted in the proper position. After third step, first fourelements of an array will be sorted.

Algorithm Let a be a linear array of n numbers, temp is a temporary variable for  swapping 1. Input n numbers of an array 2. Initialize i=0 and repeat through step 4 if(i<n) Set k=a[i] Initialize j=i-1 and repeat through if (j>=0 && k<a[j]) Set a[j+1]=a[j] A[j+1]=k 3. Display the sorted list 4. Exit 

Sort the given list using insertion sort  41, 32, 22, 73, 43

Radix Sort 10,21,17,34,44,11,654,123 0: 101: 21 112:3: 1234: 34 44 6545:6:7: 178:9:

So, the array becomes 10,21,11,123,24,44,654,17 0: 1: 10 11 172: 21 1233: 344: 445: 6546:7:8:9:

Now, the array becomes : 10,11,17,21,123,34,44,654 0: 010 011 017 021 034 0441: 1232:3:4:5:6: 6547:8:9:

The array becomes : 10,11,17,21,34,44,123,654 which is sorted