May 282017
 

We discussed Insertion sort in detail earlier. This post shows the recursive implementation of Insertion Sort. Continue reading »

Apr 102017
 

Given a number N given in the form of array, with each index storing one digit of the number. Write code to change the number to the greatest number less than N, such that digits of that number are in non-decreasing order.

For example:

INPUT ARRAY: {1, 4, 3} (representing number 143)
OUTPUT : 139

INPUT ARRAY: {2, 2, 2, 1} (representing number 2221)
OUTPUT : 1999

Continue reading »

Jun 302013
 

watch_videoSelection sort is an in-place, comparison sorting algorithm. Like bubble sort it also divides the given array in two sub arrays sorted and unsorted, divided by an imaginary wall.

Initially all the elements will be in the unsorted list. Each pass will pick the smallest element from the unsorted list and add it at the end of the sorted list, this will move the imaginary wall one step forward making more room in the sorted list and less room in the unsorted list. Continue reading »

Jun 302013
 

watch_videoWhat is Bubble Sort. Write algorithm of mention the Time & Space complexity of the Algorithm. Also suggest improvements which will improve the best case running time of Algorithm to O(n).

Solution:

Bubble Sort is a sorting algorithm which compares two adjacent elements and swap them if they are not in the right order. To sort the entire array, the array is traversed n-1 time (array having n elements). These are called passes, In the first pass the largest element moves to the last position (sorting in ascending order). So if the original (unsorted) array is:

Continue reading »