2.3.3 Sorting Algorithms Flashcards
How can a bubble sort be improved?
Adding a flag to record whether or not a swap has occured
Which sorting algorithm compares and swaps pairs of elements?
Bubble sort
What sorting algorithm places the largest element after the first pass?
Bubble sort
Name the 2 functions of a merge sort.
MergeSort( )
Merge( )
Which sorting algorithm uses pivots?
Quick sort
Which sorting algorithm is the fastest?
Quick sort
Outline the stages of a bubble sort.
Compare first value in list with the next
If first is bigger, swap the positions
Move to second value
Repeat until no more items to compare
Return to start of list
Repeat until pass through made without any swaps needed
Outline the stages of a merge sort.
Repeatedly divide list in two until all elements separated into sublists
Merge sublists to produce new sorted sublist
Repeat until elements are in single list
Outline the stages of an insertion sort.
Separates first value as sorted list
Compare next value in unsorted list with sorted
Move value to correct position
Repeat until the end of the list is reached
Outline the stages of a quick sort.
Pivot element selected
All elements less than moved to left of pivot, all elements greater move to right
Repeat process with new pivots for each side of list
What does the left pointer do in a quick sort?
Moves right until item larger than pivot found then it stops and hands to right pointer
What does the right pointer do in a quick sort?
Moves left until item smaller than pivot found then stops
What is the disadvantage of a quick sort?
If the split point is skewed too far left or right, division will be uneven
Results in O(n²) time complexity
What is the time complexity for bubble sort?
O(n)
What is the time complexity for merge sort?
O(n log n)
