#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 Quicksort
Author
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.
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.
x doesn't point to anything. x is assigned a value.
If x pointed to something, this would be the following:
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.
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.
Author
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
