In: Computer Science
Compare radixSort to bubbleSort, SelectionSort, and InsertionSort
Compare quickSort to bubbleSort, SelectionSort, and InsertionSort
Answer 1:
Title |
Radix Sort |
Bubble Sort |
Selection Sort |
Insertion sort |
Definition |
Radix sort is a sorting technique that sorts the elements by first grouping the individual digits of the same place value. Then, sort the elements according to their increasing/decreasing order. |
Bubble sort is an algorithm that compares the adjacent elements and swaps their positions if they are not in the intended order. The order can be ascending or descending. |
Selection sort is an algorithm that selects the smallest element from an unsorted list in each iteration and places that element at the beginning of the unsorted list. |
Insertion sort is a sorting algorithm that places an unsorted element at its suitable place in each iteration. |
Example |
Let the initial array be [121, 432, 564, 23, 1, 45, 788] Step 1: [121, 1, 432, 23, 564, 45, 788] Step 2: [1, 121, 23, 432, 45, 564, 788] Step 3: [1, 23, 45, 121, 432, 564, 788] |
Let the initial array be [-2, 45, 0, 11, -9] Step 1: [-2, 0, 11, -9, 45] Step 2: [-2, 0, -9, 11, 45] Step 3: [-2, -9, 0, 11, 45] Step 4: [-9, -2, 0, 11, 45] |
Let the initial array be [20, 12, 10, 15, 2] Step 1: [2, 12, 10, 15, 20] Step 2: [2, 10, 12, 15, 20] Step 3: [2, 10, 12, 15, 20] Step 4: [2, 10, 12, 15, 20] |
Let the initial array be [9, 5, 1, 4, 3] Step 1: [5, 9, 1, 4, 3] Step 2: [1, 5, 9, 4, 3] Step 3: [1, 4, 5, 9, 3] Step 4: [1, 3, 4, 5, 9] |
Time complexity |
Best case : O(nk) Average Case: O(nk) Worst case: O(nk) Where k is maximum digit |
Best case : O(n2) Average Case: O(n2) Worst case: O(n2) |
Best case : O(n2) Average Case: O(n2) Worst case: O(n2) |
Best case : O(n) Average Case: O(n2) Worst case: O(n2) |
Space complexity |
O(n) |
O(1) |
O(1) |
O(1) |
Applications |
Radix sort is implemented in
|
Bubble sort is used in the following cases where
|
The selection sort is used when:
|
The insertion sort is used when:
|
Answer 2:
Title |
Quick Sort |
Bubble Sort |
Selection Sort |
Insertion sort |
Definition |
Quicksort is an algorithm based on divide and conquer approach in which the array is split into subarrays and these sub-arrays are recursively called to sort the elements. |
Bubble sort is an algorithm that compares the adjacent elements and swaps their positions if they are not in the intended order. The order can be ascending or descending. |
Selection sort is an algorithm that selects the smallest element from an unsorted list in each iteration and places that element at the beginning of the unsorted list. |
Insertion sort is a sorting algorithm that places an unsorted element at its suitable place in each iteration. |
Example |
Let the initial array be [8, 7, 6, 1, 0, 9, 2] Step 1: [1, 7, 6, 8, 0, 9, 2] Step 2: [1, 0, 6, 8, 7, 9, 2] Step 3: [1, 0, 2, 8, 7, 9, 6] Step 4: [0, 1, 2, 8, 7, 9, 6] Step 5: [0, 1, 2, 6, 7, 9, 8] Step 5: [0, 1, 2, 6, 7, 8, 9] |
Let the initial array be [-2, 45, 0, 11, -9] Step 1: [-2, 0, 11, -9, 45] Step 2: [-2, 0, -9, 11, 45] Step 3: [-2, -9, 0, 11, 45] Step 4: [-9, -2, 0, 11, 45] |
Let the initial array be [20, 12, 10, 15, 2] Step 1: [2, 12, 10, 15, 20] Step 2: [2, 10, 12, 15, 20] Step 3: [2, 10, 12, 15, 20] Step 4: [2, 10, 12, 15, 20] |
Let the initial array be [9, 5, 1, 4, 3] Step 1: [5, 9, 1, 4, 3] Step 2: [1, 5, 9, 4, 3] Step 3: [1, 4, 5, 9, 3] Step 4: [1, 3, 4, 5, 9] |
Time complexity |
Best case : O(log n) Average Case:O(log n) Worst case: O(n2) |
Best case : O(n2) Average Case: O(n2) Worst case: O(n2) |
Best case : O(n2) Average Case: O(n2) Worst case: O(n2) |
Best case : O(n) Average Case: O(n2) Worst case: O(n2) |
Space complexity |
O(log n) |
O(1) |
O(1) |
O(1) |
Applications |
Quicksort is implemented when
|
Bubble sort is used in the following cases where
|
The selection sort is used when:
|
The insertion sort is used when:
|