Sorting Flashcards
What is bubble sort?
A simple sorting algorithm that repeatedly swaps adjacent elements in a list until they are ordered
What is the best and worst case time complexity of bubble sort?
O(n) - linear best case
O(n^2) - worst case quadratic
Explain how you implement bubble sort?
Loop through each element in a double loop bubbling each element until it is ordered
What is selection sort?
Selection Sort is a simple sorting algorithm that works by repeatedly finding the minimum element in an unsorted part of the list and moving it to the beginning of the list. This process is repeated for each unsorted element until the entire list is sorted.
What is the best and worst case time complexity of selection sort?
Best and worst cose quadratic O(n^2) because O(n) for passes and O(n) for comparisons
Explain how you implement selection sort?
Why is selection sort not a good choice for developers?
Selection sort is O(n^2) so its not a good choice for large lists or in performance-critical applications, but useful for educational purposes
Merge sort and quick sort are more efficient.
What is insertion sort?
Insertion Sort is a simple sorting algorithm that works by repeatedly inserting each unsorted element into its correct position in the sorted part of the list.
Its similar to sorting a deck of cards by repeatedly inserting cards into the correct position.
Instead of swapping elements, it shifts the other elements
What is the time complexity of insertion sort?
Best: O(n) because O(n) iteration and O(1) shift
Worst: O(n^2) because iteration and shift O(n^2)
What is merge sort?
{8,2,4,1,3}
- Split at the middle index (=length/2 = 5/2 = 2)
- Split the left subarray at the middle ({8} and {2})
Sorted left: {2, 8}
Now sorted right:
3. middle = 3/2 = 1, {4} and {1, 3}
4. split right sub array = {1} and {3}
5. merge {1,3}
Sorted right: {1, 3, 4}
Now merge both by reading a value from each array and putting in the smaller one
{1,2,3,4,8}
What type of algorithm is merge sort an example of?
Merge sort is an example of a divide and conquer algorithm
What is the best and worst case time complexity of merge sort?
O(log n) - logarithmic time because dividing O(log n) and merging is O(n)
When is merge sort a good choice?
when you need to sort large lists efficiently
O(log n) so faster than others like Bubble Sort, Selection sort and Insertion sort
when the data is too large to fit into memory - divide and conquer means it can split the data into smaller chunks, sort them and then merge them again
How would you implement merge sort in Java?
- Divide the array
- Sort each half of the array
- Merge the array
