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

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))
{
}
}``````
2
Contributors
1
2
Views
10 Years
Discussion Span
Last Post by Alex Edwards

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

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))
{
}
}

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

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))
{
}
}

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.