# 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