Lecture Data Structures: Lesson 44 provide students with knowledge about sorting; sorting integers; elementary sorting algorithms: selection sort, insertion sort, bubble sort; selection sort; swap action (selectionsorting); selection sort analysis; lighter bubbles rise to the top; . | Sorting Lecture Data Structure Dr. Sohail Aslam Sorting Integers How to sort the integers in this array 20 8 5 10 7 5 7 8 10 20 Elementary Sorting Algorithms Selection Sort Insertion Sort Bubble Sort Selection Sort Main idea find the smallest element put it in the first position find the next smallest element put it in the second position And so on until you get to the end of the list Selection Sort Example a 19 5 7 12 00 11 22 33 a 5 19 7 12 0 1 2 3 a 5 7 19 12 0 1 2 3 a 5 7 12 19 0 1 2 3 a 5 7 12 19 0 1 2 3 Selection Sort Code void selectionSort int arr int N int posmin count tmp for count 0 countSelection Sort Code int findIndexMin int arr int start int N int posmin start int index for index start index lt N index if arr index Swap Action SelectionSorting 20 8 5 10 7 5 8 20 10 7 5 7 20 10 8 5 7 8 10 20 5 7 8 10 20 Selection Sort Analysis What is the time complexity of this algorithm Worst case Best case Average case Each iteration performs a linear search on the rest of the array first element N second element N 1 penultimate element 2 last element 1 Total N N 1 2 N2 N 2 Insertion Sort Basic idea sorting cards Starts by considering the first two elements of the array data if out of order swap them Consider the third element insert it into the proper position among the first three elements. Consider the forth element insert it into the proper position among the first four elements. Insertion Sort Example a 19 12 5 7 0 1 2 3 a 12 19 5 7 0 1 2 3 a 5 12 19 7 0 1 2 3 a 5 7 12 19 0 1 2 3 Insertion Sort Code void insertionSort int arr int N int pos count val for count 1 count lt N count val arr count for pos count-1 pos gt 0 pos- if arr pos gt val arr pos 1 arr pos else break arr pos 1 val Insertion Sort animation count val pos a 19 12 5 7 1 12 0 0 1 2 3 a 19 12 19 5 7 1 12 1 0 1 2 3 a 19 12 19 5 7 0 1 2 3 a 12 19 5 7 0 1 2 3 Insertion Sort animation cont count val pos a 12 19 5 7 2 5 1 0 1 2 3 a 12 19 19 5 7 2 5 0 0 1 2 3 a 12 19 12 19 7 2 5 1 0 1 2 3 a 12 5 12
