Monthly Archives: May 2013

How does Bubble sort works?

Bubble sort is a comparison based sorting algorithm. It works like following. 
We perform series of iterations to ‘bubble up’ the elements one by one so that they form a sorted order. For example we have to sort an array [3,1,4,5,2] in ascending order, In the first iteration, the element 5 will be bubbled up to the last spot. In the second iteration element ‘4’ will be moved to the last but first spot and so on. The following sequence shows one iteration. In each step in the iteration, successive pairs of elements are compared, if they violate the order, swap it. 

3<->1 4 5 2 
1 3<->4 5 2 
1 3 4<->5 2 
1 3 4 5<->2 
1 3 4 2 5 

This iteration is repeated until the entire array is sorted. In the first iteration, there will be n-1 comparisons. In the second iteration there will be n-2 comparisons. The number of comparisons decreases with each iteration. The last iteration will have only one comparison. The following code shows the implementation of the above approach. The time complexity of bubble sort is O(n^2).
 
#include <iostream>
using namespace std;

//helper method to swap two elements
void swap( int &a, int &b)
{
int temp = a;
a = b;
b = temp;
}
//bubble sort function, takes array and it's size
//as parameters
void bubble_sort(int *array, int n)
{
int i,j;
//outer loop runs for n-1 iterations
for( i = 0 ; i < n-1 ; i++)
{
//inner loop is for comparisons
//in each iteration comparisons reduce by 1
for( j = 0 ; j < n-1-i ; j++)
{
//if elements are out-of-order, swap them
if( array[j] > array[j+1] )
swap(array[j], array[j+1]);
}
}
}
int main()
{
int n;
cin>>n;
int *array = new int[n];
int i;
for( i = 0 ; i < n ; i++ )
{
cin>>array[i];
}
bubble_sort(array,n);
for( i = 0 ; i < n ; i++)
{
cout<<array[i]<<" ";
}
return 0;
}
 

In bubble sort there is a mechanism to detect if the input array is already sorted. In any iteration, if there are no swappings performed, then we can conclude that the array is sorted. Here is how we can modify the bubble sort to implement this. 

void bubble_sort(int *array, int n)
{
int i,j;
bool swap_flag = false;
//outer loop runs for n-1 iterations
for( i = 0 ; i < n-1 ; i++)
{
//inner loop is for comparisions
//in each iteration the comparisions count reduce by 1
for( j = 0 ; j < n-1-i ; j++)
{
//if elements are out-of-order, swap them
if( array[j] > array[j+1] )
{
swap(array[j], array[j+1]);
swap_flag = true;
}
}
//if no swaps are performed in the inner loop, break
if( !swap_flag )
break;
}
}

Program to find GCD of two numbers

In mathematics, the greatest common divisor (gcd), also known as the greatest common factor (gcf), or highest common factor (hcf), of two or more integers (at least one of which is not zero), is the largest positive integer that divides the numbers without a remainder – from Wikipedia
For example, the GCD of 8 and 12 is 4
Euclidian method: This is also called division algorithm. Take smallest of the two numbers and divide the other number. If the remainder is zero smaller number is the GCD. Otherwise replace the smaller number with remainder, and bigger number with present smaller number and repeat the same procedure.

Here is the step-by-step calculation

8)12(1
   8
 —-
   4)8(2
     8
    —
     0

The following c++ code implements the iterative and recursive version of Euclidian algorithm.

#include <iostream>

using namespace std;
void swap(int &x, int &y)
{
int temp = x;
x = y;
y = temp;
}
//iterative version of Euclidian algorithm
int gcd(int x,int y)
{
while ( (y % x) != 0)
{
int r = y % x;
y = x;
x = r;
}
return x;
}
//recursive version of Euclidian algorithm
int gcd_recursive(int x, int y)
{
if( y % x == 0)
return x;
return gcd_recursive( y%x, x);
}

int main()
{
int x,y;
//read two numbers
cin>>x>>y;
//both iterative and recursive versions requires first parameter <= second
//swap if firt is greater
if( x > y )
{
swap(x,y);
}
cout<<"GCD(" << x << "," << y << ")=" << gcd_recursive(x,y) << endl;
return 0;
}

Finding the length of a linked list

In this post we will see an algorithm to find the length of the linked list. Here singly linked list is implemented in Object Oriented Programming (OOP) paradigm in C++. The algorithm is very simple. Just start at the beginning of the linked list, move to next until you reach the end of the list, incrementing a counter in each iteration. Following is the source C++ code for the same.

#include <iostream>

using namespace std;

//Node definition for a single linked list
class SLLNode
{
private:
//data member
int data;
//pointer to next node in the linked list
SLLNode *nextPtr;

public:

//Single argument constructor
//initializes data with d, next pointer to NULL
SLLNode(int d):data(d),nextPtr(NULL)
{
}
//to initialize both members
SLLNode(int d,SLLNode* next):data(d),nextPtr(next)
{
}
//returns the data
int getData()
{
return data;
}
//sets the data
void setData(int d)
{
this->data = d;
}
//gets the next pointer
SLLNode* getNext()
{
return this->nextPtr;
}
//sets the next pointer
void setNext(SLLNode *ptr)
{
this->nextPtr = ptr;
}
};

//defines the actual single linked list
class SinglyLinkedList
{
private:
//maintain two pointers to the start and the end
//so that we can append at the end easily (constant time complexity)
SLLNode * head;
SLLNode * tail;
public:
SinglyLinkedList()
{
head = NULL;
tail = NULL;
}
//adds the node to the end of the list
void appendNode(SLLNode* ptr)
{
//check if list is empty
if( head == NULL)
{
//update both the pointers
head = tail = ptr;
}
else //simply append at the end, and move the tail pointer
{
tail->setNext(ptr);
tail = tail->getNext();
}
}
//gets the length of the list
int getLength()
{
int length = 0;

SLLNode* ptr = head;

while ( ptr != NULL )
{
length++;
ptr = ptr->getNext();
}
return length;
}
};

int main()
{
SinglyLinkedList list;
list.appendNode(new SLLNode(1));
list.appendNode(new SLLNode(2));
list.appendNode(new SLLNode(3));
list.appendNode(new SLLNode(4));
cout<<"Length: "<<list.getLength()<<endl;
return 0;
}

Member initialization list in C++

You all know that in C++, constructors are used to create an object. We normally initialize all the data members with some valid data in the constructor. We generally write code similar to the following and think that m_data variable is being initialized where as it is actually being assigned.

class MyClass
{
public:
Myclass(int d)
{
m_data = d;
}
private:
int m_data;
}
 

To actually initialize a data member, we need to use member initialization list in C++. Using member initialization list, the constructor is written as follows

class MyClass
{
public:
Myclass(int d):m_data(d)
{
}
private:
int m_data;
}
 

Here we specified the member initialization list after constructor name followed by colon (:) If multiple members are present, they are separated by Comma. like m_data1(d1), m_data2(d2). In this case the members are initialized before entering the constructor itself.

What happens in the first case?  The default constructor (that is provided by the compiler) is called to initialize non-primitive data types before entering the written constructor. All the primitive type data members like int, char, float are not guaranteed to get initialized in the default constructor.

Finding the missing element in an array:

An array of size (n-1) contains all the numbers in the range [1..n] except one number which is missing. Write a program to find the missing number in O(n) time and O(1) space.

For example let N= 5 and the input array is [1,3,4,5], the output should be 2.

Given O(n) space we can always maintain a boolean array of size n to store a flag for each number if it is present or not. Here the restriction is to use constant extra space.

Two methods are discussed here.

Method#1:
Find sum of all the elements in given array. Let it be sum1. Find the sum of numbers from 1 to n. It would be n*(n+1)/2 (remember Arithmetic Progression from your school mathematics?) let it be sum2. Now subtracting sum1 from sum2 ( sum2-sum1) gives the required result.
Method#2:
Find XOR of all the elements in the array, let it be ax. Find XOR of elements from
[1..n], let it be nx. Then performing XOR between these two gives the missing number

The following C++ code shows the implementation of both the methods stated above. Both algorithms run in O(n) time and O(1) space complexity.

#include <iostream>
using namespace std;
//array contains n-1 numbers, this method finds
//the nth number missing.
int findMissingNum(int *array, int n)
{
//sum of first n numbers 1...n
int nSum = n*(n+1)/2;
//find array sum
int arSum = 0;
for( int i = 0 ; i < n-1 ; i++)
{
arSum += array[i];
}
// difference between two sum, gives the missing number
return nSum - arSum;
}

int findMissingNumXor(int *array,int n)
{
int nXor; //XOR of 1..N elements
int arXor; //XOR of array elements
int i;
//find XOR of 1 to n elements
for( i = 0 ; i < n ;i++)
{
nXor = nXor ^ (i+1);
}
//find XOR of array elements
for( i = 0 ; i < n-1 ; i++)
{
arXor = arXor ^array[i];
}
//XOR of two gives the result
return nXor ^arXor;
}
int main()
{
int *array;
int n;
cin>>n;
//allocate memory for n-1 numbers
array = new int[n-1];
int i;
//read n-1 numbers as input
for( i = 0; i < n-1; i++)
{
cin>>array[i];
}

cout<<findMissingNumXor(array,n);
//deallocate dynamic memory
delete[] array;
return 0;
}

Couple elimination problem

Given a string of some symbols, write a program to transform a string by repeatedly eliminating two same symbols occurring together.
For example if the input string is ‘RGGB’ it will be reduced to ‘RB’ because ‘GG’ can be eliminated.

Here are some more examples of input – output
Input   | Output
——————-
GBRRBR  | GR
BGRGRR  | BGRG
GGBB    | <empty>
RGBGBR  | RGBGBR

Here is how we can solve this problem. Add each character into a temporary array. As you insert the character, check for previously inserted character. If it is same, erase that character otherwise add it to the temporary array. At the end, the temporary array has the transformed string.

C++ implementation of the above approach is given below.

 
#include <iostream>
#define MAX 100
using namespace std;

int main()
{
char string[MAX];
char temp[MAX];

cin>>string;
int i;
int tempInd = 0; //to track temp string

for( i = 0 ; string[i] != '' ; i++)
{
//If temp string has atleast one character
if( tempInd > 0)
{
//If previous, and current chars are same, erase
if( temp[tempInd-1] == string[i] )
{
tempInd--;
}
else//not same, append the char to temp
{
temp[tempInd++] = string[i];
}
}
else //temp is empty, simply append the character
{
temp[tempInd++] = string[i];
}
}
//append the NULL character at the end
temp[tempInd] = '';
//print the transformed string
cout<<temp<<endl;
return 0;
}

Replacing spaces in a character array with %20

Given a character array which contains some spaces. we have to replace all the spaces with the string ‘%20’. This algorithm is commonly used during HTML encoding of the URLs in the web browsers. Assume that the array has enough space at the end to accommodate the expanded string, how do we do this efficiently?

The following solution uses no extra space and runs in O(n) time. The trick here is to start copying the characters from the end, and wherever we find space replace it with ‘%20’. The following C++ code does exactly that.

#include <iostream>
#define MAX 100
using namespace std;

void replaceSpace(char *array)
{
int len=0,i;
int spaceCount = 0;
//this loop calculates the spaces and length of the string
for( i = 0 ; array[i] != '' ; i++ )
{
//count spaces
if( array[i] == ' ')
spaceCount++;
//update length
len++;
}
//array has enough space, try to copy the string from end
//end index will be length + 2*no of spaces bcoz for each space
//there will be (3-1=2) two additional characters inserted
int resInd = len + 2*spaceCount;

//len is the index of '' (i.e last) in the original string
//start copying from there
while ( len >= 0)
{
//if space, insert %20 in reverse, bcoz we are copying from reverse
if( array[len] == ' ')
{
array[resInd--] = '0';
array[resInd--] = '2';
array[resInd--] = '%';
}
else //copy as it is
{
array[resInd--] = array[len];
}
len--;
}
}
int main()
{
char chArray[MAX];
gets(chArray);
replaceSpace(chArray);
cout<<chArray<<endl;
return 0;
}

Common elements between two sorted arrays

Given two sorted arrays, how do you efficiently find the common elements between those two?

Method#1:
Simple and Brute-force approach
Iterate through one array, and try to find the element in another array using linear search. If it is found, then print it. This approach takes O(n^2) time as for each element in the first array we doing a linear search in the second array which takes O(n). So for n elements it would be O(n^2).

Method#2:
Better approach with binary search
This approach is simliar to the first one except that it uses binary search instead of linear search for finding an element in the second array as the arrays are sorted. Binary search takes O(log n) for each element. So for n elements the time complexity would be O(n log n).

Method#3:
Efficient
This method fully utilizes the fact that both arrays are sorted. Start with two indices pointing to beginning of the arrays. If the elements pointed by these indices are same, then it is a common element, and we advance both the pointers. If one element is smaller, then advance that pointer (in hope of finding the next equal element). Continue this until any one of the two indices reaches their end.

Here is the C++ code which implements the third approach.

#include <iostream>
#include <string>
#include <vector>

using namespace std;

//prints the intersection of two sorted arrays
//duplicates are allowed
void printIntersect(vector<int>& s1, vector<int>& s2)
{
//i and j start 0 i.e first element
int i = 0 , j= 0;

//while either of the two indices reaches end
while ( i < s1.size() && j < s2.size() )
{
//if first array element is lesser, advance that index by one
if( s1[i] < s2[j] )
{
i++;
}
//otherwise advance second index
else if( s1[i] > s2[j] )
{
j++;
}
//both elements are same, print it, and advance both the pointers
else
{
cout<<s1[i]<<" ";
i++;
j++;
}
}
}

int main()
{
vector<int> set1, set2;
int n1,n2; //size of the sets
cin>>n1>>n2;

int i;
//read two arrays
for( i = 0 ; i < n1; i++ )
{
int d;
cin>>d;
set1.push_back(d);
}
for( i = 0 ; i < n2; i++ )
{
int d;
cin>>d;
set2.push_back(d);
}
printIntersect(set1,set2);
return 0;
}

Rotating an array

Rotating an array:

In this post we will discuss two solutions for rotating an array by a given number of times. One is a simple solution and another uses the reversal operation (discusses in the previous post).

Method#1: Simple and intuitive

In this method, we will copy the last element into a variable, and shift all the elements right by one step, and copy the stored element into the empty spot created at the beginning of the array. We repeat this for the given number of times.

Method#2: Using reversal algorithm

I have taken this algorithm from here. It is a three step procedure. Let array[0:n-1] be the array, and ‘s’ be the number of times to rotate the array.
step 1: Reverse the sub-array array[0:s-1]
step 2: Reverse the sub-array array[s:n-1]
step 3: Reverse the whole array i.e array[0:n-1]
 

For example let the array be [7 1 2 3 8], and it is to be rotated 3 times
here is how it works
step 1: [2 1 7 3 8]
step 2: [2 1 7 8 3]
step 3: [3 8 7 1 2]

C++ implementation of the above two methods is given below.

#include <iostream>
#include <string>

using namespace std;

//right rotates array of size n by s positions
//assumes that n > 1 (atleast 2 elements) and s < n
void rotateSimple( int* array, int n, int s)
{
int i;
int j;
for( i = 0 ; i < s ; i++ )
{
//store the last element
int last = array[n-1];

//shift all elements right by one
for( j = n-2 ; j >= 0 ; j-- )
{
array[j+1] = array[j];
}
//copy stored element to the beginning
array[0] = last;
}
}
//helper method for reversal
void swap( int &a, int &b)
{
int temp = a;
a = b;
b = temp;
}

//function to reverse the sub-array array[low to high
void reverseArray(int *array, int low, int high)
{
while( low < high ) //until both ends meet
{
swap( array[low], array[high] ); //swap the elements
low++; //increment left
high--;//decrement right
}
}
//rotate the array using reversal operation
void rotateByReverse(int* array,int n, int s)
{
reverseArray(array,0,s-1);
reverseArray(array,s,n-1);
reverseArray(array,0,n-1);
}

//utlity to print the array
void printArray(int * array,int n)
{
for( int i = 0; i < n; i++ )
{
cout<<array[i]<<" ";
}
cout<<endl;
}

int main()
{
int n; //array size
int s; //rotation count
//read array size, and rotation count
cin>>n>>s;
//dynamically allocate array based on input size
int *array = new int[n];
int i;
for( i = 0 ; i < n; i++ )
{
cin>>array[i];
}
//call rotate function
rotateByReverse( array, n, s);
printArray( array, n);
//release the memory
delete[] array;
return 0;
}

Reversing an array

In this post we will discuss a simple problem on Arrays. Given an array of numbers, how do we reverse it efficiently?

Here is the simple and effective approach. We start with one index pointing to the start, and another index pointing to the end of the array. We swap the two elements at these indices, increment left index, and decrement right index. We continue this procedure until both indices meet each other. Then we stop. At the end, the array is reversed.

For example, let us consider the array with 5 elements, Here is how it works
Array: [1  2  3  4  5] – swap
        |           |
       left       right
      
       [5  2  3  4  1] – swap
           |     |
          left  right
      
       [5  4  3  2  1] – stop
              |
             left
             right

 
#include <iostream>
#include <string>

using namespace std;

void swap( int &a, int &b)
{
int temp = a;
a = b;
b = temp;
}
//function to reverse the array
void reverseArray(int *array, int n)
{
int low = 0; //initialize low to first element
int high = n-1; //initialize high

while( low < high ) //until both ends meet
{
swap( array[low], array[high] ); //swap the elements
low++; //increment left
high--;//decrement right
}
}
void printArray( int *array,int n)
{
for(int i = 0 ; i < n;i++ )
{
cout<<array[i]<<" ";
}
cout<<endl;
}
int main()
{
int n;
cin>>n;
int* array = new int[n];
int i;

for( i = 0 ; i < n ; i++)
{
cin>>array[i];
}
reverseArray( array, n);
printArray( array, n);
return 0;
}