Home Forums C Programming Basic Sorting Algorithms

Viewing 0 reply threads
  • Author
    Posts
    • #2184
      GWILouisaxwzkla
      Participant

      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 ):


      /****************************************************************
      * File Name : c:programstempCG.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
      #include

      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 ):



      /****************************************************************
      * File Name : c:programstempCG.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
      #include

      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 )


      /****************************************************************
      * File Name : c:programstempCG.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
      #include

      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 ):



      /****************************************************************
      * File Name : c:programshelpmergeSort.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 …….

Viewing 0 reply threads
  • The forum ‘C Programming’ is closed to new topics and replies.