trouble with quick sort

This is a discussion on trouble with quick sort within the C++ Programming forums, part of the General Programming Boards category; Here I have code but I am getting 4 errors. When I use the quicksort the 4 errors occur. 1. ...

  1. #1
    Registered User
    Join Date
    Jan 2008
    Posts
    18

    trouble with quick sort

    Here I have code but I am getting 4 errors. When I use the quicksort the 4 errors occur.

    1. stating the 'partition': identifier not found
    2-4. swap: identifier not found

    I have highlighted where these errors are below in red. Below is also Part 1 and Part 2. I have Part 1 finished but when adding quick sort I am having trouble with Part 2.

    Code:
    # include <iostream>
    using std::cout;
    using std::cin;
    
    #include <cstdlib>
    using std::srand;
    using std::rand;
    
    #include <ctime>
    using std::time;
    
    void bubbleSort(int array[], int size)
    {
       bool swap;
       int temp;
    
       do
       {
          swap = false;
          for (int count = 0; count < (size - 1); count++)
          {
             if (array[count] > array[count + 1])
             {
                temp = array[count];
                array[count] = array[count + 1];
                array[count + 1] = temp;
                swap = true;
             }
          }
       } while (swap);
    }
    
    void selectionSort(int array[], int size)
    {
       int startScan, minIndex, minValue;
    
       for (startScan = 0; startScan < (size - 1); startScan++)
       {
          minIndex = startScan;
          minValue = array[startScan];
          for(int index = startScan + 1; index < size; index++)
          {
             if (array[index] < minValue)
             {
                minValue = array[index];
                minIndex = index;
             }
          }
          array[minIndex] = array[startScan];
          array[startScan] = minValue;
       }
    }
    
    //************************************************
    // quickSort uses the quicksort algorithm to     *
    // sort set, from set[start] through set[end].   *
    //************************************************
    
    void quickSort(int set[], int start, int end)
    {
       int pivotPoint;
    
       if (start < end)
       {
          // Get the pivot point.
          pivotPoint = partition(set, start, end);
          // Sort the first sub list.
          quickSort(set, start, pivotPoint - 1);
          // Sort the second sub list.
          quickSort(set, pivotPoint + 1, end);
       }
    }
    
    //**********************************************************
    // partition selects the value in the middle of the        *
    // array set as the pivot. The list is rearranged so       *
    // all the values less than the pivot are on its left      *
    // and all the values greater than pivot are on its right. *
    //**********************************************************
    
    int partition(int set[], int start, int end)
    {
       int pivotValue, pivotIndex, mid;
    
       mid = (start + end) / 2;
       swap(set[start], set[mid]);
       pivotIndex = start;
       pivotValue = set[start];
       for (int scan = start + 1; scan <= end; scan++)
       {
          if (set[scan] < pivotValue)
          {
             pivotIndex++;
             swap(set[pivotIndex], set[scan]);
          }
       }
       swap(set[start], set[pivotIndex]);
       return pivotIndex;
    }
    
    //**********************************************
    // swap simply exchanges the contents of       *
    // value1 and value2.                          *
    //**********************************************
    
    void swap(int &value1, int &value2)
    {
       int temp = value1;
    
       value1 = value2;
       value2 = temp;
    }
    int main()
    {
    	int n;
    	clock_t beg, end;
    
    	// prompt and read numbers into an array
    	cout << "A program that performs bubble sort";
    	cout << "\nEnter array size : ";
    	cin >> n;
    
    	int *prt1=new int[n];
    	int *prt2=new int[n];
    	int *prt3=new int[n];
    
    	// randomize the random number generator using current time
    	srand(time(0));
    
    	//insert numbers into array
    	for (int i=0; i<n; i++)
    		*(prt1 + i)= *(prt2 + i)= *(prt3 + i) = 1 + rand() % 1000;
    
    	//print the numbers
    	cout << "\n\n\tThe numbers before sorting are:\n\t";
    	for (int j=0; j<n; j++)
    		cout << *(prt1 + j) << "\t";
    
    	beg=clock();
    	bubbleSort( prt1, n);
    	end=clock();
    
       //print the sorted numbers
    	cout << "\n\n\tThe numbers after sorting are: \n\t";
    	for(int k=0; k<n; k++)
    		cout << *(prt1 + k) << "\t";	
    
    	cout << "\n\n\tStarting click: " << beg << "\n\tEnding click : " << end;
    	cout << "\n\n\tTime taken Bubble Sort : " << ((end-beg)*1.0) / CLK_TCK << " seconds";
    
    	beg=clock();
    	selectionSort(prt2, n);
    	end=clock();
    
    	cout << "\n\n\tStarting click: " << beg << "\n\tEnding click : " << end;
    	cout << "\n\n\tTime taken Selection Sort : " << ((end-beg)*1.0) / CLK_TCK << "seconds";
    
    	beg=clock();
    	quickSort(prt3, 0, n-1);
    	end=clock();
    
    	cout << "\n\n\tStarting click: " << beg << "\n\tEnding click : " << end;
    	cout << "\n\n\tTime taken Quick Sort : " << ((end-beg)*1.0) / CLK_TCK << "seconds";
    
    
    
    	delete[] prt1;
    	delete[] prt2;
    	delete[] prt3;
    	cout << "\n\n\t";
    	system ("pause");
    
    	return 0;
    }
    Output:

    Part 1

    What size array? 10



    Before Sort:

    42 468 335 501 170 725 479 359 963 465



    After Sort:

    42 170 335 359 465 468 479 501 725 963



    Bubble Sort: 0 seconds



    Part 2

    What size array? 50000



    Bubble Sort: 26.125 seconds



    Selection Sort: 6.391 seconds



    Quick Sort: 0.015 seconds

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Functions must be declared (with at least a prototype, if not defined) before they are used.

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,261
    Just as a person reading down the page sees a call to swap and doesn't yet know what swap does until they read down furthur, a compiler does the same. You need a "forward declaration" of some of your functions.

    Your bubble and selection sorts look pretty good. You could shorten your bubble sort by using your swap function, though you'll have to be careful to name your variable differently to the swap function.

    The partition function seems to be wrong though. There needs to be two loops inside a third loop. The first inner loop iterates along from the start until it finds an item not less than the pivot. The second inner loop iterates back from the end until it finds an item less than the pivot. Then these two items are swapped, and we repeat until the two inner loops catch up to each other.
    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"

  4. #4
    Registered User
    Join Date
    Jan 2008
    Posts
    18
    thankyou...i got it fixed now

  5. #5
    Registered User
    Join Date
    Jul 2003
    Posts
    110
    Quote Originally Posted by iMalc View Post
    The partition function seems to be wrong though. There needs to be two loops inside a third loop. The first inner loop iterates along from the start until it finds an item not less than the pivot. The second inner loop iterates back from the end until it finds an item less than the pivot. Then these two items are swapped, and we repeat until the two inner loops catch up to each other.
    That's how you usually see it, but the partition function here actually works too. It's pretty slick really, because it's so simple.

    The pivot element is actually moved to the beginning of the array, and the scan starts at the following element, but the pivot index is set to the beginning (and that's important). Notice that the pivot index is incremented before the swap. Another way to think of this approach, is just counting how many elements of the array are less than the pivot value, and putting them at 'lower' indices. The final swap simply sets the pivot value to the right place, and the array is ordered like it is supposed to be. I actually like this approach better than the two loops inside another one.

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,261
    Hmm, so it does work; my mistake. Thankyou for pointing this out.
    I can't say I can remember running into it written that way before.
    It more than triples the number of item copying going on which is probably why it is seldom written that way. I can't say it appeals to me.
    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"

  7. #7
    Registered User
    Join Date
    Jul 2003
    Posts
    110
    Exactly. I've just found it much easier to teach and demonstrate than the other way.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 26
    Last Post: 07-05-2010, 10:43 AM
  2. Quick Sort
    By e66n06 in forum C++ Programming
    Replies: 13
    Last Post: 08-21-2007, 08:02 AM
  3. Sorting
    By vasanth in forum A Brief History of Cprogramming.com
    Replies: 12
    Last Post: 11-10-2003, 04:21 PM
  4. Shell, Heap and Quick Sort
    By GaPe in forum C Programming
    Replies: 1
    Last Post: 08-19-2003, 01:04 PM
  5. radix sort and radix exchange sort.
    By whatman in forum C Programming
    Replies: 1
    Last Post: 07-31-2003, 12:24 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21