Selection Sort ( slow sort for a small number of items ):
- Code: Select all
/****************************************************************
* File Name : c:\programs\tempCG.cpp
* Date : March,28,2009
* Comments : new project
* Compiler/Assembler : Visual C++ 6.0
* Modifications :
*
* Notes: A good sort for a small number of items. Total run time
* is proportional to the number of items squared ( o ( N^2 ) ).
*
*
* Program Shell Generated At: 11:25:48 a.m.
=-=-=-=-=-=-=-=--=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=*/
#include < iostream >
//#include < string.h >
//#include < conio.h >
//#include < math.h >
//#include < iomanip >
//#include < ctype.h >
#include <stdlib.h>
#include <time.h>
using namespace std;
//>>>>>>>>>>>>>>>>>>>>>>>> GLOBAL DATA <<<<<<<<<<<<<<<<<<<<<<<<<
const int MAX_NUMBERS = 50;
int NUMBERS_PER_LINE = 15;
//<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
//@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ FUNCTION PROTOTYPES @@@@@@@@@@@@@@@@@@@@@@@@@@
void generateNumbers ( int * numbers , int numberItems );
void selectionSort ( int * array , int numberItems );
void printArray ( int * array , int numberItems );
//##################################################################################
//main function ******************************
int main ( )
{
int array [ MAX_NUMBERS ];
generateNumbers ( array , MAX_NUMBERS );
cout << endl << endl;
cout << "unsorted array " << endl;
printArray ( array , MAX_NUMBERS );
selectionSort ( array , MAX_NUMBERS );
cout << "sorted array: " << endl;
printArray ( array , MAX_NUMBERS );
cout << endl;
return 0 ;
}
/******************************* FUNCTION DEFINITION ******************************
Name : selectionSort
Parameters :
array a(n) int * ,
numberItems a(n) int
Returns: Void type
Comments: Slow n^2 algorithm
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
void selectionSort ( int * array , int numberItems )
{
int i = 0 , j , minimumIndex , temp;
while ( i <= numberItems )
{
minimumIndex = i; //select i to be smallest index
j = minimumIndex + 1; //start sorting at next index after
while ( j <= numberItems )
{
if ( array [ j ] < array [ minimumIndex ] ) //if we have found a smaller than minimum
{ //element , mark current as smallest
minimumIndex = j;
}
j ++; //goto next item in the array
}
if ( minimumIndex != numberItems ) //if we found a smaller item put it at the front
{ //of the sorted array
temp = array [ minimumIndex ]; //swap items
array [ minimumIndex ] = array [ i ];
array [ i ] = temp;
}
i ++; //goto next item in the array
}
return;
}
/******************************* FUNCTION DEFINITION ******************************
Name : printArray
Parameters :
array a(n) int * ,
numberItems a(n) int
Returns: Void type
Comments:
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
void printArray ( int * array , int numberItems )
{
int i = 0;
cout << endl << endl;
cout << "array : " << endl;
while ( i < numberItems )
{
cout << array [ i ] << " " ;
if ( i != 0 )
if ( i % NUMBERS_PER_LINE == 0 )
cout << endl;
i ++;
}
return;
}
/******************************* FUNCTION DEFINITION ******************************
Name : generateNumbers
Parameters :
numbers a(n) int ,
numberItems a(n) int
Returns: Void type
Comments: Generates an array of random numbers.
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
void generateNumbers ( int * numbers , int numberItems )
{
int i = 0;
srand ( time ( NULL ) );
while ( i < numberItems )
{
numbers [ i ] = rand () % MAX_NUMBERS;
i ++;
}
return;
}
BubbleSort : ( slow sort for small number of items ):
- Code: Select all
/****************************************************************
* File Name : c:\programs\tempCG.cpp
* Date : March,28,2009
* Comments : new project
* Compiler/Assembler : Visual C++ 6.0
* Modifications :
*
* Notes: A good sort for a small number of items. Total run time
* is proportional to the number of items squared ( o ( N^2 ) ).
*
*
* Program Shell Generated At: 11:25:48 a.m.
=-=-=-=-=-=-=-=--=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=*/
#include < iostream >
//#include < string.h >
//#include < conio.h >
//#include < math.h >
//#include < iomanip >
//#include < ctype.h >
#include <stdlib.h>
#include <time.h>
using namespace std;
//>>>>>>>>>>>>>>>>>>>>>>>> GLOBAL DATA <<<<<<<<<<<<<<<<<<<<<<<<<
const int MAX_NUMBERS = 50;
int NUMBERS_PER_LINE = 15;
//<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
//@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ FUNCTION PROTOTYPES @@@@@@@@@@@@@@@@@@@@@@@@@@
void generateNumbers ( int * numbers , int numberItems );
void bubbleSort ( int * array , int numberItems );
void printArray ( int * array , int numberItems );
//##################################################################################
//main function ******************************
int main ( )
{
int array [ MAX_NUMBERS ];
generateNumbers ( array , MAX_NUMBERS );
cout << endl << endl;
cout << "unsorted array " << endl;
printArray ( array , MAX_NUMBERS );
bubbleSort ( array , MAX_NUMBERS );
cout << endl << endl << "sorted array: " << endl;
printArray ( array , MAX_NUMBERS );
cout << endl;
return 0 ;
}
/******************************* FUNCTION DEFINITION ******************************
Name : bubbleSort
Parameters :
array a(n) int * ,
numberItems a(n) int
Returns: Void type
Comments:
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
void bubbleSort ( int * array , int numberItems )
{
int endSortedArray = numberItems - 1;
int lastSwapIndex;
int temp;
while ( endSortedArray > 0 ) //while not at the end of the unsorted array
{
lastSwapIndex = 0; //save index of the last item swapped
int i = 0; //start at the beggining of the unsorted array
while ( i < endSortedArray ) //while not in the sorted items
{
if ( array [ i ] > array [ i + 1 ] ) //if current item is smaller than next , bubble up
{
//swap array [ i ] and array [ i + 1 ]
temp = array [ i ];
array [ i ] = array [ i + 1 ];
array [ i + 1 ] = temp;
lastSwapIndex = i;
}
i ++;
}
endSortedArray = lastSwapIndex; //reset swap boundry
}
return;
}
/******************************* FUNCTION DEFINITION ******************************
Name : printArray
Parameters :
array a(n) int * ,
numberItems a(n) int
Returns: Void type
Comments:
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
void printArray ( int * array , int numberItems )
{
int i = 0;
cout << endl << endl;
cout << "array : " << endl;
while ( i < numberItems )
{
cout << array [ i ] << " " ;
if ( i != 0 )
if ( i % NUMBERS_PER_LINE == 0 )
cout << endl;
i ++;
}
return;
}
/******************************* FUNCTION DEFINITION ******************************
Name : generateNumbers
Parameters :
numbers a(n) int ,
numberItems a(n) int
Returns: Void type
Comments:
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
void generateNumbers ( int * numbers , int numberItems )
{
int i = 0;
srand ( time ( NULL ) );
while ( i < numberItems )
{
numbers [ i ] = rand () % MAX_NUMBERS;
i ++;
}
return;
}
QuickSort: ( fast sort in many cases - although not if data is already sorted )
- Code: Select all
/****************************************************************
* File Name : c:\programs\tempCG.cpp
* Date : January,8,2009
* Comments : new project
* Compiler/Assembler : Visual C++ 6.0
* Modifications :
* Notes: A faster o ( log2 ( N ) ) sorting algorithm.
*
*
*
*
* Program Shell Generated At: 4:55:58 p.m.
=-=-=-=-=-=-=-=--=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=*/
#include < iostream >
//#include < string.h >
//#include < conio.h >
//#include < math.h >
//#include < iomanip >
//#include < ctype.h >
#include <stdlib.h>
#include <time.h>
using namespace std;
//>>>>>>>>>>>>>>>>>>>>>>>> GLOBAL DATA <<<<<<<<<<<<<<<<<<<<<<<<<
const int MAX_NUMBERS = 50;
int NUMBERS_PER_LINE = 15;
//<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
//@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ FUNCTION PROTOTYPES @@@@@@@@@@@@@@@@@@@@@@@@@@
void generateNumbers ( int * numbers , int numberItems );
void quickSort ( int * array , int low , int high );
void printArray ( int * array , int numberItems );
//##################################################################################
//main function ******************************
int main ( )
{
int array [ MAX_NUMBERS ];
generateNumbers ( array , MAX_NUMBERS );
cout << endl << endl;
cout << "unsorted array " << endl;
printArray ( array , MAX_NUMBERS );
quickSort ( array , 0 , MAX_NUMBERS - 1 );
cout << "sorted array: " << endl;
printArray ( array , MAX_NUMBERS );
cout << endl;
return 0 ;
}
/******************************* FUNCTION DEFINITION ******************************
Name : generateNumbers
Parameters :
numbers a(n) int ,
numberItems a(n) int
Returns: Void type
Comments: Generate a random array of numbers
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
void generateNumbers ( int * numbers , int numberItems )
{
int i = 0;
srand ( time ( NULL ) );
while ( i < numberItems )
{
numbers [ i ] = rand () % MAX_NUMBERS;
i ++;
}
return;
}
/******************************* FUNCTION DEFINITION ******************************
Name : quickSort
Parameters :
array a(n) int * ,
low a(n) int ,
high a(n) int
Returns: Void type
Comments:
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
void quickSort ( int * array , int low , int high )
{
if ( high <= low )
return;
int pivot = array [ high ]; //select pivot to be last item in the array
int tempLow = low , tempHigh = high - 1; //partition items between tempHigh and tempLow
int temp;
int lowBound , highBound;
do //partition the array
{ //find items below the pivot
while ( array [ tempLow ] <= pivot && tempLow <= tempHigh )
tempLow ++;
//find items above the pivot
while ( array [ tempHigh ] >= pivot && tempHigh > tempLow )
tempHigh --;
//exchange items that are in the wrong partition
if ( tempLow < tempHigh )
{
temp = array [ tempLow ];
array [ tempLow ] = array [ tempHigh ];
array [ tempHigh ] = temp;
}
}
while ( tempLow < tempHigh ); //while items need to be exchanged between partitions
//exchange overlapping items
temp = array [ tempLow ];
array [ tempLow ] = array [ high ];
array [ high ] = temp;
//sort partitioned segments of the array
quickSort ( array , low , tempLow - 1 );
quickSort ( array , tempLow + 1 , high );
return;
}
/******************************* FUNCTION DEFINITION ******************************
Name : printArray
Parameters :
array a(n) int * ,
numberItems a(n) int
Returns: Void type
Comments:
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
void printArray ( int * array , int numberItems )
{
int i = 0;
cout << endl << endl;
cout << "array : " << endl;
while ( i < numberItems )
{
cout << array [ i ] << " " ;
if ( i != 0 )
if ( i % NUMBERS_PER_LINE == 0 )
cout << endl;
i ++;
}
return;
}
MergeSort ( another faster sort ):
- Code: Select all
/****************************************************************
* File Name : c:\programs\help\mergeSort.cpp
* Date : September,3,2008
* Comments : new project
* Compiler/Assembler :
* Notes: A faster N log N worst case sorting algorithm.
*
*
*
*
* Program Shell Generated At: 6:27:41 p.m.
=-=-=-=-=-=-=-=--=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=*/
#include < iostream >
#include < stdlib.h >
#include < time.h >
//#include < math.h >
//#include < iomanip >
//#include < ctype.h >
#define MAX_NUMBER 50
#define ARRAY_SIZE 20
#define ITEMS_PER_LINE 10
using namespace std;
//@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ FUNCTION PROTOTYPES @@@@@@@@@@@@@@@@@@@@@@@@@@
void mergeSort ( int * array , int * temp , int left , int right );
void mergeSort ( int * array );
void merge ( int * array , int * temp , int left , int right , int rightEnd );
void initialize ( int * array , int size );
//##################################################################################
//main function ******************************
int main ( )
{
int array [ ARRAY_SIZE ];
initialize ( array , ARRAY_SIZE );
int i = 0;
printf ( "unsorted \n" );
while ( i < ARRAY_SIZE )
{
printf ( "%i" , array [ i ] );
printf ( " " );
if ( i % ITEMS_PER_LINE == 0 && i != 0 )
printf ( "\n" );
i ++;
}
printf ( "\nsorted \n" );
mergeSort ( array );
i = 0;
while ( i < ARRAY_SIZE )
{
printf ( "%i" , array [ i ] );
printf ( " " );
if ( i % ITEMS_PER_LINE == 0 && i != 0 )
printf ( "\n" );
i ++;
}
printf ( "\n" );
return 0 ;
}
/******************************* FUNCTION DEFINITION ******************************
Name : mergeSort
Parameters :
array a(n) int * ,
temp a(n) int * ,
left a(n) int ,
right a(n) int
Returns: Void type
Comments:
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
void mergeSort ( int * array , int * temp , int left , int right )
{
if ( left < right ) //merge sort each half of array
{
int center = ( left + right ) / 2;
mergeSort ( array , temp , left , center );
mergeSort ( array , temp , center + 1 , right );
merge ( array , temp , left , center + 1 , right );
}
return;
}
/******************************* FUNCTION DEFINITION ******************************
Name : mergeSort
Parameters :
array a(n) int *
Returns: Void type
Comments: driver function for merge sort. mostly used to
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
void mergeSort ( int * array )
{
int temp [ ARRAY_SIZE ]; //
mergeSort ( array , temp , 0 , ARRAY_SIZE - 1 );
return;
}
/******************************* FUNCTION DEFINITION ******************************
Name : merge
Parameters :
array a(n) int * ,
temp a(n) int * ,
left a(n) int ,
right a(n) int ,
rightEnd ( rightEnd )
Returns: Void type
Comments:
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
void merge ( int * array , int * temp , int left , int right , int rightEnd )
{
int leftEnd = right - 1;
int tempPos = left;
int numberElements = rightEnd - left + 1;
while ( left <= leftEnd && right <= rightEnd )
if ( array [ left ] <= array [ right ] )
temp [ tempPos ++ ] = array [ left ++ ];
else
temp [ tempPos ++ ] = array [ right ++ ];
while ( left <= leftEnd )
temp [ tempPos ++ ] = array [ left ++ ];
while ( right <= rightEnd )
temp [ tempPos ++ ] = array [ right ++ ];
int i = 0;
while ( i < numberElements )
{
array [ rightEnd ] = temp [ rightEnd ] ;
rightEnd --;
i ++;
}
return;
}
/******************************* FUNCTION DEFINITION ******************************
Name : test
Parameters :
array a(n) int * ,
size a(n) int
Returns: Void type
Comments:
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
void initialize ( int * array , int size )
{
srand ( time ( NULL ) );
int i = 0;
while ( i < size )
{
array [ i ] = rand () % MAX_NUMBER;
i ++;
}
return;
}
any questions or algorithm requests , let me know .......