Data Structure and Algorithm

/***************************************************************************
Shell sort is a sorting algorithm, devised by Donald Shell in 1959, that is a generalization of insertion
sort, which exploits the fact that insertion sort works efficiently on input that is already almost sorted.
It improves on insertion sort by allowing the comparison and exchange of elements that are far apart.
The last step of Shell sort is a plain insertion sort, but by then, the array of data is guaranteed to be
almost sorted.

-------------------------------
SHELL SORT ALGORITHM
-------------------------------
input: an array num of length n with array elements numbered 0 to n - 1

Shell.Sort(num,n,key)
1. Assign, span = int(n/2)
2. while span > 0 do:
   a) for i from span to n - 1, Repeat step b,c,e
   b) assign num[i] to key and i to j
   c) while j = span and num[j - span] > key, Repeat step d
   d) swap num[j] and num[j - span]
   e) Assign, span = int(span / 2.2)
3. Use Insertion Sort to sort remaining array of data
----------------------------------------------------------------------------

The following is an implementation of Shell sort written in pseudocode.
The increment sequence is a geometric sequence in which every term is
roughly 2.2 times smaller than the previous one:
---------------------
SHELL SORT PSEUDOCODE
---------------------
span = int(n/2)
while span > 0 do:
for i = span .. n - 1 do:
   key =  num[i]
   j = i
   while j = span and num[j - span] > key do:
    num[j] = num[j - span]
    j = j - span
   num[j] = key
  span = int(span / 2.2)
****************************************************************************/

#include "iostream.h"
#include "conio.h"

void insertionSort(int num[],int N)
{
int i,j,key;
for(j = 1;j < N;j++) //From Second Element to Last
{
  key = num[j]; //Assign num[j] to key
   i = j - 1;
   while(i >= 0 && num[i] > key)
    {
     //Swap two elements
   num[i + 1] = num[i];
      i--;
      num[i + 1] = key;
    }
}
}

int main()
{
int num[50],N,i,j,span,key;
cout << "How many numbers? " ;
cin >> N;
cout << "\nEnter " << N << " Numbers\n";
for(i = 0;i < N;i++)
  cin >> num[i];

span = int(N/2);
while(span > 0)
  {
   for(i = span;i < N;i += span)
    {
     key = num[i];
     j = i;
     while(j >= span && num[j - span] > key)
      {
       num[j] = num[j - span];
       j = j - span;
      }

     num[j] = key;
    }
  span = int(span/2.2);
  }

//Now, the array of data is almost sorted
//So, using Insertion Sort as last step
insertionSort(num,N);

cout << endl;
for(int i = 0;i < N;i++)
  cout << num[i] << ' ';

getch();
return 0;
}

OUTPUT

How many numbers? 10

Enter 10 Numbers
25 65 47 88 64 10 -98 0 35 6

-98 0 6 10 25 35 47 64 65 88

Download Original File

/********************************************************************
--------------------------------------
ALGORITHM FOR MERGE SORT
--------------------------------------
mergesort(data,first,last)
1)if first < last
a)find middle as mid = (first + last) / 2
b)mergesort(data,first,mid)
c)mergesort(data,mid + 1,last);
d)merge(data,first,last)

merge(array1,first,last)
1)mid = (first + last) / 2
2)set i = first, j = mid + 1 and k = 0
3)while both left and right subarrays of array1 contain elements
a)if array1[i] < array1[j]
   temp[k++] = array1[i++]
b)else, temp[k++] = array1[j++]
4)Load into temp the remaining elements of array 1
5)load to array1 the content of temp

*********************************************************************/

#include "iostream.h"
#include "conio.h"

void merge(int *,int,int,int);

void mergesort(int *data,int first,int last)
{
int mid;
if(first < last) //If more than one element
  {
   mid = (first + last) / 2; //Find mid
   mergesort(data,first,mid); //Sort Left Subarray
   mergesort(data,mid + 1,last); //Sort Right Subarray
   merge(data,first,mid,last); //Merge Left and Right Subarray
  }
}

void merge(int *data,int first,int mid,int last)
{
int i,j,k;
i = first;
j = mid + 1;
k = 0;
int *temp = new int[last - first + 2];
while(i <= mid && j <= last) //While the end of Left or Right Subarray
  {
   //Compare data and save to temporary array
   if(data[i] < data[j])
    temp[k++] = data[i++];
   else
    temp[k++] = data[j++];
  }

if(i <= mid) //If more items in Left Subarray
  for(j = i;j <= mid;j++) //Copy items to temp
   temp[k++] = data[j];
else //more items in Right Subarray
  for(i = j;i <= last;i++)
   temp[k++] = data[i];

k = 0;
for(i = first;i <= last;i++) //Copy items from temporary array to original array
  data[i] = temp[k++];
}

int main()
{
int n,*arr;
clrscr();
cout << "How many Numbers? ";
cin >> n;
arr = new int[n];
cout << "\nEnter Elements : ";
for(int i = 0;i < n;i++) //Scan Inputs
  cin >> arr[i];

mergesort(arr,0,n - 1); //Sort
cout << endl << "\nSorted : ";
for(int i = 0;i < n;i++)
  cout << arr[i] << ' ';

getch();
return 0;
}

OUTPUT

How many numbers? 10

Enter Elements : 25 65 47 88 64 10 -98 0 35 6

Sorted : -98 0 6 10 25 35 47 64 65 88

Download Original File

Merge.cpp

/**********************************************
--------------------------------
QUICK SORT ALGORITHM
--------------------------------
Partition(a,p,q)
1. set i = p
2. for j from p + 1 to q, Repeat step 3 and 4
3. if a[j] <= a[p],increase i
4. Swap a[i] and a[j]
5. swap a[i] and a[p]
6. return i

Quick.Sort(a,p,q)
1. if p < q, Repeat step 2,3 and 4
2. set r = partition(a,p,q)
3. call recursively QuickSort(a,p,r - 1)
4. call recursively QuickSort(a,r + 1,q)
5. return
***********************************************/

#include "iostream.h"
#include "conio.h"

void swap(int &a,int &b)
{
int temp = a;
a = b;
b = temp;
}

int partition(int a[],int p,int q)
{
int i = p;
for(int j = p + 1;j <= q;j++) //from Second element to Last
  if(a[j] <= a[p]) //assign smaller element to Left of pivot
   {
    i++;
    swap(a[i],a[j]);
   }

swap(a[p],a[i]); //set Pivot
return i;
}

void QuickSort(int *a,int p,int q)
{
if(p < q)
  {
   int r = partition(a,p,q); //Find Pivot
   QuickSort(a,p,r - 1); //sort Left Subarray
   QuickSort(a,r + 1,q); //sort Right Subarray
  }
}

int main()
{
int num[50],n;
cout << "How many numbers? ";
cin >> n;
cout << "\nEnter " << n << " Numbers\n";
for(int i = 0;i < n;i++)
  cin >> num[i];

QuickSort(num,0,n - 1); //call function QuickSort with pivot at First

position

cout << endl;
for(int i = 0;i < n;i++)
  cout << num[i] << ' ';

getch();
return 0;
}

OUTPUT

How many numbers? 10

Enter 10 Numbers
25 65 47 88 64 10 -98 0 35 6

-98 0 6 10 25 35 47 64 65 88

Download Original File

Quick.cpp

/************************************
-------------------------------
INSERTION SORT ALGORITHM
-------------------------------
Insertion.Sort(num,n,key)
1. for j from 2 to n
2. assign num[j] to key
   assign j - 1 to i
3. while i > 0 and num[i] > key
swap num[i+1] and num[i]
4. Return
*************************************/

#include "iostream.h"
#include "conio.h"

int main()
{
int num[50],N,i,j,key;
cout << "How many numbers? " ;
cin >> N;
cout << "\nEnter " << N << " Numbers\n";
for(int i = 0;i < N;i++)
  cin >> num[i];

for(j = 1;j < N;j++) //From Second Element to Last
{
  key = num[j]; //Assign num[j] to key
   i = j - 1;
   while(i >= 0 && num[i] > key)
    {
     //Swap two elements
   num[i + 1] = num[i];
      i--;
      num[i + 1] = key;
    }
}

//Print Output
cout << endl;
for(i = 0;i < N;i++)
  cout << num[i] << ' ';

getch();
return 0;
}

OUTPUT

How many numbers? 10

Enter 10 Numbers
25 65 47 88 64 10 -98 0 35 6

-98 0 6 10 25 35 47 64 65 88

Download Original File

Insertion.cpp

/***************************************
------------------------------
SELECTION SORT ALGORTHM
------------------------------
Selection.Sort(num,n,least)
1. for i from 1 to n, Repeat step 2 & 3
2. find Least item of the array and,
  save index to least
3. Swap Least Element with ith Element
4. Return
****************************************/

#include "iostream.h"
#include "conio.h"

void swap(int &a,int &b)
{
int temp = a;
a = b;
b = temp;
}

int main()
{
int num[50],i,j,n,least;
cout << "How many numbers? ";
cin >> n;
cout << "\nEnter " << n << " Numbers\n";
for(i = 0;i < n ;i++)
  cin >> num[i];

for(i = 0;i < n;i++)
  {
   least = i; //set least to first index
   for(j = i + 1;j < n;j++) //from next index to n
    if(num[j] < num[least]) //find least element
     least = j; //Save Index

   swap(num[least],num[i]); //Swap least element with ith element
  }

//Print Output
cout << endl;
for(i = 0;i < n;i++)
  cout << num[i] << ' ';

getch();
return 0;
}

OUTPUT

How many numbers? 10

Enter 10 Numbers
25 65 47 88 64 10 -98 0 35 6

-98 0 6 10 25 35 47 64 65 88

Download Original File

Selection.cpp

/*********************************************
---------------------
BUBBLE SORT Algorithm
---------------------
Bubble.Sort(Data,N)
1. Repeat step 2 & 3 for i =  0 to N - 2
2. for j = 0 to j < N - i
3. if Data[j] < Data[j + 1]
swap Data[j] and Data[j + 1]
4. Return
**********************************************/

#include "iostream.h"
#include "conio.h"


void swap(int &a,int &b)
{
int temp = a;
a = b;
b = temp;
}

int main()
{
int num[50],n;
cout << "How many numbers? ";
cin >> n;
cout << "\nEnter " << n << " Numbers\n";
for(int i = 0;i < n;i++)
  cin >> num[i];

for(int i = 0;i < n - 2;i++) //outer loop from First to Second Last
  for(int j = 0;j < n - i;j++) //inner loop from First to n - i
   if(num[j] > num[j+1]) //if current number is greater than next number,
     swap(num[j],num[j+1]); //swap two numbres

/*
  or,
for(int i = 0;i < n - 2;i++) //outer loop from First to Second Last
  for(int j = n - 1;j > i;j--) //inner loop from last to greater than i
  if(num[j] < num[j - 1]) //if current number is less than next number,
    swap(num[j],num[j - 1]); //swap two numbers
*/

//Print Output
cout << endl << endl;
for(int i = 0;i < n;i++)
  cout << num[i] << ' ';

getch();
return 0;
}

OUTPUT

How many numbers? 10

Enter 10 Numbers
25 65 47 88 64 10 -98 0 35 6

-98 0 6 10 25 35 47 64 65 88

Download Original File