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:

Decimal To Binary Conversion Using Stack

Stack can be used to convert a number into it's binary form.

1. Push the remainder into stack after dividing the number by 2.
2. Keep doing 1, till number>0.
3. Pop the binary remainders 1/0 to get the binary form.

 Following is the program: