Public Group

# The Quicksort

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

## Recommended Posts

Hi, I came accros some quicksort code and typed it up in my IDE so I could understand how it works. I added several lines of cout's to track the values of variables as shown below. The five cout lines in the function 'qs' were the ones I added.
#include <iostream>
#include <cstring>

using namespace std;

void quicksort(char *items, int len);

void qs(char *items, int left, int right);

int main() {

char str[] = "axbcdefghijklmnop";

cout << "Original order: " << str << "\n";

quicksort(str, strlen(str));

cout << "Sorted order: " << str << "\n";

for(;;);

return 0;

}

// Set up a call to the actual sorting function.
void quicksort(char *items, int len)
{
qs(items, 0, len-1);
}

// A recursive version of Quicksort for sorting characters.
void qs(char *items, int left, int right)
{
int i, j;
char x, y;

i = left; j = right;
x = items[( left+right) / 2 ];

do {
while((items < x) && (i < right)) i++;
cout << i << "\n" << x << "\n";
while((x < items[j]) && (j > left)) j--;
cout << j << "\n";

if(i <= j) {
y = items;
items = items[j];
items[j] = y;
i++; j--;
}
cout << i << "\n" << x << "\n";
cout << j << "\n";

} while(i <= j);

cout << "\n-----------\n" << items << "\n-----------\n";

if(left < j) qs(items, left, j);
if(i < right) qs(items, i, right);
}


The output of the function before it entered its first recursion with the if statements at the bottom of the function was this: Original order: axbcdefghijklmnop str length 17 1 h 8 2 h 7 8 h 7 8 h 7 --------- ahbc... Heres the promblem and question. In the code in the first and third cout statements I output the variable 'x' which is a pointer to an element in the charachter array, and when output it displays the value of the element it points to. The first time the function is called, x is initialized to point the the 9th element of the charachter array (items[8]). items[8] value is h at the beggining of the function. After the first two while loops on the first run through the do while loop items[8] should have a value of h. Then the program will enter the if. In the case of this program, x and h will swap places. I now thought that the pointer variable x should now when it is cout, display a value of x, because item[8] in the charachter array str now has a value of x. However the valiable pointer x when cout still couts with a value of h. Does this mean that the pointer valiable x has actually changed which element it is pointing to, as h is ,after the point before recursion, the second element of the array. Thanks, hope that all makes sense.

##### Share on other sites
x doesn't point to anything. x is assigned a value.

char x, y;x = items[( left+right) / 2 ];

If x pointed to something, this would be the following:
char *x;x = &items[( left+right) / 2 ];

In this case, x would be a pointer to memory address, which, at time of algorithm running, is the 9th element within the array.

So no, x doesn't change, unless it's specifically assigned new value via "x = ..." statement.

x in this case is value, and i and j are indices (or cursors, or "pointers"). But the only real pointer that the algorithm uses is the pointer to array. Everything else are values.

I hope I understood the problem.

##### Share on other sites
Oh of course, thanks alot, I think I was just confusing all the pointer theory, yeh I thought x was a pointer, great thanks for that, helped alot.

1. 1
2. 2
Rutin
20
3. 3
4. 4
frob
15
5. 5

• 10
• 9
• 14
• 9
• 33
• ### Forum Statistics

• Total Topics
632592
• Total Posts
3007295

×