Preview

07 -Sorting Algorithms

 1. Bubble sort is a comparison based algorithm that compares each pair of elements in an array and ...

  compares each element to the last element and swaps the first with the last

  compares each element to the first element and swaps it with the second until the array is sorted

  swaps them if they are out of order until the entire array is sorted.

  removes them if they are out of order so that the array is sorted quicker

 2. An array of numbers "5 1 4 2 8", needs to be sorted from lowest to greatest using bubble sort. The steps in the first and second pass are shown. In the second pass, what would the next step look like?
Example:
First Pass:
( 5 1 4 2 8 ) --> ( 1 5 4 2 8 ), compares first two elements, swaps since 5 > 1.
( 1 5 4 2 8 ) -->  ( 1 4 5 2 8 ), Swap since 5 > 4
( 1 4 5 2 8 ) -->  ( 1 4 2 5 8 ), Swap since 5 > 2
( 1 4 2 5 8 ) --> ( 1 4 2 5 8 ), (8 > 5), algorithm does not swap them.

Second Pass:
( 1 4 2 5 8 ) --> ( 1 4 2 5 8 )

  ( 1 2 5 4 8 ) --> ( 1 4 2 5 8 ), Swap since 2 < 4

  ( 1 4 5 2 8 ) --“> ( 1 4 2 5 8 ), Swap since 5 < 2

  ( 1 2 4 5 8 ) --> ( 1 2 4 5 8 ), Swap since 2 > 4

  ( 1 4 2 5 8 ) --> ( 1 2 4 5 8 ), Swap since 4 > 2

 3. The insertion sorts iterates through an input array and removes one element per iteration, finds the place the element belongs in the array, and then places it there. It is generally considered _____ efficient on large lists than more advanced algorithms

  more

  equally

  less

  favourably

 4. The following code is for:
procedure MysterySort( A : list of sortable items )
    n = length(A)
    repeat
        newn = 0
        for i = 1 to n-1 inclusive do
            if A[i-1] > A[i] then
                swap(A[i-1], A[i])
                newn = i
            end if
        end for
        n = newn
    until n <= 1
end procedure

  a merge sort

  a bubble sort

  a linear sort

  an insertion sort

 5. Which of the following statements are true about insertion sort?

  considered efficient for (quite) small data sets

  Relatively simple coding implementation

  all of these are true and are also advantages of insertion sort.

  in place: i.e only requires a constant amount O(1) of additional memory space

 6. This algorithm is also called the "divide and conquer" algorithm and its main focus is on how to combine together two pre-sorted arrays such that the resulting array is also sorted.

  Linear Sort

  Merge Sort

  Combined Sort

  Binary Sort

 7. Analyse the following code. What type of sort is it for?
def functionSort(data_list):
   quickSortHlp(data_list,0,len(data_list)-1)

def functionSortHlp(data_list,first,last):
   if first < last:

       splitpoint = partition(data_list,first,last)

       functionSortHlp(data_list,first,splitpoint-1)
       functionSortHlp(data_list,splitpoint+1,last)


def partition(data_list,first,last):
   pivotvalue = data_list[first]

   leftmark = first+1
   rightmark = last

   done = False
   while not done:

       while leftmark <= rightmark and data_list[leftmark] <= pivotvalue:
           leftmark = leftmark + 1

       while data_list[rightmark] >= pivotvalue and rightmark >= leftmark:
           rightmark = rightmark -1

       if rightmark < leftmark:
           done = True
       else:
           temp = data_list[leftmark]
           data_list[leftmark] = data_list[rightmark]
           data_list[rightmark] = temp

   temp = data_list[first]
   data_list[first] = data_list[rightmark]
   data_list[rightmark] = temp


   return rightmark

data_list = [54,26,93,17,77,31,44,55,20]
functionSort(data_list)
print(data_list)

  Insertion Sort

  Bubble Partition Sort

  Quicksort

  Merge Sort

 8. The following is describing an insertion sort.
 The basic idea is to keep splitting a 
 list into two smaller lists, sort those lists
 using the same rules, then split the sub-lists
 and sort again, until there are only lists of 
 1 item or less left.
 
 This sort is complex to code

  False

  True

 9. What sorting technique is being demonstrated in the code below?
def mySort(nlist):
    for passnum in range(len(nlist)-1,0,-1):
        for i in range(passnum):
            if nlist[i]>nlist[i+1]:
                temp = nlist[i]
                nlist[i] = nlist[i+1]
                nlist[i+1] = temp

nlist = [14,46,43,27,57,41,45,21,70]
nlist2 = [3,2]
mySort(nlist2)
print(nlist2)

  This isn't a sort

  Insertion Sort

  Quick Sort

  Bubble Sort