Thread: Help with Sorting algorithms

  1. #1
    Registered User
    Join Date
    Nov 2012
    Posts
    10

    Help with Sorting algorithms

    i need to combine insertion, bubble, quick, merge, and shell sort into one program in a menu style so i can compare them, and so that i can choose which algorithm to use. i have the menu set up but i need help with adding the algorithms into the menu. they all are supposed to sort the same list (50 numbers) and say how many steps they took.

    insert
    Code:
     
    #include <iostream>
    #include <time.h>
    #include <cstdlib>
    using namespace std;
    const int INSERTION =1, BUBBLE = 2, QUICK = 3, MERGE = 4, SHELL = 5, QUIT = 6;
    void menu(int &option);
    
    
    int main()
    {
    	int choice;
    	menu(choice);
    	while(choice != QUIT)
    	{
    
    
    		if (choice == INSERTION)
    		{
    		
    		}// close INSERTION if
    		
    		if (choice == BUBBLE)
    		{
    		
    		}// close BUBBLE if
    		
    		if (choice == QUICK)
    		{
    		
    		}// close QUICK if
    		
    		if (choice == MERGE)
    		{
    		
    		}// close MERGE if
    		
    		if (choice == SHELL)
    		{
    		
    		}// close SHELL if
    		
    	}//close while
    } //close int
    
    
    void InsertionSort( apvector <int> &num)
    {
         int i, j, key, numLength = num.length( );
         for(j = 1; j < numLength; j++)    // Start with 1 (not 0)
        {
               key = num[j];
               for(i = j - 1; (i >= 0) && (num[i] < key); i--)   // Smaller values move up
              {
                     num[i+1] = num[i];
              }
             num[i+1] = key;    //Put key into its proper location
         }
         return;
    }
    
    
    void BubbleSort(apvector <int> &num)
    {
          int i, j, flag = 1;    // set flag to 1 to start first pass
          int temp;             // holding variable
          int numLength = num.length( ); 
          for(i = 1; (i <= numLength) && flag; i++)
         {
              flag = 0;
              for (j=0; j < (numLength -1); j++)
             {
                   if (num[j+1] > num[j])      // ascending order simply changes to <
                  { 
                        temp = num[j];             // swap elements
                        num[j] = num[j+1];
                        num[j+1] = temp;
                        flag = 1;               // indicates that a swap occurred.
                   }
              }
         }
         return;   //arrays are passed to functions by address; nothing is returned
    }
    
    
    void QuickSort(apvector <int> &num, int top, int bottom)
    {
          // top = subscript of beginning of array
          // bottom = subscript of end of array
          
         int middle;
         if (top < bottom)
        {
              middle = partition(num, top, bottom);
              quicksort(num, top, middle);   // sort first section
              quicksort(num, middle+1, bottom);    // sort second section
         }
         return;
    }
    
    
    
    
    //Function to determine the partitions
    // partitions the array and returns the middle subscript
    int partition(apvector <int> &array, int top, int bottom)
    {
         int x = array[top];
         int i = top - 1;
         int j = bottom + 1;
         int temp;
         do
         {
               do      
               {
                      j - -;
               }while (x >array[j]);
    
    
              do  
             {
                     i++;
              } while (x <array[i]);
    
    
              if (i < j)
             { 
                     temp = array[i];    
                     array[i] = array[j];
                     array[j] = temp;
             }
         }while (i < j);     
         return j;           // returns middle subscript  
    }
    
    
    void MergeSort(apvector <int> &arrayA, apvector <int> &arrayB, apvector <int> &arrayC)
    {
         int indexA = 0;     // initialize variables for the subscripts
         int indexB = 0;
         int indexC = 0;
    
    
         while((indexA < arrayA.length( )) && (indexB < arrayB.length( ))
         {
              if (arrayA[indexA] < arrayB[indexB])
              {
                     arrayC[indexC] = arrayA[indexA];
                     indexA++;    //increase the subscript
              }
             else
             {
                     arrayC[indexC] = arrayB[indexB];
                     indexB++;      //increase the subscript
             }
            indexC++;      //move to the next position in the new array
         }
         // Move remaining elements to end of new array when one merging array is empty
         while (indexA < arrayA.length( ))
         {
               arrayC[indexC] = arrayA[indexA];
               indexA++;
               indexC++;
         }
         while (indexB < arrayB.length( ))
         {
               arrayC[indexC] = arrayB[indexB];
               indexB++;
               indexC++;
         }
         return;
    }
    
    
    void ShellSort( apvector <int> &num)
    {
         int i, temp, flag = 1, numLength = num.length( );
         int d = numLength;
         while( flag || (d > 1))      // boolean flag (true when not equal to 0)
         {
              flag = 0;           // reset flag to 0 to check for future swaps
              d = (d+1) / 2;
              for (i = 0; i < (numLength - d); i++)
            {
                   if (num[i + d] > num[i])
                  {
                          temp = num[i + d];      // swap positions i+d and i
                          num[i + d] = num[i];
                          num[i] = temp;
                          flag = 1;                  // tells swap has occurred
                  }
             }
         }
         return;
    }
    
    
    void menu(int &option)
    {
    	cout << "1 INSERTION" << endl;
    	cout << "2 BUBBLE" << endl;
    	cout << "3 QUICK" << endl;
    	cout << "4 MERGE" << endl;
    	cout << "5 SHELL" << endl;
    	cout << "Choose your algorithm" << endl;
    	cin >> option;
    }

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Okay, I can see that you have several things still to do, but you haven't said which part you want help with.

    How about we start with the compile errors? I can see some obvious problems with the QuickSort method. Can you please post the compile errors you are getting?
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  3. #3
    Registered User
    Join Date
    Nov 2012
    Posts
    10
    There are no compile errors yet, since i have not compiled it yet. What i am needing is an array of around 50 numbers, and with calling the functions which start at line 46 in order to sort said array.

  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    So how did you test your existing sort functions to begin with?

    > There are no compile errors yet, since i have not compiled it yet
    Ah, now it's clear - yet another copy/paste merchant -> Arrays in C++ - Quick Sort


    If you want constant random numbers, call srand(0) before you start calling rand()
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Question about sorting algorithms
    By lios1984 in forum C Programming
    Replies: 4
    Last Post: 01-16-2012, 12:03 AM
  2. Sorting algorithms
    By ToNy_ in forum C Programming
    Replies: 9
    Last Post: 12-14-2011, 10:27 AM
  3. Sorting Algorithms
    By ashir30000 in forum C++ Programming
    Replies: 9
    Last Post: 05-21-2009, 09:27 AM
  4. Sorting Algorithms with Time
    By silicon in forum C++ Programming
    Replies: 3
    Last Post: 05-03-2005, 11:27 AM
  5. recommendations on sorting algorithms
    By btq in forum C++ Programming
    Replies: 4
    Last Post: 10-14-2002, 11:36 AM