ALGORITHMS

Question 1

What is bubble sort?

Answer 1

A O(n2) sorting algorithm that iterates through a list, comparing each element
to its successor and swapping elements if the successor is greater than the current element.
This is repeated until no more swaps can be made.

Question 2

What is merge sort?

Answer 2

A O(n log(n)) divide-and-conquer sorting algorithm that recursively halves the
list into sublists until all sublists are of length 1. The sublists are then merged back together in such a way that they are always sorted, until the full single list is obtained.

Question 3

What is insertion sort?

Answer 3

A O(n2) sorting algorithm that divides a list into a sorted and unsorted
section. Elements from the unsorted section are compared with and placed in the right
position in the sorted section one by one until the sorted section spans the entire list.

Question 4

What is quick sort?

Answer 4

A O(n log(n)) sorting algorithm similar to Merge Sort, but relies on choosing a
pivot element whenever the list is split. Elements greater than the pivot go into one sub list,
while the rest go into the other. All sublists of length 1 will already be in a sorted order.

Question 5

Describe the process of bubble sort

Answer 5

1) Set swapMade variable to True.
2) While swapMade is True, make passes through the list:
- for all items list.LENGTH-2 (all but the last item):
- compare the first and the second item in the list:
- if the first item is greater than the second item, then they are not in order
– swap them and set swapMade variable to True; or
- if the first item is less than the second item, then they are in order; repeat the comparison process until the end of the list is reached;
- when the end of the list is reached, begin another pass.
3) On the final pass, all of the items should be sorted and therefore swapMade will remain False and the algorithm will finish.

Question 6

What is the pseudocode for bubble sort?

Answer 6

FUNCTION bubbleSort(list)
swapMade = True
WHILE swapMade == True
swapMade = False
FOR i=0 TO list.LENGTH – 2 // iterate through
all but the last item
IF list[i] > list[i+1] THEN
temp = list[i+1]
list[i+1] = list[i]
list[i] = temp
swapMade = True
ENDIF
NEXT i
ENDWHILE
RETURN list
ENDFUNCTION

Question 7

Describe the process of merge sort

Answer 7

1) The list is split into two halves.
2) For the left half:
- split the left half into halves until each sublist is of length one.
- merge the pair of sublists on the left half by repeating this process until all items are in
the merged list:
- comparing the first item in the left half with the first item in the right half;
- if the item in the left half is less than the item in the right half, add the item from
the left half to the merged list and read the next item from the left half;
- if the item in the right half is less than the item in the left half, add the item from
the right half to the merged list and read the next item from the right half;
- once either list is empty, any remaining items are added to the merged list.
3) For the right half:
- split the right half into halves until each sublist is of length one.
- merge the pair of sublists on the right half by repeating this process until all items are in
the merged list:
- comparing the first item in the left half with the first item in the right half;
- if the item in the left half is less than the item in the right half, add the item from
the left half to the merged list and read the next item from the left half;
- if the item in the right half is less than the item in the left half, add the item from
the right half to the merged list and read the next item from the right half;
- once either list is empty, any remaining items are added to the merged list.
4) Merge the left half and the right half by repeating this process until all items are in the merged
list:
- comparing the first item in the left half with the first item in the right half;
- if the item in the left half is less than the item in the right half, add the item from the left
half to the merged list and read the next item from the left half;
- if the item in the right half is less than the item in the left half, add the item from the right
half to the merged list and read the next item from the right half;
- once either list is empty, any remaining items are added to the merged list.

Question 8

What is the pseudocode for merge sort?

Answer 8

PROCEDURE mergeSort(list)
// base case
IF list.LENGTH > 1 THEN // if list is not, by definition, sorted
mid = list.LENGTH DIV 2 // performs integer division to find
the midpoint of the list
leftHalf = mergeList[:mid] // left half of list
rightHalf = mergeList[mid:] // right half of list
// recursive case
mergeSort(leftHalf) // recursive call for leftHalf
mergeSort(rightHalf) // recursive call for rightHalf
i = 0 // pointer to item in leftHalf (starting at the first item)
j = 0 // pointer to item in rightHalf (starting at the first item)
k = 0 // pointer to item in list (starting at the first item)
// while the first item in the leftHalf is less than the length of the
length of the leftHalf AND the first item in the rightHalf is less
than the length of the rightHalf
i.e. while there are still item in the leftHalf and rightHalf of the
sublists
WHILE i < leftHalf.LENGTH AND j < rightHalf.LENGTH
// if the item at the pointer in the leftHalf is less than the item
at the pointer in the rightHalf
IF leftHalf[i]<rightHalf[j] THEN
// the item at the pointer in leftHalf the becomes is added to
the list
list[k] = leftHalf[i]
// increment the pointer pointing to the item in the leftHalf
i = i + 1
ELSE
// the item at the pointer in rightHalf the becomes is added to
the list
list[j] = rightHalf[j]
ENDIF
// increment the pointer pointing to the item in the list
k = k + 1
ENDWHILE
WHILE i < leftHalf.LENGTH
mergeList[k] = leftHalf[i]
// increment the pointer pointing to the item in the leftHalf
i = i + 1
// increment the pointer pointing to the item in the list
k = k + 1
ENDWHILE
WHILE j < rightHalf.LENGTH
mergeList[k] = rightHalf[j]
// increment the pointer pointing to the item in the rightHalf
j = j + 1
// increment the pointer pointing to the item in the list
k = k + 1
ENDWHILE
ENDIF
ENDPROCEDURE

Question 9

Describe the process of insertion sort

Answer 9

1) Make the first item in the list the sorted portion of the list and the remaining items are the
unsorted portion of the list.
2) While there are items in the unsorted list:
- take the first item in the unsorted list;
- while there is an item to the left of the first item in the unsorted list:
- swap with that item;
- the sorted list is now one item bigger, as the first item of the unsorted list has become a
member of the sorted list.

Question 10

What is the pseudocode for insertion sort?

Answer 10

FUNCTION insertionSort(list)
FOR i=0 TO list.LENGTH-1 // iterate through all but the last item
currentItem = list[i] // take the first item in the unsorted list
position = i // set the position to the current index value
// while there are items in the unsorted list
WHILE position > 0 AND list[position - 1] > currentItem
// swap the items
list[position] = list[position – 1]
position = position – 1
ENDWHILE
list[position] = currentItem
NEXT i
RETURN list
ENDFUNCTION

Question 11

Describe the process of quick sort

Answer 11

1) Select a pivot value, sometimes the first item in the list.
2) Locate the two position markers:
- set leftMark variable to the index of the second item in the list (after the pivot); and
- set rightMark variable to the index of the last item in the list.
3) Move the items which are less than or equal to the pivot to the left-hand side of the pivot and
move the items which are greater than the pivot to the right-hand side of the pivot:
- compare the pivot to the item at the leftMark and if the item at the leftMark is less than
pivot, increment the leftMark (move to the right) – repeat this until the pivot is greater
than the item at the leftMark.
- compare the pivot to the item at the rightMark and if the item at the rightMark is greater
than the pivot, decrement the rightMark (move to the left) – repeat this until the pivot is
less than the item at the rightMark.
4) Exchange the item at leftMark with the item at rightMark and repeat stage 3).
5) When rightMark < leftMark, the split point is at the position of the rightMark.
6) Exchange the item at the pivot with the item at the split point.
7) Divide the list at the split point and recursively quick sort each half

Question 12

What is the pseudocode for quick sort?

Answer 12

FUNCTION partition(list, start, end)
pivot = list[start] // set the pivot to point to the first item
leftMark = start + 1 // set the leftMark to point to the item after the pivot
rightMark = end // set the rightMark to point to the last item
done = False // the split point has not been found
WHILE done == False // while the split point has not been found
// while the leftMark is less than or equal to the rightMark and the leftMark
is less than or equal to the pivot
WHILE leftMark <= rightMark AND list[leftMark] <= pivot
// increment the leftMark
leftMark = leftMark + 1
ENDWHILE
// while the rightMark is greater than or equal to the leftMark and the
rightMark is greater than or equal to the pivot
WHILE rightMark >= leftMark AND list[rightMark] >= pivot
// decrement the rightMark
rightMark = rightMark – 1
ENDWHILE
// if the pointer have swapped over
IF rightMark < leftMark THEN
// the split point has been found
done = True
ELSE
// the split point has not been found so swap the items at the leftMark and
the rightMark
temp = list[leftMark]
list[leftMark] = list[rightMark]
list[rightMark] = temp
ENDIF
ENDWHILE
// swap the item at the pivot with the item at the rightMark
temp = list[start]
list[start] = list[rightMark]
list[rightMark] = temp
// return the split point (rightMark)
RETURN rightMark
ENDFUNCTION
FUNCTION quicksort(list, start, end)
// base case
IF start < end THEN
// partition the list
split = partition(list, start, end)
// recursive case - quick sort the right half
quickSort(list, start, split-1)
// recursive case - quick sort the left half
quickSort(list, split+1, end)
ENDIF
RETURN list
ENDFUNCTION
list = [9, 5, 4, 15, 3, 8, 11]
sortedList = quicksort(list, 0, list.LENGTH-1)
PRINT(sortedList)

Question 13

What is the time complexity of bubble sort?

Answer 13

O(n^2)

Question 14

What is the space complexity of bubble sort?

Answer 14

O(1)

Question 15

What is the time complexity of merge sort?

Answer 15

O(n log n)

Question 16

What is the space complexity of merge sort?

Answer 16

O(n log n)

Question 17

What is the time complexity of insertion sort?

Answer 17

O(n^2)

Question 18

What is the space complexity of insertion sort?

Answer 18

O(1)

Question 19

What is the time complexity of quick sort?

Answer 19

O(n log n)

Question 20

What is the space complexity of quick sort?

Answer 20

O(log n)