Sorting Inn Quick

Quick Sort  Quick sort is proposed by C.A.R Hoare in the year 1962.  The quick sort technique is based on the divide and conquer technique.   Quick sort works recursively by first selecting a random “Pivot Value” from the list. It partitions the list into elements that are less than the pivotal and greater than the pivotal. Quick sort Quicksort picks an element as pivot, and then it partitions the given array around the picked pivot element. In quick sort, a large array is divided into two arrays in which one holds values that are smaller than the specified value (Pivot), and another array holds the values that are greater than Quick Sort Divide: Partition the array A[P…..r] into two subarrays, A[P….q-1] and A[q+1……r] such that each element of A[p…q-1] is less than or equal to A[q], which in turn less than or equal to each element of A[q+1…r]. Conquer: Sort the two subarrays A[P….q1] and A[q+1……r] by recursive calls. Combine: Since the subarrays are sorted in place, no work is needed to combine them. The array A[p…r] is now sorted. Algorithm for Quick Sort Upper Index Lower index Algorithm for Quick Sort Quick Sort Quick Sort Worst case Analysis of Quick Sort The Worst Case partition behaviors of Quick sort occurs when the partitioning routine produces one region with n-1 element and another with only one element. Lets assume that this unbalanced partitioning arises at every step of the algorithm, since partitioning cost Θ(n). T(n)=T(n-1)+Θ(n) T(n-1)=T(n-2)+(n-1)+n T(n)=n(n+1) = Θ(n2) 2 Worst case Analysis of Quick Sort Worst case = Θ(n2) Best Case= T(n)=2T(n/2)+Θ(n) T(n)=Θ(nlogn) Bubble Sort Stage 1: Compare each element (except the last one) with its neighbor to the right    If they are out of order, swap them This puts the largest element at the very end The last element is now in the correct and final place Stage 2: Compare each element (except the last two) with its neighbor to the right    If they are out of order, swap them This puts the second largest element next to last The last two elements are now in their correct and final places Stage 3: Compare each element (except the last three) with its neighbor to the right  Continue as above until you have no unsorted elements on the left 10 Example of Bubble Sort Stage 1 Stage 2 Stage 3 Stage 4 7 2 8 5 4 2 7 5 4 8 2 5 4 7 8 2 4 5 7 8 2 7 8 5 4 2 7 5 4 8 2 5 4 7 8 2 4 5 7 8 2 7 8 5 4 2 5 7 4 8 2 4 5 7 8 2 7 5 8 4 2 5 4 7 8 2 7 5 4 8 (done) 11 Code for Bubble Sort void bubbleSort(int[] a) { int stage, inner, temp; for (stage = a.length - 1; stage > 0; stage--) { // counting down for (inner = 0; inner < stage; inner++) { // bubbling up if (a[inner] > a[inner + 1]) { // if out of order... temp = a[inner]; // ...then swap a[inner] = a[inner + 1]; a[inner + 1] = temp; } } } } 12 Insertion Sort 13 Insertion Sort Suppose we know how to insert a new element x in its proper place in an already sorted array A of size k, to get a new sorted array of size k+1 Use this to sort the given array A of size n as follows: Insert A[1] in the sorted array A[0]. So now A[0],A[1] are sorted Insert A[2] in the sorted array A[0],A[1]. So now A[0],A[1],A[2] are sorted Insert A[3] in the sorted array A[0],A[1],A[2]. So now A[0],A[1],A[2],A[3] are sorted ….. Insert A[i] in the sorted array A[0],A[1],…,A[i-1]. So now A[0],A[1],…A[i] are sorted Continue until i = n-1 (outer loop)       14 How to do the first step Compare x with A[k-1] (the last element) If x ≥ A[k-1], we can make A[k] = x (as x is the max of all the elements) If x < A[k-1], put A[k] = A[k-1] to create a hole in the k-th position, put x there Now repeat by comparing x with A[k-2] (inserting x in its proper place in the sorted subarray A[0],A[1],…A[k-1] of k-2 elements) The value x bubbles to the left until it finds an element A[i] such that x ≥ A[i] No need to compare any more as all elements A[0], A[1], A[i] are less than x   15 Example of first step A 5 7 11 13 20 22 Insert x = 15 16 Example of first step A 5 7 11 13 20 22 Insert x = 15 Compare with 22. x < 22, so move 22 right 5 7 11 13 20 15 22 17 Example of first step A 5 7 11 13 20 22 Insert x = 15 Compare with 22. x < 22, so move 22 right 5 7 11 13 20 15 22 Compare with 20. x < 20, so move 20 right 5 7 11 13 15 20 22 18 Example of first step A 5 7 11 13 20 22 Insert x = 15 Compare with 22. x < 22, so move 22 right 5 7 11 13 20 15 22 Compare with 20. x < 20, so move 20 right 5 7 11 13 15 20 22 Compare with 13. x > 13, so stop A 5 7 11 13 15 20 22 19 Sort using the insertion A 7 5 13 11 22 20 Insert 5 in 7 5 7 13 11 22 20 Insert 13 in 5, 7 5 7 13 11 22 20 Insert 20 in 5, 7, 11, 13, 22 5 7 11 13 20 22 Insert 11 in 5, 7, 13 5 7 11 13 22 20 Insert 22 in 5, 7, 11, 13 5 7 11 13 22 20 20 Insertion Sort Code void InsertionSort (int A[ ], int size) { int i, j, item; for (i=1; i= 0; j--) if (item < A[j]) { /* push elements down*/ A[j+1] = A[j]; A[j] = item ; /* can do this on } else break; /*inserted, exit loop */ } } 21 void InsertionSort (int A[ ], int size) { int i,j, item; for (i=1; i=0; j--) 4 if (item > A[j]) 7 { A[j+1] = A[j]; A[j] = item6 ; } 2 else break; 1 } 5 int main() { i = 1:: 2, i = 2:: 9, int X[100], i, size; i = 3:: 9, scanf("%d",&size); i = 4:: 9, for (i=0;i