Sort Algorithms

Question 1

Time complexity of bubble sort

Answer 1

O(n**2)

Question 2

Time complexity of insert sort

Answer 2

O(n^2)

Question 3

Bubble sort vs Insertion sort

Answer 3

Both has time complexity of O(n^2), where sorting time will grow quadratically.
Insertion sort takes less time than bubble sort for large values of n.

Question 4

Time complexity of merge sort

Answer 4

O(nlogn)

Question 5

Time complexity of quick sort (worst and average)

Answer 5

Worst case: O(n^2)
Worst case occurs when:
1. the elements in the array is mostly sorted
2. Pivot chosen is not the median

average: O(nlogn)

Question 6

What does stable mean?

Answer 6

Stable implementation ensures that order of elements with same sorting characteristics is preserved

Question 7

What does in place/ out of place mean?

Answer 7

Out of place means that additional data structures are instantiated /created in the process
In place means that additional data structures are not created as the process is done in the original array.

Question 8

Describe Bubble Sort (S,M,SD,LD,ASD)

Answer 8

Stable
small Memory usage as implementation is usually in place and not much overhead
efficient with Small Datasets
slowest with Large Datasets
efficient with Almost Sorted Datasets

Question 9

Describe Insertion Sort (S,M,SD,LD,ASD)

Answer 9

Stable
small Memory usage as in place implementation
efficient with Small Datasets
inefficient with Large Datasets as time complexity O(n^2)
most efficient with Almost Sorted Datasets

Question 10

Describe mergsort (S,M,SD,LD,ASD)

Answer 10

Stable
large Memory usage as implementation is usually recursive and thus incurs large overhead
inefficient with Small Datasets
efficient with Large Datasets
inefficient with almost sorted Datasets as the array will be divided regardless of

Question 11

Describe quick Sort (S,M,SD,LD,ASD)

Answer 11

usually Unstable
Memory usage depends on in place/out of place
efficient with Small Datasets
efficient with Large Datasets but slower than mergesort
MOST INEFFICIENT with Almost Sorted Datasets as the array is split up regardless, which makes the array more unsorted