here is the code I came up with. I had to split it, please copy and past the two halves so you would have an idea about the program.
[ code ]
#include <iostream>
#include <CONIO.H>
#include <STDLIB.H>
#include <STDIO.H>
#include <TIME.H>
#include <FSTREAM>
///////////////////////////////////////////////////////
using namespace std ;
const int arrSize=30000;
fstream outfile ("SortingAlgorithms.txt");
//////////////////////////////////////////////////////
void insert_special( int x, int heap[], int start, int end ){
// insert x into the sub-heap from start to end
// location start is empt
int child = 2*start + 1; // left child of start
while (child <= end) {
if (child < end && heap[child] < heap[child + 1])
child++; // child is the larger child of start
if (x > heap[child])
break; // x stays in start
else {
heap[start] = heap[child];
start = child;
child = 2*start + 1;
}
}
heap[start] = x;
}
void buildHeap(int a[], int size )
// Build a heap from an array of items
// Binary tree with one node satisfies heap properties
// Therefore ignore leaves and start from the parent
// of the last item
{
int i;
for (i = (size - 2)/2; i >= 0; i--) // start from parent of last item
insert_special( a[i], a, i, size-1);
}
void heapSort( int a[], int size )
// sort an array of the given size
{
int i;
int temp;
buildHeap( a, size );
for (i = size-1; i >=1; i--) {
temp = a[i]; // extract the last element from the array
a[i] = a[0]; // move top of heap to the end of the array
insert_special( temp, a, 0, i-1 ); // restore heap properties
}
}
//////////////////////////////////////////////////////
void mergeConquer(int a[], int left, int mid, int right) {
int x=0;//counters
int y=0;
int z=0;
int lno = mid - left + 1;
int rno = right - mid;
int *L = new int[lno];
int *R = new int[rno];
//////////////////////////////////////
for ( y = 0; y < lno; y++) {
L[y] = a[left + y];
}
////////////////////////////////////
for (z = 0; z < rno; z++) {
R[z] = a[mid + z + 1];
}
y = 0;
z = 0;
/////////////////////////////////
for (int i = left; i <= right; i++) {
if ( (y < lno) && (z < rno)) {
if (L[y] <= R[z]) {
a[i] = L[y];
y++;
}
else {
a[i] = R[z];
z++;
}
}
else if ( (y < lno) && (z >= rno)) {
a[i] = L[y];
y++;
}
else if ( (y >= lno) && (z < rno)) {
a[i] = R[z];
z++;
}
}
}
///////////////////////////////////////////////////////////////////////////////////////
void mergeDivide(int a[], int left, int right) {
int mid = (left + right) / 2;
if (left < right) {
//cout << "============";
mergeDivide(a, left, mid);
mergeDivide(a, mid + 1, right);
mergeConquer(a, left, mid, right);
}
}
/////////////////////////////////////////////////////
void swap(int array[], int index1, int index2)
{
int temp = array[index1];
array[index1] = array[index2];
array[index2] = temp;
}
//////////////////////////////////////////////////////////////////////////////////////////
void quickSort(int array[], int start, int end)
{
int i = start;//counters
int k = end;
if (end - start >= 1)
{
int pivot = array[start];
while (k > i)
{
while (array[i] <= pivot && i <= end && k > i)
i++;
while (array[k] > pivot && k >= start && k >= i)
k--;
if (k > i)
swap(array, i, k);
}
swap(array, start, k);
quickSort(array, start, k - 1);
quickSort(array, k + 1, end);
}
else
{
return;
}
}
//////////////////////////////////////////////////////////////////////////////////////////
void sortItInQuick(int array[])
{
quickSort(array, 0, arrSize-1);
}
////////////////////////////////////////////////////////////////////////////////////////
void shuffelArray(int a[] ){
int x;
srand ( time(NULL) );
for(int i=0;i< arrSize;i++){
x=(((rand()%1000)*2)+165959802);
//x=(rand()%100);
//cout<<x<<endl;
a[i]=x;
//getch();
}
getch();
cout<<endl<<"------------------------------------------- end intioalzition"<<endl;
}
////////////////////////////////////////////////////////////
void printOnFile(int arr[],char name[],int time){
outfile<<endl<<"-------------------------------------------------------------------"<<endl;
outfile<<"-------------------------------------------------------------------"<<endl;
outfile<<"-------------------------------------------------------------------"<<endl;
outfile<<"-------------------------------------------------------------------"<<endl;
outfile<<name<<endl<<"and the time is : "<<time<<endl;
outfile<<"-------------------------------------------------------------------"<<endl;
outfile<<"-------------------------------------------------------------------"<<endl;
outfile<<"-------------------------------------------------------------------"<<endl;
outfile<<"-------------------------------------------------------------------"<<endl;
/*for(int i=0;i<arrSize;i++){
outfile <<arr[i]<<" ";
}*/
}
////////////////////////////////////////////////////////////
void copyArray(int arr1[],int arr2[],int size){
arr2=new int[size];
for(int i=0;i<size;i++)
arr2[i]=arr1[i];
}
////////////////////////////////////////////////////////////
void sortInsertions(int a[]) {
for (int j = 2; j < arrSize; j++) {
for (int k = 0; k < j; k++) {
if (a[j] < a[k]) {
int temp = a[k];
a[k] = a[j];
a[j] = temp;
}
}
}
}
//////////////////////////////////////////////////////
40
