Sorting Flashcards Preview

Big O Sorting > Sorting > Flashcards

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

Best , average, worst time of quicksort

Best: Ω(n log(n))

Average: Θ(n log(n))

Worst: O(n^2)

2

Worst space compl of quicksort

O(log(n))

3

Merge sort time best, avg, worst

Mergesort

Ω(n log(n))

Θ(n log(n))

O(n log(n))

4

Merge sort space worst

O(n)

5

Timsort best, avg, worst time

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

6

Timsort worst space

O(n)

7

Heapsort b,a,w time

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

8

Heapsort worst space

O(1)

9

Bubble sort b, a, worst time

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

10

Bubble sort worst space

o(1)

11

Insertion sort b,a ,w time

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

12

Inesrtion sort w space

O(1)

13

Selection sort b,a,w time

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

14

Selection sort worst space

O(1)

15

Tree sort time b,a,w

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

16

Tree sort worst space complexity

O(n)

17

Shell sort b,a,w time

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

18

Shell sort worst space

O(1)

19

Bucket sort b,a,w time

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

20

Bucket sort worst space

O(n)

21

Radix sort b,a,w time

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

22

Radix sort worst space

O(n+k)

23

Counting sort b,a,w time

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

24

Counting sort worst space

O(k)

25

Cube sort b,a,w time

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

26

Cubesort worst space

O(n)

27

Shellsort description

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

Bucket sort description

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

Cubesort description

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

Timsort description

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.