Sep 162013
 

To learn the basics of the Queue visit our previous post on implementing Queue using linked list. In case the Queue is implemented using Linked list Enqueue (insertion) is about inserting a new node at the end and Dequeue (removing an element) is about deleting the first node.

But, for array, things are little different. Continue reading »

pinkdiamonds.nl

Jul 262013
 

stackStack is a collection of objects where objects are inserted and removed in the Last-In-First-Out order. Element inserted at the end will be deleted first. It is a limited access data structure which essentially allows two operations push and pop.

Push: Inserting data at the top of stack.
Pop: deleting data from the top of stack.

The function call stack of C and C++ is a typical example of stack data structure. If we have three functions main, fun1 and fun2. main calling fun1 and fun1 calling fun2 as shown below. Continue reading »

Jul 262013
 

A better implementation of Stack is usually using linked list unless you are sure of the number of elements in array. But if you are just starting with data structures and are not familiar with linked list, you can try implementing stack in an array.

While using array to implement stack is easy, it has limitation that the stack cannot grow beyond a fixed size (of array).  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 »

Jun 292013
 

watch_videoBinary search is a Divide & Conquer algorithm used to search for an element in the array. It requires the array to be sorted. If array is not sorted then the only way to search in the array is Linear search.

Binary search divide the number of elements to be searched in two halves in each iteration and only one half remains relevant to be searched and the other is ignored. Therefore, even if the element is not present in the array we don’t need to traverse all the element in the list. Continue reading »

Jun 292013
 

watch_videoLinear search or Sequential search is a method for finding a particular value in a linear list of values (Array or Linked List). It is done by checking each of its elements, one at a time in list, until the desired one is found or the list is exhausted.

Problem definition (for array)

Given an Array of numbers a0, a1, a2, …, an. and a number x. Write a function which will return i, such that (ai == x). If x is not in the Array, then return -1 (which means “Not Found”).

Continue reading »