# 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