1. Bubble sort is a comparison based algorithm that compares each pair of elements in an array and ...
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 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 2 5 4 8 ) --> ( 1 4 2 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
4. The following code is for:
5. Which of the following statements are true about insertion sort?
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.
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
Merge Sort
Quicksort
Bubble Partition Sort
8. The following is describing an insertion sort.
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)
Bubble Sort
This isn't a sort
Insertion Sort
Quick Sort