Big O - Array Sorting Algorithms Flashcards
What is the best time complexity of quicksort?
O(n log(n)) - bad
What is quicksort?
A divide and conquer algorithm where it divides the array into two smaller sub arrays. An index in each array is chosen as pivot, and the pivot compares itself to all the other entries so all smaller values are before it and all larger values are behind it. Recursively goes through each sub array (the one before and the one after the pivot position) and repeats.
What is the average time complexity of quicksort?
O(n log(n)) - bad
What is the worst time complexity of quicksort?
O(n^2) - terrible
What is the worst space complexity of quicksort?
O(log(n)) - good
What is merge sort?
A comparison based divide and conquer algorithm, where the list is divided into sublists of one element, then compared with an adjacent list to merge the two lists until it is sorted. A new array needs to be allocated to store the sorted list.
What is the best time complexity of merge sort?
O(n log(n)) - bad
What is the average time complexity of merge sort?
O(n log(n)) - bad
What is the worst time complexity of merge sort?
O(n log(n)) - bad
What is the worst space complexity of merge sort?
O(n) - okay
What is timsort?
An adaptive sorting algorithm designer by Tim Peters, where it identifies the longest “run” (sorted subarray) and chooses either insertion or merge sort.
What is the best time complexity of timsort?
O(n) - great!
What is the average time complexity of timsort?
O(n log(n)) - bad
What is the worst time complexity of timsort?
O(n log(n)) - bad
What is the worst space complexity of timsort?
O(n) - okay
What is heapsort?
The High-Level Idea
Heapsort is similar to selection sort—we’re repeatedly choosing the largest item and moving it to the end of our array. The main difference is that instead of scanning through the entire array to find the largest item, we convert the array into a max heap ↴ to speed things up.
Strengths
Fast. Heap sort runs in O(nlg(n))O(n\lg(n))O(nlg(n)) time, which scales well as nnn grows. Unlike quicksort, there’s no worst-case O(n2)O(n^2)O(n2) complexity.
Space efficient. Heap sort takes O(1)O(1)O(1) space. That’s way better than merge sort’s O(n)O(n)O(n) overhead.
Weaknesses
Slow in practice. While the asymptotic complexity of heap sort makes it look faster than quicksort, in real systems heap sort is often slower. (Remember, nnn and 2n2n2n are both O(n)O(n)O(n), even though the first is twice as fast as the second. Heap sort’s O(nlg(n))O(n\lg(n))O(nlg(n)) hides constant factors, but they still impact overall performance.)
Source: https://www.interviewcake.com/concept/java/heapsort
What is the best time complexity of heapsort?
O(n log(n)) - bad
What is the average time complexity of heapsort?
O(n log(n)) - bad
What is the worst time complexity of heapsort?
O(n log(n)) - bad
What is the worst space complexity of heapsort?
O(1) - great since it is done in place
What is bubble sort?
A simple algorithm that begins from the beginning of the list and compares adjacent pairs and swaps their position if not sorted. It repeatedly goes through the list, which grows shorter each time as the larger values get sorted to the end.
What is the best time complexity of bubble sort?
O(n) - good, only needs to go through once
What is the worst space complexity of bubble sort?
O(1) - great, done in place
What is the average time complexity of bubble sort?
O(n^2) - horrible
What is the worst time complexity of bubble sort?
O(n^2) - horrible
What is the best time complexity of insertion sort?
O(n) - great
What is the average time complexity of insertion sort?
O(n^2) - horrible
What is the worst time complexity of insertion sort?
O(n^2) - horrible
What is the worst space complexity of insertion sort?
O(1) - great, done in place
What is selection sort?
How It Works
Selection sort works by selecting the smallest element from an unsorted array and moving it to the front.
Here’s how it’d work on this array:
We’ll scan through all the items (from left to right) to find the smallest one …
… and move it to the front.
Now, the first item is sorted, and the rest of the array is unsorted.
Repeat! We’ll look through all the unsorted items, find the smallest one, and swap it with the first unsorted item.
We can do this for the next-smallest item
Source: https://www.interviewcake.com/concept/java/selection-sort
What is the best time complexity of selection sort?
O(n^2) - horrible
What is the average time complexity of selection sort?
O(n^2) - horrible
What is the worst time complexity of selection sort?
O(n^2) - horrible
What is the worst space complexity of selection sort?
O(1) - great
What is the best time complexity of bucket sort?
O(n + k), where K is number of buckets
What is the average time complexity of bucket sort?
O(n + k), where K is number of buckets
What is the worst time complexity of bucket sort?
O(n^2) - horrible
What is the worst space complexity of bucket sort?
O(n) - okay
What is radix sort?
A non-comparative sorting algorithm that sorts data with integer keys by grouping keys by individual digits that share the same significant digit position and value. Starts with 1s place, then 10s, then 100s, etc.
What is the best time complexity of radix sort?
O(nk) - good, but k is variable
What is the average time complexity of radix sort?
O(nk) - good, but k is variable
What is the worst time complexity of radix sort?
O(nk) - good, but k is variable
What is the worst space complexity of radix sort?
O(n+k)
What is bucket sort?
A comparison sorting algorithm that sets up an array of empty buckets. It distributes the contents of the original array in the buckets. Each non empty bucket is sorted, then each bucket is visited in order and put back in the original array.
What is insertion sort?
A super simple sorting algorithm where it removes one element from the list, finds where it belongs in the sorted list, and inserts it there. It can be performed online (as the list is being received). Good for short lists, bad for long ones.
