Preview

06 - Sorting Algorithms

 1. Read the description below. What sort is this describing?
__________ sort is a simple sorting algorithm that builds the final sorted array 
(or list) one item at a time. It is a comparison-based algorithm that builds a 
final sorted array one element at a time. It 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 much 
less efficient on large lists than more advanced algorithms

  Insertion

  moon

  bubble

  merge

 2. What type of sort is being described below?
_______sort is a comparison​-based algorithm that compares each pair of elements 
in an array and swaps them if they are out of order until the 
entire array is sorted.

  Merge

  Insertion

  Trump

  Bubble

 3. What is being described below?
__________ is another comparison-based algorithm also known as a "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. You may be interested to know 
that it was invented by the marvellous John von Neumann in 1945.

  bubble sort

  merge sort

  insertion sort

  binary search sort

 4. The below four steps describe the process (algorithm) involved in what type of sort?
1. First divide the list into the smallest unit (1 element), 
2. then compare each element with the adjacent list to 
3. sort and merge the two adjacent lists. 
4. Finally all the elements are sorted and merged.

  cumbersome sort

  Merge Sort

  bubble sort

  insertion sort

 5. Look at the diagram below that is showing the stages of a Bubble Sort. (This is based on an OCR GCSE past paper). What numbers will be shown in the next stage of the sort?
uploads/bsort.jpg

  2,13,6,10,12,4

  2,4,6,8,9,10,12,13

  2,6,13,8,9,10,12,4

  None of the above

 6. The following pseudocode is describing what type of sort?
Element 1 is a sorted list.
The rest of the elements are an ‘unsorted’ list.
Compare the first element in the unsorted list to each element in the sorted list.
IF it is smaller, put it in in front of that element (move the others along).
ELSEIF it is larger, compare with the next.
ELSEIF there are no more elements in the sorted list put it in the final position.
REPEAT UNTIL all element in the unsorted list are in the sorted list.

  Insertion Sort

  sort it out sort

  merge sort

  bubble sort

 7. Fill in the blanks to complete the sentences that describe a merge sort.
The key word of course is '________', so we are referring to bringing two 
lists together. Conceptually, a merge sort works as follows : 
First, ______ the unsorted list into n sublists, each containing 
1 element (a list of 1 element is considered sorted). Then, 
repeatedly merge sub lists to produce new _______ sublists until 
there is only 1 sublist remaining. 
This will be the sorted list.

  divide / merge / sorted

  divide / sort / lists

  merge / divide / sorted

  insert / merge / sorted

 8. When people manually sort cards in a bridge hand, most use a method that is similar to insertion sort

  False

  True

 9. The following is showing the stages/passes for an Insertion Sort
Example:
First Pass:
( 5 1 4 2 8 ) > ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, 
and 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 ), Now, since these elements are
already in order (8 > 5), algorithm does not swap them.

Second Pass:
( 1 4 2 5 8 ) > ( 1 4 2 5 8 )
( 1 4 2 5 8 ) > ( 1 2 4 5 8 ), Swap since 4 > 2
( 1 2 4 5 8 ) > ( 1 2 4 5 8 )
( 1 2 4 5 8 ) >  ( 1 2 4 5 8 )
Now, the array is already sorted, but our algorithm does not know 
if it is completed. The algorithm needs one whole pass without anyswap to know
it is sorted.

Third Pass:
( 1 2 4 5 8 ) > ( 1 2 4 5 8 )
( 1 2 4 5 8 ) > ( 1 2 4 5 8 )
( 1 2 4 5 8 ) > ( 1 2 4 5 8 )
( 1 2 4 5 8 ) > ( 1 2 4 5 8 )

  True

  False

 10. Which of the following is NOT a type of sorting algorithm?

  Mouse Sort

  Insertion Sort

  Bubble Sort

  Merge Sort