Sorting Flashcards Preview

Big O Sorting > Sorting > Flashcards

Flashcards in Sorting Deck (31)
Loading flashcards...
1
Q

Best , average, worst time of quicksort

A

Best: Ω(n log(n))

Average: Θ(n log(n))

Worst: O(n^2)

2
Q

Worst space compl of quicksort

A

O(log(n))

3
Q

Merge sort time best, avg, worst

A

Mergesort

Ω(n log(n))

Θ(n log(n))

O(n log(n))

4
Q

Merge sort space worst

A

O(n)

5
Q

Timsort best, avg, worst time

A

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

6
Q

Timsort worst space

A

O(n)

7
Q

Heapsort b,a,w time

A

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

8
Q

Heapsort worst space

A

O(1)

9
Q

Bubble sort b, a, worst time

A

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

10
Q

Bubble sort worst space

A

o(1)

11
Q

Insertion sort b,a ,w time

A

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

12
Q

Inesrtion sort w space

A

O(1)

13
Q

Selection sort b,a,w time

A

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

14
Q

Selection sort worst space

A

O(1)

15
Q

Tree sort time b,a,w

A

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

16
Q

Tree sort worst space complexity

A

O(n)

17
Q

Shell sort b,a,w time

A

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

18
Q

Shell sort worst space

A

O(1)

19
Q

Bucket sort b,a,w time

A

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

20
Q

Bucket sort worst space

A

O(n)

21
Q

Radix sort b,a,w time

A

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

22
Q

Radix sort worst space

A

O(n+k)

23
Q

Counting sort b,a,w time

A

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

24
Q

Counting sort worst space

A

O(k)

25
Q

Cube sort b,a,w time

A

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

26
Q

Cubesort worst space

A

O(n)

27
Q

Shellsort description

A

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.

28
Q

Bucket sort description

A

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.

29
Q

Cubesort description

A

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]

30
Q

Timsort description

A

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.

31
Q

Counting sort description

A

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.