#include <iostream.h>
#include <stdio.h>
#include<conio.h>
class List
{
public:
int arr[20];
int sorted[20];
int cmp_count; //Number of comparisons
int mov_count; //Number of data movements
// Number of elements in array
int n;
List()
{
cmp_count = 0;
mov_count = 0;
}
void read()
{
// Get the number of elements to store in the array
while (1)
{
cout << "\nEnter the number of elements in the array: ";
cin >> n;
if (n <= 20)
break;
else
cout << "\nArray can have maximum 20 elements.\n";
}
cout << "\n-----------------------\n";
cout << " Enter array elements \n";
cout << "-----------------------\n";
// Get array elements
for (int i = 0; i < n; i++)
{
cout << "<" << i + 1 << "> ";
cin >> arr[i];
}
}
void m_sort(int low, int high)
{
int mid;
if (low >= high)
return;
mid = (low + high) / 2;
m_sort(low, mid);
m_sort(mid + 1, high);
merge(low, mid, high);
}
void merge(int low, int mid, int high)
{
int i, j, k;
i = low;
j = mid + 1;
k = low;
while ((i <= mid) && (j <= high))
{
if (arr[i] <= arr[j])
{
sorted[k++] = arr[i++];
}
else
{
sorted[k++] = arr[j++];
}
cmp_count++;
}
//If there are still some elements in the first sub list
//append them to the new list.
while (i <= mid)
{
sorted[k++] = arr[i++];
mov_count++;
}
//If there are still some elements in the second sub list
//append them to the new list.
while (j <= high)
{
sorted[k++] = arr[j++];
mov_count++;
}
//Copy the sorted elements in the original array
for (i = low; i <= high; i++)
{
arr[i] = sorted[i];
mov_count++;
}
}
void display()
{
cout << "\n-----------------------\n";
cout << " Sorted array elements \n";
cout << "-----------------------\n";
for (int j = 0; j < n; j++)
{
cout << arr[j]<< endl;
}
cout << "\nNumber of comparisons: " << cmp_count;
cout << "\nNumber of data movements: " << mov_count;
}
int getSize()
{
return (n);
}
};
void main()
{
clrscr();
// Declaring the object of the class
List myList;
// Accept the array elements
myList.read();
// First call to merge sort algorithm
myList.m_sort(0, myList.getSize() - 1);
// Display sorted array
myList.display();
getch();
}
0 comments:
Post a Comment