RANDOMIZED AND HIGHER SORTING METHODS

Purpose of randomization

Randomized algorithms are faster, easier to implement, or easier to analyze

than deterministic algorithms for some applications

Randomized Analysis of InsertionSort

Observation: For each round, M(i) ≤ C(i) ≤ M(i) + 1.

Observation: Shift → #Inversions decreases by exactly 1

#Inversions= sum from i to n(sum from j=i+1 to n(Z_ij))= #M(moves)

Quicksort Idea

• If in my sequence all elements a₁, . . . , a_i−1 are smaller than a_i and all elements a_i+1, . . . , a_n are greater than ai, then the elements before and after can be sorted independently (divide-and-conquer).

• In particular, it also holds that a_i is already in the correct position in the sorted sequence.

Quicksort algo

1. Choose one element from the sequence as the pivot element p.

2. Check for each element in the sequence whether it is greater or smaller than p, and move it left or right of p if necessary

• Swap the pivot with the element at the far left.

• Traverse from outside to inside and swap elements if necessary.

• if both i(left) j(rgt) are bigger than pivot move j

• if one is smaller/larger swap

• if both are smaller move i

• Swap the pivot to the correct position.

3. Let p now be at position i of the sequence. Perform steps 1 and 2 on a1, . . . , ai−1 and ai+1, . . . , an (unless 1 = i − 1 or i + 1 = n).

Quicksort algo analysis

bad pivot choice: elem at posn 1, min/max

good pivot choice: always median elem, random elem

Mergesort idea

Given two already sorted sequences a1, . . . , an and b1, . . . , bm, these can be merged into a sorted sequence in linear time.

With each comparison, another element of the sorted sequence is added. ⇒ in total ≤ n + m comparisons

Mergesort algo

• Recursively divide the input in half into two sequences until single elements

• Merge adjacent subsequences.

Heapsort Idea

Find the maximum and place it at the end of the sequence. Repeat the process on the remaining sequence iteratively.

Heap

A heap is a left complete binary tree in which for every node, the children do not store values greater than itself.

Binary tree

each node has at most two children

left complete

all nodes up to the penultimate level have exactly two children, all nodes at the last level are as far left as possible

Heap Ops

insert(WT x): inserts element x such that the heap property still holds

extractMax(): returns the root element, deletes it from the heap, and repairs it

Heap as arrays

Store tree from top to bottom from left to right.

O(log n)

insert(WT x)

extractMax()

• Remove root element.

• Set last array element at root position +heapify(follow heap rule)