Sign in to follow this  
Genesiiis

The Quicksort

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[i] < x) && (i < right)) i++; 
	cout << i << "\n" << x << "\n";
    while((x < items[j]) && (j > left)) j--;  
	cout << j << "\n";
  
    if(i <= j) {  
      y = items[i];  
      items[i] = 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 this post


Link to post
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 this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this