0

Hello,

My code works but I would like to adjust it to perform better. My teacher would like me to perform quickSort with pointers. I did use them but I was wondering what else I could change to improve the usage of pointers? For instance how can I pass pointers to the partition function?

My code is below:

void Sort::swap(int &value1, int &value2)
{
   int temp = value1;

   value1 = value2;
   value2 = temp;
}


int Sort::partition(int set[], int start, int end)
{
   int currentValue, pivot, mid;

   mid = (start + end) / 2;
   swap(set[start], set[mid]);
   pivot = start;
   currentValue = set[start];
   for (int scan = start + 1; scan <= end; scan++)
   {
      if (set[scan] < currentValue)
      {
         pivot++;
         swap(set[pivot], set[scan]);
      }
   }
   swap(set[start], set[pivot]);
   return pivot;
}


void Sort::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);
   }
}

bool Sort::test()
{
	Sort set; // create object
	bool answer = false;

	cout << "Enter the size of the array: ";
	//cin >> arraySize;
	cout << "50";
	set.arraySize = 50;
	cout << "\nArray being randomly populated with integers.";

	// pointers add/change values in the array indirectly
    int *prt1=new int[set.arraySize];
  
    // randomize the random number generator for the array elements using current time
    srand ( (unsigned)time ( 0 ) );

    //insert random numbers into the array
    for (int i=0; i < set.arraySize; i++)
        *(prt1 + i)= 1 + rand() % 1000;
	
    //print the numbers in the array before sorting
    cout << "\n\nThe integers before sorting are:\n";
    for (int i=0; i < set.arraySize; i++)
        cout << *(prt1 + i) << "\t";

    set.quickSort(prt1, 0, set.arraySize-1);

	 //now print the sorted numbers
    cout << "\n\nThe integers after sorting are: \n";
    for(int i=0; i < set.arraySize; i++)
    cout << *(prt1 + i) << "\t"; 

	// test the values to see if the program was successful
	if(*(prt1 + 1) < *(prt1 + 2))
	{
		answer = true;
	}
	return answer;
}
2
Contributors
1
Reply
2
Views
8 Years
Discussion Span
Last Post by Alex Edwards
0

I'm going to assume you have done tests in the following way--

#include <cstdlib>
#include <iostream>

using namespace std;

struct Sort{
       
       public:
              int arraySize;
              void swap(int&, int&);
              int partition(int[], int, int);
              void quickSort(int[], int, int);
              bool test();
};

void Sort::swap(int &value1, int &value2)
{
   int temp = value1;

   value1 = value2;
   value2 = temp;
}


int Sort::partition(int set[], int start, int end)
{
   int currentValue, pivot, mid;

   mid = (start + end) / 2;
   swap(set[start], set[mid]);
   pivot = start;
   currentValue = set[start];
   for (int scan = start + 1; scan <= end; scan++)
   {
      if (set[scan] < currentValue)
      {
         pivot++;
         swap(set[pivot], set[scan]);
      }
   }
   swap(set[start], set[pivot]);
   return pivot;
}


void Sort::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);
   }
}

bool Sort::test()
{
	Sort set; // create object
	bool answer = false;

	cout << "Enter the size of the array: ";
	//cin >> arraySize;
	cout << "50";
	set.arraySize = 50;
	cout << "\nArray being randomly populated with integers.";

	// pointers add/change values in the array indirectly
    int *prt1=new int[set.arraySize];
  
    // randomize the random number generator for the array elements using current time
    srand ( (unsigned)time ( 0 ) );

    //insert random numbers into the array
    for (int i=0; i < set.arraySize; i++)
        *(prt1 + i)= 1 + rand() % 1000;
	
    //print the numbers in the array before sorting
    cout << "\n\nThe integers before sorting are:\n";
    for (int i=0; i < set.arraySize; i++)
        cout << *(prt1 + i) << "\t";

    set.quickSort(prt1, 0, set.arraySize-1);

	 //now print the sorted numbers
    cout << "\n\nThe integers after sorting are: \n";
    for(int i=0; i < set.arraySize; i++)
    cout << *(prt1 + i) << "\t"; 

	// test the values to see if the program was successful
	if(*(prt1 + 1) < *(prt1 + 2))
	{
		answer = true;
	}
	return answer;
}

int main(int argc, char *argv[])
{
    Sort &refSort = (*new Sort);
    refSort.test();
    
    cin.get();
    return 0;
}

Now it's just a matter of what your teacher wants when he says to "use pointers."

Does he want you to sort pointers? Does he want you to user pointers as arguments? Does he want you to use pointer arithmetic when doing the sorts?

I think this is what he expected you to do. Look at the comments to see if you understand them.

#include <cstdlib>
#include <iostream>

using namespace std;

struct Sort{
       
       public:
              int arraySize;
              void swap(int *value1, int *value2);
              int partition(int *set, int start, int end);
              void quickSort(int *set, int start, int end);
              bool test();
};

void Sort::swap(int *value1, int *value2)
{
   int temp = *value1; // assigning dereferenced value1 to temp

   (*value1) = (*value2); // assigning dereferenced value2 to the value pointer value1 points to
   (*value2) = temp; // assigning the temp value to the value pointer value2 points to, ending the swap
}


int Sort::partition(int *set, int start, int end)
{
   int currentValue, pivot, mid;

   mid = (start + end) / 2;
   swap(&set[start], &set[mid]); // referencing the address of set[start] and set[mid]
   pivot = start;
   currentValue = set[start];
   for (int scan = start + 1; scan <= end; scan++)
   {
      if (set[scan] < currentValue)
      {
         pivot++;
         swap(&set[pivot], &set[scan]); // once again referencing the address of set[start] and set[mid]
      }
   }
   swap(&set[start], &set[pivot]); // nothing special here either
   return pivot;
}


void Sort::quickSort(int *set, int start, int end)
{
   int pivotPoint;

   if (start < end)
   {
      // Get the pivot point.
      pivotPoint = partition(set, start, end); // set is already a pointer so no need to reference
      // Sort the first sub list.
      quickSort(set, start, pivotPoint - 1); // ditto
      // Sort the second sub list.
      quickSort(set, pivotPoint + 1, end); // ditto
   }
}

bool Sort::test()
{
	Sort set; // create object
	bool answer = false;

	cout << "Enter the size of the array: ";
	//cin >> arraySize;
	cout << "50";
	set.arraySize = 50;
	cout << "\nArray being randomly populated with integers.";

	// pointers add/change values in the array indirectly
    int *prt1=new int[set.arraySize];
  
    // randomize the random number generator for the array elements using current time
    srand ( (unsigned)time ( 0 ) );

    //insert random numbers into the array
    for (int i=0; i < set.arraySize; i++)
        *(prt1 + i)= 1 + rand() % 1000;
	
    //print the numbers in the array before sorting
    cout << "\n\nThe integers before sorting are:\n";
    for (int i=0; i < set.arraySize; i++)
        cout << *(prt1 + i) << "\t";

    set.quickSort(prt1, 0, set.arraySize-1);

	 //now print the sorted numbers
    cout << "\n\nThe integers after sorting are: \n";
    for(int i=0; i < set.arraySize; i++)
    cout << *(prt1 + i) << "\t"; 

	// test the values to see if the program was successful
	if(*(prt1 + 1) < *(prt1 + 2))
	{
		answer = true;
	}
	return answer;
}

int main(int argc, char *argv[])
{
    Sort *refSort = new Sort;
    refSort->test();
    delete refSort;
    cin.get();
    return 0;
}

Nothing special was done really - instead of passing by array/reference, the values were passed as "pointers."

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.