Question

1. Sorting algorithm for arrays: understand how to perform the following algorithms. (a). Simple sorting

   1. Bubblesort:T(n)ÎO(n2)

   2. Selection sort : T(n) Î O(n2)

   3. Insertion sort: T(n) Î O(n2)

   (b).Advanced sorting

i. Shell sort: O(n2) < O(n1.25) < O(nlogn), O(n1.25) is empirical result for shell sort.

2. Merge sort: T(n) Î O(nlogn), need one temporary array with the same length as the array needed to be sorted.

3. Quick sort: -average case: T(n) Î O(nlogn),
   -worst case(rare occurrence): T(n) Î O(n2)

5. Searching algorithm for arrays: understand how to perform the following algorithms. (a). Searching in unsorted arrays

i. Sequentialsearch
ii. Sequential search with sentinel

(b).Searching in sorted arrays

1. Binary search

2. Interpolation search

Answer 1

Bubble Sort:
Bubble Sort is based on repeatedly swapping the adjacent elements if they are in wrong order.
Lets under stand by simple example Array = [9,4,5,3]
In step 1, 9 is compared with 4. Since 9>4, 9 is moved ahead of 4. Similarly all the other elements are of a lesser value than 9, 9 is moved to the end of the array.
Now the Array ={4,5,3,9}.
In step 2, 4 is compared with 5. Since 5>4 and both 4 and 5 are in ascending order, these elements are not swapped. However, when 5 is compared with 3, 5>3 and these elements are in descending order. Therefore, 5 and 3 are swapped.
Now the Array ={4,3,5,9}.
In step 3, the element 4 is compared with 3. Since 4>3 and the elements are in descending order, 4 and 3 are swapped.
The sorted array is A[]={3,4,5,7}.

Selection Sort:
The selection sort algorithm sorts an array by repeatedly finding the minimum or maximum element from unsorted part and putting it at the beginning or ending.
Lets under stand by simple example Array = [64,25,12,22,11]
step 1, Find the minimum element in array[0...4] and place it at beginning
11 25 12 22 64
step 2, Find the minimum element in arr[1...4] and place it at beginning of arr[1...4]
11 12 25 22 64
step 3, Find the minimum element in arr[2...4] and place it at beginning of arr[2...4]
11 12 22 25 64
step 4, Find the minimum element in arr[3...4] and place it at beginning of arr[3...4]
11 12 22 25 64

Insertion sort :
Insertion sort is based on the idea that one element from the input elements is consumed in each iteration to find its correct position i.e, the position to which it belongs in a sorted array.
Array = [12, 11, 13, 5, 6]
Let us loop for i = 1 (second element of the array) to 4 (last element of the array)
Step 1: i = 1. Since 11 is smaller than 12, move 12 and insert 11 before 12
[11, 12, 13, 5, 6]
Step 2: i = 2. 13 will remain at its position as all elements in A[0..I-1] are smaller than 13
[11, 12, 13, 5, 6]
Step 3: i = 3. 5 will move to the beginning and all other elements from 11 to 13 will move one position ahead of their current position.
[5, 11, 12, 13, 6]
Step 4: i = 4. 6 will move to position after 5, and elements from 11 to 13 will move one position ahead of their current position.
[5, 6, 11, 12, 13]

Shell Sort :
Shell Sort is mainly a variation of Insertion Sort. In insertion sort, we move elements only one position ahead. When an element has to be moved far ahead, many movements are involved. The idea of shell Sort is to allow exchange of far items. In shell Sort, we make the array h-sorted for a large value of h. We keep reducing the value of h until it becomes 1. An array is said to be h-sorted if all sub lists of every h'th element is sorted.

Merge sort :
Merge sort is a divide-and-conquer algorithm based on the idea of breaking down a list into several sub-lists until each sub list consists of a single element and merging those sub lists in a manner that results into a sorted list.
Step 1:Divide the unsorted list into N sub lists, each containing 1 element.
Step 2:Take adjacent pairs of two singleton lists and merge them to form a list of 2 elements. N will now convert into N/2 lists of size 2.
Step 3:Repeat the process till a single sorted list of obtained.
While comparing two sub lists for merging, the first element of both lists is taken into consideration. While sorting in ascending order, the element that is of a lesser value becomes a new element of the sorted list. This procedure is repeated until both the smaller sub lists are empty and the new combined sub list comprises all the elements of both the sub lists.

Quick Sort :
Like Merge Sort, Quick Sort is a Divide and Conquer algorithm. It picks an element as pivot and partitions the given array around the picked pivot. There are many different versions of quick Sort that pick pivot in different ways.
Step 1:Always pick first element as pivot.
Step 2:Always pick last element as pivot (implemented below)
Step 3:Pick a random element as pivot.
Step 4:Pick median as pivot.
The key process in quick Sort is partition(). Target of partitions is, given an array and an element x of array as pivot, put x at its correct position in sorted array and put all smaller elements (smaller than x) before x, and put all greater elements (greater than x) after x. All this should be done in linear time.

Sequential Search:
In this, the list or array is traversed sequentially and every element is checked. For example: Linear Search.
Linear search is used on a collections of items. It relies on the technique of traversing a list from start to end by exploring properties of all the elements that are found on the way.
For example, consider an array of integers of size N. You should find and print the position of all the elements with value x. Here, the linear search is based on the idea of matching each element from the beginning of the list to the end of the list with the integer x, and then printing the position of the element if the condition is `True'.

Binary Search:
Search a sorted array by repeatedly dividing the search interval in half. Begin with an interval covering the whole array. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise narrow it to the upper half. Repeatedly check until the value is found or the interval is empty. We basically ignore half of the elements just after one comparison.
Step 1: Compare x with the middle element.
Step 2:If x matches with middle element, we return the mid index.
Step 3:Else If x is greater than the mid element, then x can only lie in right half sub array after the mid element. So we recur for right half.
Step 4:Else (x is smaller) recur for the left half.

Interpolation Search :
The Interpolation Search is an improvement over Binary Search for instances, where the values in a sorted array are uniformly distributed. Binary Search always goes to the middle element to check. On the other hand, interpolation search may go to different locations according to the value of the key being searched. For example, if the value of the key is closer to the last element, interpolation search is likely to start search toward the end side.
Step 1: In a loop, calculate the value of “pos” using the probe position formula.
Step 2: If it is a match, return the index of the item, and exit.
Step 3: If the item is less than arr[pos], calculate the probe position of the left sub-array. Otherwise calculate the same in the right sub-array.
Step 4: Repeat until a match is found or the sub-array reduces to zero.