trouble with quick sort

[dukebdx12]

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.

# 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

[tabstop]

Functions must be declared (with at least a prototype, if not defined) before they are used.

[iMalc]

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.

[dukebdx12]

thankyou...i got it fixed now

[whoie]

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.

[iMalc]

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.

[whoie]

Exactly. I've just found it much easier to teach and demonstrate than the other way.