XI-CS Check Point 14.1 Solution
1. Some commonly used sorting techniques or algorithms are selection sort, insertion sort, bubble sort, heap sort, merge sort, quick sort, etc.
2. In bubble sort, two adjoining values are compared repetitively and the heavier one gets down the list. In each pass the heaviest element gets settled to its position which is at the last position in the list.
So for the list: \([35, 6, 8, 11, 15, 9, 7, 22, 41, 65]\)
After the first pass the list becomes
\([6, 8, 11, 15, 9, 7, 22, 35, 41, 65]\)
and after the second pass
\([6, 8, 11, 9, 7, 15, 22, 35, 41, 65]\)
Detail Algorithm: At the first pass, the inner loop will run \(n-1\) times. i.e., \(10-1 = 9\) times. In each inner loop, there will be 9 comparison and 9 swaps in the worst case. At the second pass, the inner loop will run \(n-2\) times i.e. \(10-2=8\). So there will be 8 comparison and 8 swaps at most. The process will continue until \(n-9\). At Average case, the number of swaps can be simply counted by counting the number of elements on the right side that are smaller than it.
3. In Insertion sort, we divide the list into two groups: sorted and unsorted. After each pass, the sorted increased by one element and the unsorted become decrease by one element. In the first step we choose the second element and compare it to the first element and swap if second element is smaller than the first one. Now first and second element are sorted part, all other elements are unsorted. Now in each step we choose an element starting from the third element and compare it to its previous elements while it is smaller than them, and the put it at its correct position in the sorted list.
List to sort: \([42, 29, 74, 11, 65, 58]\)
42 is considered already sorted.
step-1: \([29, 42, 74, 11, 65, 58]\) – 1 swap (29 is sorted here)
step-2: \(29, 42, 74, 11, 65, 58\) – no swap (74 > 42, 74>29, so no swap, 74 is now sorted)
step-3: \(11, 29, 42, 74, 65, 58\) – 3 swap (11<74, 11<42, 11<29, 11 is now sorted)
step-4: \(11, 29, 42, 65, 74, 58\) – 1 swap happens (65<74, 65>42, 65>29,65>11, now 65 is sorted)
step-5: \(11, 29, 42, 58, 65, 74\) – 2 swap happens (58<74, 58<65, 58>42, 58>29, 58>11 now 58 is sorted)
Detail Algorithm: At first pass (Outer loop), there will be \(n-5\) comparison i.e. \(6-5 = 1\) times, 1 swap at most. At second pass, \(n-4\) comparison i.e., \(6-4 = 2\), 2 swap at most(but no swap happens in our solution because we do not encounter the worst case here). The process continue till \(n-1\).
