03-Simple-Sorting.pdf

Data Structures and Algorithm Simple Sorting   Sorting refers to ordering data in an increasing or decreasing fashion according Sorting to some linear relationship among the data items.  Sorting arranges data in a sequence...

Data Structures and Algorithm Simple Sorting   Sorting refers to ordering data in an increasing or decreasing fashion according Sorting to some linear relationship among the data items.  Sorting arranges data in a sequence which makes searching easier.  The importance of sorting lies in the fact that data searching can be optimized to a very high level, if data is stored in a sorted manner. Sorting is also used to represent data in more readable formats. Following are some of the examples of sorting in real- life scenarios − Sorting ❖ Telephone Directory − The telephone directory stores the telephone numbers of people sorted by their names, so that the names can be searched easily. ❖ Dictionary − The dictionary stores words in an alphabetical order so that searching of any word becomes easy.   Bubble Sort Simple Sorting  Selection Sort Techniques  Insertion Sort  Bubble Sort is a simple algorithm which is used to sort a given set of n elements provided in form of an array with n number of elements.  It is known as bubble sort, because with every complete iteration the largest element in the given array, bubbles up towards the last place or the highest index. Bubble Sort  Sorting takes place by stepping through all the elements one-by-one and comparing it with the adjacent element and swapping them if required.  If there is a total of n elements, then there is a need to repeat the process for n-1 times.  Bubble Sort  If the given array is to be sorted in ascending order, bubble sort will start by:  Comparing the first element of the array with the second element.  If the first element is greater than the second, then swap them  If vice versa, no move will be done  Compare now the 2nd element that was swapped to the 3rd element, and so on. Bubble Sort start bubbleSort(list) for all elements of list if list[i] > list[i+1] swap(list[i], list[i+1]) end if end for return list Bubble Sort  Sorting takes an unordered collection and makes it an ordered one. 0 1 2 3 4 5 77 42 35 12 101 5 0 1 2 3 4 5 5 12 35 42 77 101 "Bubbling Up" the Largest Element  Traverse a collection of elements  Move from the front to the end  “Bubble” the largest value to the end using pair-wise comparisons and swapping 0 1 2 3 4 5 77 42 35 12 101 5 "Bubbling Up" the Largest Element  Traverse a collection of elements  Move from the front to the end  “Bubble” the largest value to the end using pair-wise comparisons and swapping 0 1 2 3 4 5 7742 Swap 42 77 35 12 101 5 "Bubbling Up" the Largest Element  Traverse a collection of elements  Move from the front to the end  “Bubble” the largest value to the end using pair-wise comparisons and swapping 0 1 2 3 4 5 42 77 35 Swap 3577 12 101 5 "Bubbling Up" the Largest Element  Traverse a collection of elements  Move from the front to the end  “Bubble” the largest value to the end using pair-wise comparisons and swapping 0 1 2 3 4 5 42 35 77 12 Swap 1277 101 5 "Bubbling Up" the Largest Element  Traverse a collection of elements  Move from the front to the end  “Bubble” the largest value to the end using pair-wise comparisons and swapping 0 1 2 3 4 5 42 35 12 77 101 5 No need to swap "Bubbling Up" the Largest Element  Traverse a collection of elements  Move from the front to the end  “Bubble” the largest value to the end using pair-wise comparisons and swapping 0 1 2 3 4 5 42 35 12 77 101 5 Swap 101 5 "Bubbling Up" the Largest Element  Traverse a collection of elements  Move from the front to the end  “Bubble” the largest value to the end using pair-wise comparisons and swapping 0 1 2 3 4 5 42 35 12 77 5 101 Largest value correctly placed Items of Interest  Notice that only the largest value is correctly placed  All other values are still out of order  We need to repeat this process 0 1 2 3 4 5 42 35 12 77 5 101 Largest value correctly placed Repeat “Bubble Up” How Many Times?  If we have N elements…  And if each time we bubble an element, we place it in its correct location…  Then we repeat the “bubble up” process N – 1 times.  This guarantees we’ll correctly place all N elements.  “Bubbling” All the Elements 0 1 2 3 4 5 42 35 12 77 5 101 0 1 2 3 4 5 35 12 42 5 77 101 0 1 2 3 4 5 N-1 12 35 5 42 77 101 0 1 2 3 4 5 12 5 35 42 77 101 0 1 2 3 4 5 5 12 35 42 77 101 Optimized Bubble Sort In the given algorithm, all the comparisons are made even if the array is already sorted. This increases the execution time. We can use a boolean variable to determine if any swapping occurred during the “bubble up.” The value of Boolean variable is set true if there occurs swapping of elements. Otherwise, it is set false. After an iteration, if there is no swapping, the value of the Boolean variable will be false. This means elements are already sorted and there is no need to perform further iterations. This boolean “flag” needs to be reset after each “bubble up.” This will reduce the execution time and helps to optimize the bubble sort. Bubble Sort Algorithm : do swapped = false for i = 1 to indexOfLastUnsortedElement-1 if leftElement > rightElement swap(leftElement, rightElement) swapped = true while swapped “Bubbling” All the Elements 0 1 2 3 4 5 77 42 35 12 101 5 0 1 2 3 4 5 42 35 12 77 5 101 0 1 2 3 4 5 35 12 42 5 77 101 0 1 2 3 4 5 12 35 5 42 77 101 0 1 2 3 4 5 12 5 35 42 77 101 Practice  Simulate Bubble Sort on the following data and show the result of each iteration: { 18, 20, 15, 31, 40, 4, 27 } Practice { 18, 20, 15, 31, 40, 4, 27 }  Selection sort is done by selecting an element in the list and moving it to the proper position  find the minimum value in the list  swap it with the value in the first position Selection Sort  repeat the steps for the remainder of the list starting the next position after swapping to the first position Selection Sort 14 20 30 28 9 Selection Sort Algorithm: Step 1 − Set min to location 0 Step 2 − Search the minimum element in the list Step 3 − Swap with value at location min Step 4 − Increment min to point to next element Step 5 − Repeat until list is sorted Selection Sort Pseudocode: repeat (numOfElements - 1) times set the first unsorted element as the minimum for each of the unsorted elements if element < currentMinimum set element as new minimum swap minimum with first unsorted position Selection Sort Example: Selection Sort Example:  Selection Sort - Example 8 4 6 9 2 3 1 1 2 3 4 9 6 8 1 4 6 9 2 3 8 1 2 3 4 6 9 8 1 2 6 9 4 3 8 1 2 3 4 6 8 9 1 2 3 9 4 6 8 1 2 3 4 6 8 9 Practice  Simulate Selection Sort on the following data and show the result of each iteration: { 18, 20, 15, 31, 40, 4, 27 } Practice { 18, 20, 15, 31, 40, 4, 27 }  As the name suggests, insertion sort inserts each element of the array to its proper place.  It is a very simple sort method which is used to arrange the deck of cards while playing bridge.  Insertion sort is an efficient algorithm Insertion Sort for sorting a small number of elements.  The Insertion sort algorithm sorts the input numbers “in place”, that is, it rearranges the numbers within the array, with at most a constant number of them stored outside the array at any time. Insertion Sort Idea: like sorting a hand of playing cards  Startwith an empty left hand and the cards facing down on the table.  Remove one card at a time from the table, and insert it into the correct position in the left hand  compare it with each of the cards already in the hand, from right to left  The cards held in the left hand are sorted  these cards were originally the top cards of the pile on the table 36  Insertion Sort To insert 12, we need to make room for it by moving first 36 and then 24. 37  Insertion Sort 38  Insertion Sort 39 Insertion Sort  To perform insertion sort:  Divide the list into two: sorted part and the unsorted part  Unsorted part: Transfer one-by-one to their correct location in the sorted area Insertion Sort 14 20 30 28 9 Sorted Un Sorted 14 20 30 28 9 Sorted Un Sorted 14 20 28 30 9 Sorted Un Sorted 9 14 20 28 30 Sorted  If it is the first element, it is already Step 1 sorted. Step 2 Pick next element Insertion Sort Step 3 Compare with all elements in the sorted sub-list Algorithm Step 4 Shift all the elements in the sorted sub- list that is greater than the value to be sorted Step 5 Insert the value Step 6 Repeat until list is sorted Insertion Sort Algorithm: mark first element as sorted for each unsorted element X 'extract' the element X for j = lastSortedIndex down to 0 if current element j > X move sorted element to the right by 1 break loop and insert X here Insertion Sort Example: Sort this array in ascending order: { 70, 36, 40, 95, 22, 55, 26 } Practice  SimulateInsertion Sort on the following data and show the result of each iteration: { 18, 20, 15, 31, 40, 4, 27 } Thank You… ☺