Quick Sort

Question 1

What is quick sort

Answer 1

Quick sort orders data set extremely quickly using divide and conquer

Question 2

How does quick sort work

Answer 2

Uses a pivot value from data to compare against rest of the data to determine positions
More efficient than Merge sort typically requires less memory but depends on how much is sorted and chosen pivot

Question 3

What is quick sort suitable for

Answer 3

Suitable for any data set but shines with larger data set, ideal for parrell processing where divide and conquer is used

Question 4

IRL examples of quick sort

Answer 4

Medical monitoring, life support, aircraft control, defence system

Question 5

Pseudocode for quick sort steps

Answer 5

1. Set a pointer to the first and last item in the list
   2a. While the first pointer is not equal to the second pointer
   2b. Move 1st pointer one item towards 2nd pointer
2. Repeat from step one to the left of pointer
3. Repeat from step 1 right of pointet

Question 6

Actual pseudocode uses recursion

Answer 6

Pointer 1 = 0
Pointrer2 = items.Length - 1
While pointer!= pointer2
If(items[pointer] > items[pointer] and pointer < pointer2) or (items[pointer1] < items[pointer2] and pointer1 > pointer2) Then
Swap(items[pointer1], items[pointer2])
Swap(pointer1, pointer2)
End If
If Pointer1 < pointer2 Then
Pointer1 = Pointer1 + 1
Else
Pointer1 = Pointer 1 - 1
End If
End While
Left = quicksort(items[0 to pointer1])
Right = quicksort(items[pointer1 + 1 to items.Length])
Return left + items[Pointer1] + right
End Function