Heap Sort - Coursera Algorithms

Heap Sort is an in place sort that builds a max binary heap and then repeatedly deletes the maximum element. It's not stable and it's inner loop takes longer than Quick Sort. It has poor cache usage. To build a heap, it takes O(N) and for sort, it takes O(NlogN).

Following is the program:

Related Posts:

Binary Heap

Binary Heap - Coursera Algorithms

A binary tree is either empty or points to a root node with links to left and right binary trees. A tree is complete if it is balanced perfectly, excluding the bottom level. A binary heap is an array representation of a heap ordered complete binary tree.

Max node is root at a[1]. For a node k, it's parent is at k/2 and it's children are at 2k and 2k+1.
Swim: When a child node is greater than parent, keep exchanging them till they are ordered.
Sink: When a parent node is lesser than child, keep exchanging them till they are ordered.
In insert operation, add the child at end and swim it. --> O(logN)
In delete operation, exchange root with node at end and sink the top node. -->O(logN)

Following is the program:

Three Way Quick Sort - Coursera Algorithms

Three Way Quick Sort uses multiple partition elements, such that the there are no larger entries to their left and no smaller entries to their right. It is in place, but not a stable sort. This is used to deal with duplicate elements.

Time complexity: O(NlgN)


Following is the program, partition elements are from lt to gt:

Related Posts: 

Quick Sort

Insertion Sort 

Quick Select - Coursera Algorithms

Quick select finds k^th smallest element by partitioning. It takes linear time and O(N²) in worst case.

Following is the program:

Quick Sort - Coursera Algorithms

Quick Sort uses a partition element, such that the there are no larger entries to it's left and no smaller entries to it's right. It is in place, but not a stable sort.

Time complexity: O(NlgN)
Worst case : O(N²)

Following is the program:

Merge Sort - Coursera Algorithms

Merge sort uses divide and conquer approach to sort the elements. It takes at most NlgN compares and 6NlgN array accesses with total running time of NlgN.

Following is an optimized merge sort - it uses insertion sort for less number of elements. Please see Insertion Sort for the insertion sort algorithm. It also has a method for bottom up merge sort which is not as efficient as the recursive merge sort.

Related Posts: 

Insertion Sort

Shell Sort - Coursera Algorithms

Shell sort moves entries by more than one position at a time. It is basically insertion sort with a stride length h - it considers h interleaved sequences and sorts them using insertion sort. When the increment(h) is big, the sub-arrays are smaller and when the increment gets shorter in subsequent iterations, the array is already partially sorted. In both cases, insertion sort works great and hence, it's the best option here.

The optimal value for h is provided by Knuth as 3X+1, but no accurate model has been found for this algorithm yet.

It takes O(N3/2) compares in worst case. It's fast unless array size is large and it has less footprint for code. These make it a perfect choice for hardware sort prototype, linux/kernel, embedded systems etc.

Following is the program:

Related Posts: 

Insertion Sort

Insertion Sort - Coursera Algorithms

Insertion Sort swaps an element with a larger entry to it's left.

It take ~1/4 N2 compares and ~1/4 N2 exchanges.
Best case(already sorted) : N-1 compares and zero exchanges.
Worst case(reverse sorted):  ~1/2 N2 compares and ~1/2 N2 exchanges.
Partially sorted(when number of inversions <= cN): linear time as number of exchanges equal the number of inversions.

Following is the program, it also uses shuffle to make the order as random as possible. This is done by swapping each element with a random index r such that r is between 0 and iteration i. This takes linear time.

Selection Sort - Coursera Algorithms

Selection sort finds the minimum element and swaps it with the first element, till the complete array is sorted. It takes N²/2 compares and N exchanges.

Following is the program:

Generic Queue Using Resized Array And Iterator - Coursera Algorithms

To make the stack generic and to hide the internal representation of a queue from client, we can use Generics and Iterator.

Following is the program:

Generic Queue Using Linked List And Iterator - Coursera Algorithms

To make the stack generic and to hide the internal representation of a queue from client, we can use Generics and Iterator.

Following is the program:

Generic Stack Using Resized Array And Iterator - Coursera Algorithms

To make the stack generic and to hide the internal representation of a stack from client, we can use Generics and Iterator.

Following is the program:

Generic Stack Using Linked List And Iterator - Coursera Algorithms

To make the stack generic and to hide the internal representation of a stack from client, we can use Generics and Iterator.

Following is the program:

Queue Using Array Resizing - Coursera Algorithms

Queues follow FIFO standard. To implement, we need to maintain two indices to first and last elements of the array, for enqueue and dequeue operations.

Following is the program:

Related Posts: 

Queue Using Linked List - Coursera Algorithms

Queue Using Linked List - Coursera Algorithms

Queues follow FIFO standard. To implement, we need to maintain two pointers to first and last nodes of linked list, as we insert at the end of the list and removed the first element of the list for enqueue and dequeue operations.

Following is the program:

Stack Using Array Resizing - Coursera Algorithms

When implementing stacks using arrays, we may run into overflow and underflow problems. We can resize the array on need basis by doubling the array in push op when the array has reached it's limit and by halving the array in pop op when the array is just 25% utilized. 

This will result in constant amortized time operations, but ~N in worst case.

Linked list on the other hand has constant time even in worst case. But still, linked list may take more time and memory because of the links. 

If occasional slow ops are bearable, then arrays would be a better option than linked lists. 

Following is the complete program:

Related Posts:  

Stack Using Linked List - Coursera Algorithms

Stack Using Array - Coursera Algorithms

Stack Using Array - Coursera Algorithms

Stack works in a LIFO order. It supports insert, remove, iteration and test for empty operations.

They can be represented using array. An initial capacity for this array is taken as input. We manipulate an index variable for push and pop, instead of actually deleting items from stack.

If using objects in stack, avoid loitering(holding references to objects and preventing GC) by using following code in pop operation:

public String pop() { String item = s[--N]; s[N] = null; return item; } 

Following is the complete program:

Related Posts:  

Stack Using Linked List - Coursera Algorithms

Stack Using Linked List - Coursera Algorithms

Stack works in a LIFO order. It supports insert, remove, iteration and test for empty operations.

They can be represented using linked list. Push and pop operations are done on the first element. This takes constant time for any operation and about ~36N Bytes for N stack items - 16B overhead + 8B inner Node class + 8B reference to Node object + 4B for integer values.

Following is the program:

Finding maximum and minimum in union find algorithm

This post is a problem based on union find algorithm. For the algorithm, please see "Weighted Quick Union With Path Compression - Coursera Algorithms"

Problem: Given an element, find the max/min of it's connected components tree.

Following is my, probably brute force, solution to find max/min. For this, we use extra arrays to store the max and min values. We updated the max and min only for root nodes. For all other nodes, just find the root and it's max/min.

Weighted Quick Union With Path Compression - Coursera Algorithms

Weighted Quick Union can be improved further by path compression. The idea here is to avoid flatten the tree. After computing the root of a node,  we set the id of each examined node to point to that root.

Running Time:
For M union-find operations on N elements, running time  ≤ c ( N + M lg* N ) array accesses. 

lg*N = number of times we have to take log of N to get 1.

It's almost linear and union find doesn't have any linear algorithm.

Following is the program: