T
Trent
Running this I see that on first run, both bubble and selection sort have 9
sort counts while insertion sort has ZERO. With a sorted list, should this
be ZERO for all?
Also bsort and Ssort have the same exact sorting counts also..shouldn't they
differ somewhat?
Source and data file below.
Thanks
Trent
#include <iostream>
#include <fstream>
#include<iomanip>
using namespace std;
void bubbleSort(int *array, const int, int &); //function prototypes
void selectionSort(int *, const int, int &);
void insertionSort(int *, const int, int &);
void swap(int *, int *);
void print(int *array, int size, int *bubbleSort, int *selectionSort, int
*insertionSort, int bcount, int scount, int icount);
// print(&numArray, arraySize, &bsort, &ssort, &isort,
bsortCounter,sSortCounter, iSortCounter);
ifstream inFile;
ofstream outFile;
int main()
{
const int arraySize = 10;
int numArray[arraySize];
int bsort[arraySize];
int bsortCounter =0;
int isort[arraySize];
int iSortCounter =0;
int ssort[arraySize];
int sSortCounter =0;
// each sort needs array and counter (parallel arrays)
inFile.open("input.txt"); //opening input file
if (!inFile)
{
cerr << "Error Opening File" << endl;
system("pause");
return -1;
}
for (int i =0;i < 5;i++)
{
for (int j=0; j< arraySize;j++)
{
inFile >> numArray[j];
bsort[j]=numArray[j];
isort[j]=numArray[j];
ssort[j]=numArray[j];
}
cout << endl;
bubbleSort(bsort, arraySize, bsortCounter);// call the sort functions
selectionSort(ssort, arraySize,sSortCounter);
insertionSort(isort, arraySize,iSortCounter);
print(numArray, arraySize, bsort, ssort, isort, bsortCounter,sSortCounter,
iSortCounter);\
}
cout << endl;
system("pause");
inFile.close();// close files
outFile.close();
return 0;
}
// Funtions below
void bubbleSort(int *array, const int size, int &count)
{
int i, pass;
for (pass =0; pass < size - 1; pass++) //# of passes
count= count+1;
for (i= 0; i < size - 1; i++) // one pass
if (array > array[i+1]) //one comparison
{
swap(array, array[i+1]);
}
}// end of bubble Sort function
void selectionSort(int *array, const int size, int &count)
{
int i, j, tmp;
for (i = 0; i < size - 1; i++)
{
tmp = i;
count = count + 1;
for (j = i+1; j < size; j++)
if (array[j] < array[tmp])
tmp = j;
swap(array, array[tmp]); //call swap funtion
}
}//end of selection sort function
void insertionSort(int *array,const int size, int &count)
{
int tmp,i;
for(int j=1;j<size;j++)
{
tmp=array[j];
i=j-1;
while(array>tmp && i>=0)
{
count = count +1;
array[i+1]=array;
i--;
}
array[i+1]=tmp;
}
}
void print(int *array, int size, int *bubbleSort, int *selectionSort, int
*insertionSort, int bcount, int scount, int icount)
{
cout << " Unsorted List Bubble Sorted Selection Sorted Insertion
Sorted" << endl;
for (int k =0;k < size;k++)
cout << setw(15) <<array[k] << setw(16) << bubbleSort[k] << setw(20) <<
selectionSort[k] << setw(19) << insertionSort[k] << endl;
cout << endl << "Number: " << setw(23) <<bcount << setw(20)<<scount
<<setw(19)<< icount << endl;
}// end of print function
void swap(int *element1, int *element2)
{
int tmp = *element1;
*element1 = *element2;
*element2 = tmp;
}
----------------------
Data Input File
----------------------
231
678
850
999
1050
1222
1325
1444
1600
1900
1900
1600
1444
1325
1222
1050
999
850
678
231
231
1444
850
999
678
1222
1050
1325
1600
1900
1050
999
850
678
231
1222
1325
1444
1600
1900
231
850
999
1050
1222
1325
1444
1600
1900
678
sort counts while insertion sort has ZERO. With a sorted list, should this
be ZERO for all?
Also bsort and Ssort have the same exact sorting counts also..shouldn't they
differ somewhat?
Source and data file below.
Thanks
Trent
#include <iostream>
#include <fstream>
#include<iomanip>
using namespace std;
void bubbleSort(int *array, const int, int &); //function prototypes
void selectionSort(int *, const int, int &);
void insertionSort(int *, const int, int &);
void swap(int *, int *);
void print(int *array, int size, int *bubbleSort, int *selectionSort, int
*insertionSort, int bcount, int scount, int icount);
// print(&numArray, arraySize, &bsort, &ssort, &isort,
bsortCounter,sSortCounter, iSortCounter);
ifstream inFile;
ofstream outFile;
int main()
{
const int arraySize = 10;
int numArray[arraySize];
int bsort[arraySize];
int bsortCounter =0;
int isort[arraySize];
int iSortCounter =0;
int ssort[arraySize];
int sSortCounter =0;
// each sort needs array and counter (parallel arrays)
inFile.open("input.txt"); //opening input file
if (!inFile)
{
cerr << "Error Opening File" << endl;
system("pause");
return -1;
}
for (int i =0;i < 5;i++)
{
for (int j=0; j< arraySize;j++)
{
inFile >> numArray[j];
bsort[j]=numArray[j];
isort[j]=numArray[j];
ssort[j]=numArray[j];
}
cout << endl;
bubbleSort(bsort, arraySize, bsortCounter);// call the sort functions
selectionSort(ssort, arraySize,sSortCounter);
insertionSort(isort, arraySize,iSortCounter);
print(numArray, arraySize, bsort, ssort, isort, bsortCounter,sSortCounter,
iSortCounter);\
}
cout << endl;
system("pause");
inFile.close();// close files
outFile.close();
return 0;
}
// Funtions below
void bubbleSort(int *array, const int size, int &count)
{
int i, pass;
for (pass =0; pass < size - 1; pass++) //# of passes
count= count+1;
for (i= 0; i < size - 1; i++) // one pass
if (array > array[i+1]) //one comparison
{
swap(array, array[i+1]);
}
}// end of bubble Sort function
void selectionSort(int *array, const int size, int &count)
{
int i, j, tmp;
for (i = 0; i < size - 1; i++)
{
tmp = i;
count = count + 1;
for (j = i+1; j < size; j++)
if (array[j] < array[tmp])
tmp = j;
swap(array, array[tmp]); //call swap funtion
}
}//end of selection sort function
void insertionSort(int *array,const int size, int &count)
{
int tmp,i;
for(int j=1;j<size;j++)
{
tmp=array[j];
i=j-1;
while(array>tmp && i>=0)
{
count = count +1;
array[i+1]=array;
i--;
}
array[i+1]=tmp;
}
}
void print(int *array, int size, int *bubbleSort, int *selectionSort, int
*insertionSort, int bcount, int scount, int icount)
{
cout << " Unsorted List Bubble Sorted Selection Sorted Insertion
Sorted" << endl;
for (int k =0;k < size;k++)
cout << setw(15) <<array[k] << setw(16) << bubbleSort[k] << setw(20) <<
selectionSort[k] << setw(19) << insertionSort[k] << endl;
cout << endl << "Number: " << setw(23) <<bcount << setw(20)<<scount
<<setw(19)<< icount << endl;
}// end of print function
void swap(int *element1, int *element2)
{
int tmp = *element1;
*element1 = *element2;
*element2 = tmp;
}
----------------------
Data Input File
----------------------
231
678
850
999
1050
1222
1325
1444
1600
1900
1900
1600
1444
1325
1222
1050
999
850
678
231
231
1444
850
999
678
1222
1050
1325
1600
1900
1050
999
850
678
231
1222
1325
1444
1600
1900
231
850
999
1050
1222
1325
1444
1600
1900
678