Sorting and Searching

Most of the software problems can be solved by sorting it.

The most common algorithms are Quick Sort, Merge Sort, Heap Sort, Smooth Sort, Bubble Sort, Insertion Sort, Selection Sort and Bucket Sort.

Implementation of these algorithms is not something you will be asked in interviews but the computation complexity and the algorithm idea will be helpful to solve many software problems. 

We will discuss about Insertion Sort, Quick Sort, Heap Sort, Bucket Sort and Merge Sort here,  

Insertion Sort :

A simple sorting algorithm for small set of data. Its order of complexity is O(N^2). If you are looking for an online algorithm you need Insertion Sort.

The only logic in this algorithm is to swap the elements at index i and i-1 if Arr[i-1] > Arr[i].

Computational Complexity : average case O(N^2), worst case O(N^2)
Space Complexity : O(1)

Below is the C++ code.

http://codepad.org/ifroX6ZD

C# code :

Quick Sort :

The gist of QuickSort is to select a pivot element, arrange all the elements in the array such that element less than the pivot are to the left of pivot and the ones greater than pivot are to the right of pivot. This process is recursively applied to the elements lesser than the pivot and the greater ones.

Computational Complexity :  average O(N^2), worst case O(Nlog(N))
Space Complexity : O(Nlog(N))

Here is the code for Quick Sort.

http://codepad.org/arFqgAG5

Merge Sort : 

Coming Soon

Heap Sort:

Coming Soon

Bucket Sort:

Coming Soon

Selection Sort:

As the name suggests we select either the minimum or maximum among the sub set of elements and add it to the already sorted sub set, resulting in a sorted final array.

Here is the code in C++

http://codepad.org/oIE3SSfO


1) Given a array of unsorted numbers segregate the numbers such that all the negative numbers come before zeros and all the positive numbers come after zeros.

A) Lets take an index for positive numbers, an index for negative numbers and an iterator.

     Initialize the positive index with  [length of the array - 1].
     Initialize the negative index with 0.

     The code below shows the actual implementation

     http://codepad.org/RzGv9cdg