Lecture Data Structures & Algorithms: Chapter 4 (Sorting Techniques) presented bubble sort, selection sort, insertion sort, quick sort and other content. Invite you to read the lecture. | Data Structures & Algorithms 1 Sorting Techniques BUBBLE SORT INSERTION SORT SELECTION SORT QUICK SORT Why sort??? a) By keeping a data file sorted, we can do binary search on it. b) Doing certain operations, like matching data in two different files, become much faster. There are various methods for sorting: Bubble sort, Insertion sort, Selection sort, Quick sort, Heap sort, Merge sort . They having different average and worst case behaviors. BUBBLE SORT Introduction: Bubble sorting is a simple sorting technique in which we arrange the elements of the list by forming pairs of adjacent elements. That means we form the pair of the (i) th and (i+1)th element. If the order is ascending, we interchange the elements of the pair if the first element of the pair is greater than the second element. 10 5 17 4 8 15 5 10 17 4 8 15 5 10 17 4 8 15 5 10 4 17 8 15 Swap Swap Swap No Swap Bubble sort: end of First pass void bsort(int arr[], int n) { for(int i=0;i arr[j]) swap(&arr[i],&arr[j]); } BUBBLE SORT How to run by hand??? SELECTION SORT Selection sort is a simplicity sorting algorithm. It works as its name as it is. Here are basic steps of selection sort algorithm: 1. Find the minimum element in the list 2. Swap it with the element in the first position of the list 3. Repeat the steps above for all remainder elements of the list starting at the second position. SELECTION SORT SELECTION SORT SELECTION SORT void selection_sort(int arr[], int n) { for (int i = 0; i < n ; i++) { int min = i; for (int j = i+1; j < n; j++) { if (arr[j] < arr[min]) { min = j; } } swap(&arr[i], &arr[min]); } } How to run by hand??? INSERTION SORT Introduction: Basic Idea: Insert a record R into a sequence of ordered records: R1,R2,, Ri with keys K1 <= K2 <= . <= Ki , such that, the resulting sequence of size i+1 is also ordered with respect to key values. INSERTION SORT INSERTION SORT INSERTION SORT void InsertionSort(int M[],int n) { for(int . | Data Structures & Algorithms 1 Sorting Techniques BUBBLE SORT INSERTION SORT SELECTION SORT QUICK SORT Why sort??? a) By keeping a data file sorted, we can do binary search on it. b) Doing certain operations, like matching data in two different files, become much faster. There are various methods for sorting: Bubble sort, Insertion sort, Selection sort, Quick sort, Heap sort, Merge sort . They having different average and worst case behaviors. BUBBLE SORT Introduction: Bubble sorting is a simple sorting technique in which we arrange the elements of the list by forming pairs of adjacent elements. That means we form the pair of the (i) th and (i+1)th element. If the order is ascending, we interchange the elements of the pair if the first element of the pair is greater than the second element. 10 5 17 4 8 15 5 10 17 4 8 15 5 10 17 4 8 15 5 10 4 17 8 15 Swap Swap Swap No Swap Bubble sort: end of First pass void bsort(int arr[], int n) { for(int i=0;i
