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