pdf2.pdf

SELECTION SORT QUICK SORT  SORTING Sorting algorithms put elements of a list into an order. Eg. : Numerical Sorting and Alphabetical Sorting Many sorting algorithms have been invented for sorting. They are either comparison based or non-comparison based....

SELECTION SORT QUICK SORT  SORTING Sorting algorithms put elements of a list into an order. Eg. : Numerical Sorting and Alphabetical Sorting Many sorting algorithms have been invented for sorting. They are either comparison based or non-comparison based. Their relative advantages and disadvantages have been studied extensively.  SORTING A comparison based sorting algorithm runs the elements through a single abstract comparison operation i.e. usually a "less than or equal to" operator That determines which of two elements should occur first in the final sorted list. Such examples include; Bubble Sort, Insertion Sort, Merge Sort, Heap Sort, Selection Sort, Quick Sort... Sort Non-comparison based sorting algorithms, on the other hand, are sorting algorithms which are not comparison based. Eg. : Counting Sort and Radix Sort SELECTION SORT  Introduction The selection sort algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at the beginning. The algorithm maintains two sub arrays in a given array. 1. The sub array which is already sorted. 2. Remaining sub array which is unsorted. In every iteration of selection sort, the minimum element from the unsorted sub-array is picked and moved to the sorted sub-array.  SELECTION SORT Example : arr[] = {2,7,4,1,5,3} Elements: 2 7 4 1 5 3 2 7 4 1 5 3 Index: 0 1 2 3 4 5 0 1 2 3 4 5 1 7 4 2 5 3 1 2 4 7 5 3 0 1 2 3 4 5 0 1 2 3 4 5 Sorted Array: Sorted Array:  SELECTION SORT Example : arr[] = {2,7,4,1,5,3}... 1 2 3 7 5 4 1 2 3 4 5 7 0 1 2 3 4 5 0 1 2 3 4 5 1 2 3 4 5 7 0 1 2 3 4 5 Sorted Array: Sorted Array:  SELECTION SORT class EthCode void printArray(int arr[]) { { void sort(int arr[]) int n = arr.length; { for (int i=0; i Starting index, high --> Ending index */ quickSort(arr[], low, high) { if (low < high) { pi = partition(arr, low, high); quickSort(arr, low, pi - 1); // Before pi quickSort(arr, pi + 1, high); // After pi } } QUICK SORT  QUICK SORT Time taken by Quick Sort in general can be written as following; T(n) = T(k) + T(n-k-1) + (n) So, Time Complexity T(n) : O(n*2) Auxiliary Space : O(1) Algorithmic Paradigm : Incremental Approach and Divide & Conquer Sorting In Place : Yes  QUICK SORT class EthCode{ void sort(int arr[], int low, int high){ int partition(int arr[], int low, int high) if (low < high) { { int pivot = arr[high]; int pi = partition(arr, low, high); int i = (low-1); sort(arr, low, pi-1); for (int j=low; j