Quick Sort Flashcards

You may prefer our related Brainscape-certified flashcards:
1
Q

What is quick sort

A

Quick sort orders data set extremely quickly using divide and conquer

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

IRL examples of quick sort

A

Medical monitoring, life support, aircraft control, defence system

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Pseudocode for quick sort steps

A
  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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly