Sorting and Order Statistics Flashcards
How does Insertion sort work?
Insertion sort works by maintaining loop invariant on a subarray of the original array. At each step i of the main loop subarray A[0…i-1] is in sorted order. Inside of the array algorithm moves all the elements A[j] (j < i) larger (or smaller) than A[i] to the right. When it comes to an element which does not satisfy the sorting condition in relation to A[i] it stops and puts A[i] in its position. The loop then continues until i == len(A).
What’s your trick to remembering how insertion sort works?
Save the pivot. Copy all the bigger elements than the pivot one step to the right. This will create pairs of same elements as the loop continues. At the end when the element is not bigger than the pivot or the loop is at the beginning, as always there will be only one pair of same elements, put the pivot to this position.
How does Merge sort work?
Divide the problem of input size N on two subproblems with sizes N/2. Recursively sort the the two subproblems. Merge the subproblems solutions. Recursions stops when subproblem size is 1.
What’s the most important part of Merge sort algorithm?
The merge function.
How does merge function work in Merge sort algorithm?
It merges two already sorted arrays in one sorted array. For this it uses a helper array. It goes through each element of first and second subarray until one of those two subarray runs out of elements. In each iteration it copies the smaller of two current elements from subarrays from helper array to main array. After it’s done all of the elements from one subarray are copied in the right order from helper array to main array and the rest of the elements in the remaining subarray need to be copied.
How does Heap Sort work?
Heap Sort works by building a heap. After that it takes the first element of the max heap and exchanges it with the last element in array and decreases heap size. Then it build the heap again with the first element.
What is a priority queue?
A priority queue is a data structure for maintaining a set S of elements, each with an associated value called a key. It supports following operations: Insert, Maximum, Extract-Max, Increase-Key. It can be implemented using heaps.
