Sorting

Question 1

Best , average, worst time of quicksort

Answer 1

Best: Ω(n log(n))

Average: Θ(n log(n))

Worst: O(n^2)

Question 2

Worst space compl of quicksort

Answer 2

O(log(n))

Question 3

Merge sort time best, avg, worst

Answer 3

Mergesort

Ω(n log(n))

Θ(n log(n))

O(n log(n))

Question 4

Merge sort space worst

Answer 4

O(n)

Question 5

Timsort best, avg, worst time

Answer 5

TimsortΩ(n)Θ(n log(n))O(n log(n))

Question 6

Timsort worst space

Answer 6

O(n)

Question 7

Heapsort b,a,w time

Answer 7

HeapsortΩ(n log(n))Θ(n log(n))O(n log(n))

Question 8

Heapsort worst space

Answer 8

O(1)

Question 9

Bubble sort b, a, worst time

Answer 9

Bubble SortΩ(n)Θ(n^2)O(n^2)

Question 10

Bubble sort worst space

Answer 10

o(1)

Question 11

Insertion sort b,a ,w time

Answer 11

Insertion SortΩ(n)Θ(n^2)O(n^2)

Question 12

Inesrtion sort w space

Answer 12

O(1)

Question 13

Selection sort b,a,w time

Answer 13

Selection SortΩ(n^2)Θ(n^2)O(n^2)

Question 14

Selection sort worst space

Answer 14

O(1)

Question 15

Tree sort time b,a,w

Answer 15

Tree SortΩ(n log(n))Θ(n log(n))O(n^2)

Question 16

Tree sort worst space complexity

Answer 16

O(n)

Question 17

Shell sort b,a,w time

Answer 17

Shell SortΩ(n log(n))Θ(n(log(n))^2)O(n(log(n))^2)

Question 18

Shell sort worst space

Answer 18

O(1)

Question 19

Bucket sort b,a,w time

Answer 19

Bucket SortΩ(n+k)Θ(n+k)O(n^2)

Question 20

Bucket sort worst space

Answer 20

O(n)

Question 21

Radix sort b,a,w time

Answer 21

Radix SortΩ(nk)Θ(nk)O(nk)

Question 22

Radix sort worst space

Answer 22

O(n+k)

Question 23

Counting sort b,a,w time

Answer 23

Counting SortΩ(n+k)Θ(n+k)O(n+k)

Question 24

Counting sort worst space

Answer 24

O(k)

Question 25

Cube sort b,a,w time

Answer 25

CubesortΩ(n)Θ(n log(n))O(n log(n))

Question 26

Cubesort worst space

Answer 26

O(n)

Question 27

Shellsort description

Answer 27

Shellsort, also known as Shell sort or Shell’s method, is an in-place comparison sort. It can be seen as either a generalization of sorting by exchange (bubble sort) or sorting by insertion (insertion sort).[3] The method starts by sorting pairs of elements far apart from each other, then progressively reducing the gap between elements to be compared. Starting with far apart elements, it can move some out-of-place elements into position faster than a simple nearest neighbor exchange. Donald Shell published the first version of this sort in 1959.[4][5] The running time of Shellsort is heavily dependent on the gap sequence it uses. For many practical variants, determining their time complexityremains an open problem.

Question 28

Bucket sort description

Answer 28

Bucket sort, or bin sort, is a sorting algorithm that works by distributing the elements of an array into a number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm, or by recursively applying the bucket sorting algorithm. It is a distribution sort, a generalization of pigeonhole sort, and is a cousin of radix sort in the most-to-least significant digit flavor

Bucket sort works as follows:

Set up an array of initially empty “buckets”.

Scatter: Go over the original array, putting each object in its bucket.

Sort each non-empty bucket.

Gather: Visit the buckets in order and put all elements back into the original array.

Question 29

Cubesort description

Answer 29

Cubesort is a parallel sorting algorithm that builds a self-balancing multi-dimensional array from the keys to be sorted. As the axes are of similar length the structure resembles a cube. After each key is inserted the cube can be rapidly converted to an array.[1]

Question 30

Timsort description

Answer 30

Timsort is a hybrid stable sorting algorithm, derived from merge sort and insertion sort, designed to perform well on many kinds of real-world data. It uses techniques from Peter McIlroy’s “Optimistic Sorting and Information Theoretic Complexity”. The algorithm finds subsequences of the data that are already ordered, and uses that knowledge to sort the remainder more efficiently. This is done by merging an identified subsequence, called a run, with existing runs until certain criteria are fulfilled.

Question 31

Counting sort description

Answer 31

Counting Sort

Counting sort is a sorting technique based on keys between a specific range. It works by counting the number of objects having distinct key values (kind of hashing). Then doing some arithmetic to calculate the position of each object in the output sequence.