5.1 Classic Algorithms -Sorting

Question 1

Why Bother With Sorting?

Answer 1

❑Sorting applications are one of the most common algorithms
❑They are implemented in computer games, network routing software, operating systems, AI algorithms, bin packing algorithms, etc….
❑The sorting problem itself is easily understood
❑It doesn’t need a large amount of background knowledge before we can start implementing it
❑The algorithms are quite small and manageable
❑They can be implemented in a short period of time
❑They are relatively simple to analyse

Question 2

Formal Definition of Sorting

Answer 2

❑The sorting problem is a mapping from xto y, where
❑xand yare both nlength vectors (lists and/or arrays)
❑y is a permutation of x(different ordering)
❑yi< yi+1for all i=0,…,n-1
❑The problem of reordering items of an array in a certain order
❑The algorithms can easily be applied to integers or character vectors
❑Sorting whole numbers
❑Sorting names and/or addresses
❑Essentially anything that can be ordered/compared.

Question 3

Applications

Answer 3

❑When an array is sorted, many problems involving an array become easier, for example:
❑Searching for a specific value
❑To find the smallest and/or largest value (min/max)
❑To count how many times a specific value appear in array
❑To find out how unique are the values and delete duplicates
❑To do intersection and/or union between two different arrays

Question 4

Bubble Sort

Answer 4

❑It is one of the simplest sorting algorithm
❑Repeatedly compare adjacent pairs of elements
❑Swap the elements in pair putting the smaller element first
❑When it reaches end of list, starts over
❑It stops when no more swaps can be made

Question 5

Bubble Sort: Summary

Answer 5

❑If we compare pairs of adjacent elements and none are out of order, the list is sorted
❑If any are out of order, we must have to swap them to get an ordered list
❑Bubble sort will make passes though the list swapping any elements that are out of orde

Question 6

Best-Case Analysis

Answer 6

❑If the elements are in sorted order at the start, the for loop will compare the adjacent pairs but not make any changes
❑This means that the NoSwapsvariable will remain true
❑The While loop is only done once
❑Thus, comparisons are done but not the swaps…
❑There are n-1 comparisons in the best-case
❑B(n)O(n)

Question 7

Worst-Case Analysis

Answer 7

❑If in the best case the while loop is done once, in the worst case the while loop must be done as many times as possible
❑This will be when the data is in reverse order
❑Each pass of the Forloop must make at least one swap of the elements

Question 8

Quick Sort

Answer 8

❑Quicksort is a divide and conquer algorithm
❑Quicksort picks an element from the list as the pivot, and partitions the list into two pieces:
❑Those elements smaller than the pivot value (not necessarily in order)
❑Those elements larger than the pivot value (not necessarily in order)
❑Quicksort is then called recursively on both pieces

Question 9

Variations of Quick Sort

Answer 9

❑There are many different versions of Quick Sort, based on the different ways of picking the pivot:
❑Pivot always being the first element
❑Pivot always being the last element
❑Pivot is selected randomly
❑The median is chosen as the pivol

Question 10

Worst-case Analysis

Answer 10

❑In the worst case, PivotListwill do n-1comparisons, but creates one partition that has n-1elements and the other will have 1 element
❑When will this happen?
❑Because we wind up just reducing the partition by one element each time
❑Results in n levels of recursion, each with O(n) work due to the partitioning process
❑The worst case is given by

Question 11

Best-case Analysis

Answer 11

❑PivotListcreates two parts that are the same size
❑And then all subsequent parts are the same size as the algorithm calls itself, this can be modelled as a binary tree
❑Summing up over the partitions we get B(n)=B(nh)=O(nLog2(n))

Question 12

Radix Sort

Answer 12

❑Non-comparison sorting method!❑The Radix sort is efficient for sorting lists than can be broken down by positional significance
❑Radix sort works by using a binary bucket sort for each binary digit/bit
❑We first “sort” by the least significant bit
❑Split input into 2 sets (bucket) based on the bit –those that have a 0 or those that have a 1
❑The ordering of the data as they are put in each set (or bucket) must be maintained…
❑Then proceed to the next least significant bit and repeat until we run out of bits.