2.3.3 Sorting Algorithms
No description yet. This curated deck is ready for daily study.
Card preview (17)
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)
What is the time complexity for quick sort?
O (n log n)
What is the time complexity for insertion sort?
O(n²)