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