Quick Sort Flashcards
1
Q
What is quick sort
A
Quick sort orders data set extremely quickly using divide and conquer
2
Q
How does quick sort work
A
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
3
Q
What is quick sort suitable for
A
Suitable for any data set but shines with larger data set, ideal for parrell processing where divide and conquer is used
4
Q
IRL examples of quick sort
A
Medical monitoring, life support, aircraft control, defence system
5
Q
Pseudocode for quick sort steps
A
- 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 - Repeat from step one to the left of pointer
- Repeat from step 1 right of pointet
6
Q
Actual pseudocode uses recursion
A
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