Sorting

Question 1

Bubble Sort

Answer 1

Iterates over every element, comparing each pair and swapping if necessary. No more iterations are needed once no swaps take place. It has high time complexity O(n^2) best case but can be improved to O(n) if given sorted list.

Question 2

Selection Sort

Answer 2

Iterates over each element and swaps it with the smallest element int the remaining list. Works well for small sets. Time complexity is O(n^2) best case.

Question 3

Insertion Sort

Answer 3

Every repetition removes an element from the input, and inputs into the correct position. Best when the input data is nearly sorted or the input size is small. Time complexity is O(n^2) worst case and O(n) best case.

Question 4

Shell Sort

Answer 4

It is an improvement of insertion sort and is faster than bubble, selection, and insertion sorting. Time complexity is O(nlogn) worst case and O(n) best case.

Question 5

Merge Sort

Answer 5

The list is divided into two parts and these are solved recursively, then they are merged.Used for sorting a linked list. It is insensitive to the initial ordering of the list. Time complexity is O(nlogn) best and worst case.

Question 6

Heap Sort

Answer 6

Used to sort priority queues. Time complexity is O(nlogn) best and worst case.

Question 7

Quicksort

Answer 7

It is an example of a divide-and-conquer algorithm. It is also called partition exchange sort. The array is divided into two, and the two sub-arrays are sorted by recursive calls. In the recursion, if there are 1 or no items in the array, return. Else, an element is picked at random to use as the “pivot”. This array is in turn split into 2. Time complexity is O(n^2) worst case and O(nlogn) best case.

Question 8

Tree Sort

Answer 8

Each element is scanned and placed into the proper position of the binary search tree. Time complexity is O(n^2) worst case and O(nlogn) best case.

Question 9

Counting Sort

Answer 9

Assumes that each element is an integer in the range of 1 to K. Time complexity of O(n) in best and worst cases.

Question 10

Bucket/Bin Sort

Answer 10

Time complexity of O(n) in best and worst cases.

Question 11

Radix Sort

Answer 11

Time complexity of O(n) in best and worst cases.

Question 12

Topological Sort

Answer 12

Used to sort graphs.

Question 13

External Sorting

Answer 13

Uses another sort algorithm but allows to sort under memory constraints.