# C++ Recursion Quick Sort

This topic is 369 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Edit : Maybe this should be in Beginners forum.  Sorry if it should be there.

Hello everyone, we're getting closer to the holidays.  Everyone have a safe happy season.

I'm having trouble with a recursion problem for an : Inside the Quick Sort example.  At the very least, I am having trouble understanding how the right side of the quick sort is done after doing all the left hand subsections.  I understand that the partition function's job is to keep reducing the left-hand subsection.

I am not very good at recursion yet and I am also having trouble mostly with the two quicksort calls in the quicksort function.

I could really use some help.  Thank you,

Josheir

Here is the code:

#include <iostream>
void getdata(int[], int);
void display(int[], int);
void swap(int &, int &);
void partition(int[], int&, int&);
void quicksort(int[], int, int);

//using std;
int main() {

const int max = 10;
int list[max];
getdata(list, max);
std::cout << "initial list\n";
display(list, max);
quicksort(list, 0, max - 1);
std::cout << "sorted list:\n";
display(list, max);

while (1);

return(0);
}

void getdata(int a[], int n)
{

a[0] = 10;
a[1] = 9;
a[2] = 8;
a[3] = 7;
a[4] = 6;
a[5] = 5;
a[6] = 4;
a[7] = 3;
a[8] = 2;
a[9] = 1;

}

void display(int a[], int n)
{

for (int i = 0; i < n; i++)
std::cout << a[i] << "[" << i << "]\t";

std::cout << std::endl;

}
void swap(int &a, int &b)
{
int temp = a; a = b; b = temp;
}

void quicksort(int a[], int left, int right)

{
int l = left, r = right;

partition(a, l, r);

if (left < r)
{

quicksort(a, left, r);

}

if (l < right)
{

quicksort(a, l, right);

}
}
void partition(int a[], int &l, int &r)
{

int pivot = a[l];

while (r > l)
{
while (a[l] < pivot)++l;
while (pivot < a[r])--r;
if (l > r)continue;
swap(a[l], a[r]);
++l; --r;

}

}


Thanks again.

Edited by Josheir

##### Share on other sites

Try walking through a visualization (like https://visualgo.net/en/sorting - click QUI on the top bar to switch to QuickSort).

##### Share on other sites

Thank you ApochPiQ, this is the site I learned from : http://www.algolist.net/Algorithims/Sorting/Quicksort.  The second page (when printed) illustrates the stop partition nicely so that it is easy to understand the left value for the right side partition.

Have happy holidays; Sincerely,

Josheeir

1. 1
Rutin
69
2. 2
3. 3
4. 4
5. 5

• 21
• 10
• 33
• 20
• 9
• ### Forum Statistics

• Total Topics
633430
• Total Posts
3011831
• ### Who's Online (See full list)

There are no registered users currently online

×