Preview

07 -Sorting Algorithms

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

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

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

  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

 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 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

  ( 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

 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

  less

  equally

  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 bubble sort

  a linear sort

  a merge sort

  an insertion sort

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

  Relatively simple coding implementation

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

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

  considered efficient for (quite) small data sets

 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.

  Combined Sort

  Linear Sort

  Merge 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)

  Merge Sort

  Quicksort

  Bubble Partition Sort

  Insertion 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)

  Quick Sort

  Bubble Sort

  Insertion Sort

  This isn't a sort