Part 6 Sorting techniques.pdf

Data Structures and Algorithms Part 6 : Sorting Techniques 1 Data Structures and Algorithms Part 6 Simple sorting techniques - Outline  Simple Sorting techniques 1. Bubble sort. 2. Selection sort. 3. Insertion sort.  Stability.  Comparing simple sorting techniques 2...

Data Structures and Algorithms Part 6 : Sorting Techniques 1 Data Structures and Algorithms Part 6 Simple sorting techniques - Outline  Simple Sorting techniques 1. Bubble sort. 2. Selection sort. 3. Insertion sort.  Stability.  Comparing simple sorting techniques 2 Data Structures and Algorithms Part 6  Bubble Sort 3 Data Structures and Algorithms Part 6 Bubble Sort  Step 1: Iteration and Comparison  Bubble sort works by repeatedly stepping through the list, comparing adjacent elements.  Step 2: Swapping Elements  If the elements are out of order, they are swapped. This means the larger element "bubbles up" to its correct position, hence the name "Bubble Sort."  Step 3: Repetition and Sorting  This process is repeated for the entire length of the list. Each iteration places the largest unsorted element at the end of the list, effectively sorting it in descending order. 4 Data Structures and Algorithms Part 6 5 Data Structures and Algorithms Part 6 Example: 6 Data Structures and Algorithms Part 6 7 Data Structures and Algorithms Part 6 Bubble sort implementation void bubbleSort(int arr[]) { int temp; for(int index =arr.length-1; index >1; index --){ // outer loop (backward) for(int scan =0; scan < index; scan ++){ // inner loop (forward) if( arr[scan] > arr[scan +1] ) {// out of order? temp = arr[scan]; // swap them arr[scan] = arr[scan +1]; arr[scan +1] = temp; } // end if } // end inner loop } // end outer loop } // end bubbleSort() //-------------------------------------------------------------- 8 Data Structures and Algorithms Part 6 Efficiency of the Bubble Sort  If N is the number of items in the array, there are N-1 comparisons on the first pass, N-2 on the second, and so on. The formula for the sum of such a series is: (N–1) + (N–2) + (N–3) +... + 1 = N*(N–1)/2  Thus, the algorithm makes about N2⁄2 comparisons.  There are fewer swaps than there are comparisons because two bars are swapped only if they need to be. If the data is random, a swap is necessary about half the time, so there will be about N2⁄4 swaps.  Both swaps and comparisons are proportional to N2. Because constants don’t count in Big O notation, we can ignore the 2 and 4 and say that the bubble sort runs in O(N2) time. 9 Data Structures and Algorithms Part 6  Selection Sort 10 Data Structures and Algorithms Part 6 Selection Sort  Step 1: Finding the Minimum  Selection sort begins by finding the minimum element in the unsorted portion of the list. This minimum element is then swapped with the element at the beginning of the unsorted portion.  Step 2: Iterative Sorting  This process is repeated for the remaining unsorted portion, moving the minimum element to the next position. Each iteration effectively reduces the unsorted portion of the list by one element.  Step 3: Sorted Sub list  As the process iterates, a sorted sublist grows from the beginning of the list. Eventually, the entire list is sorted when all elements have been placed in their correct positions. 11 Data Structures and Algorithms Part 6 12 Data Structures and Algorithms Part 6 Selection Sort Copyright © 2017 Pearson Education, Inc. Selection sort implementation void selectionSort(int arr[]) { int min, temp; for(int index =0; index