Selection Problem and its solution in ‘C’

We define selection problem as follows:

Input    : An array of N distinct numbers and an integer i, with 1 ≤ i ≤ N. 

Output : The element that is larger than exactly i – 1 other elements of the array.

You will obviously think of sorting the array and then simply finding the ith element in it, which can be done with O(N log N) time complexity using merge sort or quicksort or heapsort. But, can we do better than this? Yes, following randomized algorithm achieves this in O(N) expected running time practically.

This algorithm SELECT is modeled after the quicksort algorithm. As in quciksort, we partition the input array recursively. But unlike quicksort, which processes both sub-arrays, SELECT works on only one of these sub-arrays. This difference shows up in the analysis: whereas quicksort has an expected running time of O(N log N), the expected running time of SELECT is O(N). Explanation for the algorithm is clearly given in the code.          

Solution in C

Question: Select the ith minimum element in an array with O(N) expected running time.

Input:

First line of the input contains T, number of test cases

Each test case contains an integer N ≤ 200, the number of integers in that array, followed by N distinct integers separated by N spaces with i in the next line.

Output: ith minimum element.

Sample Input

2
5 4 7 9 3 1
3
4 6 10 5 7
1

Sample Output

4
5

Code

Explanation is given in the gist.

Quicksort and its Implementation in ‘C’

Like Merge Sort, Quicksort is a divide and conquer algorithm. Quicksort first divides the array into two smaller sub-arrays around a picked element called Pivot. Then recursively sort the sub-arrays. It works as follows:

  1. Pick an element, called a pivot, from the array.
  2. Reorder the array such that all the elements before pivot are less than pivot value, while all elements after pivot are grater than or equal to pivot. After this operation, the pivot is in its final position. This is the key process in quicksort, called the partition().
  3. Recursively apply this to the sub-arrays before and after the pivot. Look at this example.

There are different variants of Quicksort that pick pivots in different ways:

  1. First element of array.
  2. Last element of array.(used in the following implementation)
  3. Random element of array.
  4. Middle index element of array.

Complexities

Time complexity : O( N log N --  N log N -- N² ) [Best -- Average -- Worst] 
Memory          :  O(N or log N) # auxiliary i.e. apart from storing input array 
Stable          :  No i.e. can change relative order of elements with same key
# N being the number of elements in the array

Other popular sorting algorithms’ complexities are given here.

Usage and advantages

Continue reading

Merge Sort and its Implementation in ‘C’

Merge sort is an advanced sorting algorithm, derived from divide and conquer algorithmic paradigm. It works as follows:

1. Divide unsorted array into N sub-arrays, each containing one element. (which is sorted already)

2. Repeatedly merge these sub-arrays to produce sorted new ones until only 1 sub-array is left-out, this is the required sorted array.

Look at the following animation for clear understanding.

Merge sort animation.

Merge sort animation. Courtesy: Wikipedia.org

Complexities

Time complexity : O( N log N --  N log N -- N log N ) [Best -- Average -- Worst] 
Memory          :  O(N) # auxiliary i.e. apart from storing input array 
Stable          :  Yes i.e. doesn't change relative order of elements with same key
# N being the number of elements in the array

You can read complexities of other popular sorting algorithms here.

Usage and Applications

As of Perl 5.8, merge sort is its default sorting algorithm (it was quicksort in previous versions of Perl). In Java, the Arrays.sort() methods use merge sort or a tuned quicksort depending on the datatypes and for implementation efficiency switch to insertion sort when fewer than seven array elements are being sorted. Merge sort is often the best choice for sorting linked lists. Used to find inversion count of an array.

Bottom Line: Typically, default sort implementation for most of the languages is either Mergesort or Quicksort.

Implementation in C:

Continue reading

Insertion sort and its Implementation in ‘C’

Insertion sort is one of the simplest sorting algorithms, it works the way we sort the playing cards. It iterates up the given array, and growing a sorted array behind. At each array-position, it checks the value there against the value in the previous array-position. If larger, it leaves the element in that position and moves to the next. If smaller, it inserts the element into the correct position, shifting the larger values up to make space.

Example illustrating Insertion sort:

Input : 21 9 3 12 6
21 9 3 12 6 
9 21 3 12 6 // sorted subarray = {9,21}
3 9 21 12 6 // sorted subarray = {3,9,21}
3 9 12 21 6 // sorted subarray = {3,9,12,21}
3 6 9 12 21
output : 3 6 9 12 21
Insertion sort animation

Insertion sort animation. courtesy: wikipedia.org

Complexity

Time complexity : O( N --  N² -- N² ) [Best -- Average -- Worst] 
Memory          :  O(1) i.e. just the input array:"in place"
Stable          :  Yes i.e. doesn't change relative order of elements with same key
# N being the number of elements in the array

You can read about complexities of other sorting algorithms here.

Usage

It is much less efficient on larger arrays than the advanced sorting algorithms like quicksort, merge sort and heapsort. Easier to implement, more efficient in practice that the other O(N²) algorithms like selection sort and bubble sort.

Bottom line: Use this over selection or bubble sort.

Implementation in C

Continue reading

Selection Sort and its Implementation in ‘C’

Selection sort is one of the simplest sorting algorithms, at any instance it maintains two subarrays in a given array : one with the elements that are already sorted which is built up from left to right starting at front of the array, other with rest of elements in the array that are remaining to be sorted. The algorithm proceeds by finding the smallest element in the unsorted array and swapping it with the left most element of the unsorted array. Following example clarifies this sentence.

Input : 21 9 3 12 6
21 9 3 12 6 
3 9 21 12 6 // sorted subarray = {3}
3 6 21 12 9 // sorted subarray = {3,6}
3 6 9 12 21 // sorted subarray = {3,6,9}
3 6 9 12 21 // sorted subarray = {3,6,9,12}
output : 3 6 9 12 21

Complexity Analysis

You can read about complexities of other sorting algorithms here.

Time complexity : O( N²  --  N²-- N² ) [Best -- Average -- Worst]
Memory          :  O(1) i.e. just the input array:"in place"
Stable          :  Yes 
# N being the number of elements in the array

Usage

It is inefficient on larger lists due to its O() time complexity, and generally performs worse than the similar insertion sort. It is easier to implement than most of the other sorting algorithms, can be advantageous over other complicated algorithms, especially when the memory is limited.

Bottom line: Simplest algorithm one can implement when time complexity is not concerned.

Implementation in C

Continue reading