VJC Chapter 12 Sorting Algorithms

VJC/H2Computing/9569 Chapter 12 Sorting Algorithms Contents 1 Bubble sort 1.1 Non-optimised bubble sort 1.2 Optimised bubble sort 1.3 Time complexity of bubble sort 2 Insertion sort 2.1 Time complexity of insertion sort 3 Merge sort 3.1 Time complexity of merge sort 4 Quicksort 4.1 Out-of-place quicksort 4.2 In-place quicksort 4.3 Time complexity of quicksort 5 Merge sort vs Quick sort Syllabus Learning Outcomes 1.2 Fundamental Algorithms Understand algorithms for sorting and searching methods such as insertion sort, bubble sort, quicksort, merge sort, linear search, binary search and hash table search, and use examples to explain these methods. 1.2.1 Implement sort algorithms. – Insertion sort – Bubble sort – Quicksort – Merge sort 1.2.2 Use examples to explain sort algorithms. 1.2.5 Compare and describe the efficiencies of the sort and search algorithms using Big-O notation for time complexity (worst case). Exclude: space complexity 2.3 Implementing Algorithms and Data Structures Use programming language elements and constructs to implement sort and search algorithms such as insertion sort, bubble sort, quicksort, merge sort, linear search, binary search, and hash table search, as well as data structures such as stacks, queues, linear linked lists, and binary search trees. 2.3.1 Implement sort programs. – Insertion sort – Bubble sort – Quicksort – Merge sort 1

VJC/H2Computing/9569 Sorting algorithms are used to put data in order. This data may be numbers, strings, records or objects. The four sorting algorithms you are expected to know are bubble sort, insertion sort, merge sort and quicksort. Sorting algorithms could be compared based on ● Time taken to complete the work ● Memory requirement to complete the work ● Stability in keeping the input orders of items having the same sorting order 1. Bubble sort Bubble sort is one of the easiest sorting algorithms to understand and implement; however, it is very inefficient compared to other alternatives. 1.1 Non-optimised bubble sort Let’s look at how a simple bubble sort is implemented. It works as follows: Compare the first and second values. If the first value is larger than the second value, swap them. Compare the second and third values. If the second value is larger than the third value, swap them. Keep on comparing adjacent values, swapping them if necessary, until the last two values in the list have been processed. When we have completed the first pass through the entire array, the largest value is in the correct position at the end of the array. The other values may or may not be in the correct order. We need to work through the array again and again with each pass having one less value to compare. Illustration of bubble sort in one pass: Swapping values working down the array in one pass 2

VJC/H2Computing/9569 States of the array after each pass The algorithm of non-optimised bubble sort in pseudocode is: FOR passes 0 TO length of data - 2 FOR j 0 TO length of data – 2 – passes IF data[j] > data[j + 1] THEN data[j], data[j + 1] data[j + 1], data[j] ENDIF ENDFOR ENDFOR The values to be sorted may already be in the correct order before the outer loop has been through all its iterations. Look at the list of values below. States of the array after each pass After the third pass, the values are all in the correct order but the algorithm will continue to run. This means that we are making comparisons when no further swaps need to be made. 3

VJC/H2Computing/9569 1.2 Optimised bubble sort If we have gone through one pass without swapping any values, this means that the values must be in the correct order. So, we can improve the algorithm by using a variable swapped to store whether a swap has taken place during the current pass. When we swap a pair of values, we set swapped to True . This indicates that the list was not sorted. If swapped is False at the end of one pass through the list, this indicates that none of the values are swapped. If none of the values are swapped, the list must be sorted, and we can exit the sort algorithm. This allows us to cut down on any unnecessary comparisons and passes which improves the bubble sort algorithm to make it optimised. The algorithm of optimised bubble sort in pseudocode is: swapped TRUE passes length of data – 1 WHILE swapped DO swapped FALSE FOR j 0 TO passes - 1 IF data[j] > data[j + 1] THEN data[j], data[j + 1] data[j + 1], data[j] swapped TRUE ENDIF ENDFOR passes passes – 1 ENDWHILE 1.3 Time complexity of bubble sort First, we assume that we will be sorting the array (of size n) using bubble sort in an ascending order. At the first iteration of the bubble sort, we are iterating through n-1 elements, until the largest element 'bubbles' to the end of the array. At the second iteration, we are iterating through n – 2 elements. After the second iteration, the second largest element bubbles up to the second last position of the array. This process continues until the whole array is sorted (or no more swaps occur, in the optimised case). 4

VJC/H2Computing/9569 No. of comparisons = (n-1) + (n-2) + (n-3) + … + 3 + 2 + 1 = Best case time complexity: Ω( n) Given a sorted list, we only need one pass with n-1 comparisons on the values in the list to check that it is sorted. This example will give a time complexity of Ω( n). Worst case time complexity: O(n 2 ) The non-optimised bubble sort algorithm will give the worst case time complexity of O(n 2 ) as it needs to make (n-1)*(n-2) comparisons to complete the sort. 2. Insertion Sort Insertion sort works by dividing an array into two parts: sorted and unsorted. Elements are inserted one by one into their correct position in the sorted section. To sort an array in ascending order using insertion sort, we start with the first element in the array. One element by itself is already sorted. Then we consider the next element in the unsorted array. If it is smaller than the first element, we insert this element to the left of the first element, else we place it to the right. Next, we consider the third element in the array. We make comparisons with the elements in the sorted array leftwards until we find the correct position to insert this element into the sorted array. We then repeat this for the remaining elements, until the whole array is