Chapter 15 Flashcards
What is stable sorting
Unlike unstable sorting, If there are duplicate keys in data set then after sorting the duplicate keys order will be the same as before. And also the data associated with keys maintain its key value pair position.
Does bubble sort, selection sort and insertion sort are in-place sorting algorithm
Yes
Which sorting algorithm is stable and which sorting algorithm unstable by nature
Bubble sort
Insertion sort
are stable algorithm but
Selection sort is unstable algorithm
Does mergesort stable and in-place algorithm
Merge sort is a stable algorithm but not in-place algorithm.
Does quicksort stable and in-place algorithm
Quicksort is not stable but an in-place algorithm
Does heapsort stable and in-place algorithm
Heapsort is not stable but an in-place algorithm
Does comparison based algorithm always n log n
Yes
What is in-place algorithm
In computer science, an in-place algorithm is an algorithm which transforms input using no auxiliary data structure. The input is usually overwritten by the output as the algorithm executes. It requires 2 arrays one is origin and other is target.
What is T(n)
Running time
What is Stirling’s approximation
Stirling’s approximation (or Stirling’s formula) is an approximation for factorials. It is a good-quality approximation, leading to accurate results even for small values of n.
Is it possible to sort without making comparison
Yes
What is linear time sorting
There are sorting algorithms that run faster than O(n lg n) time but they require special assumptions about the input sequence to be sort. Examples of sorting algorithms that run in linear time are counting sort, radix sort and bucket sort.
What is counting sort
Recall that the rank of an item is the number of elements that are less than or equal to. Once we know the ranks, we simply copy numbers to their final position in an output array.
If k is theta(n) then counting sort is an theta(n) time algorithm. True/False
True
