# 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

bubble

moon

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

Trump

Merge

Insertion

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

merge sort

bubble sort

binary search sort

insertion 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.```

bubble sort

Merge Sort

insertion sort

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

2,13,6,10,12,4

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

None of the above

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

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

bubble sort

merge 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.```

merge / divide / sorted

insert / merge / sorted

divide / merge / sorted

divide / sort / lists

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

True

False

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

False

True

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

Merge Sort

Bubble Sort

Mouse Sort

Insertion Sort