Jump to content
  • Advertisement
Sign in to follow this  
Genesiiis

The Quicksort

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

If you intended to correct an error in the post then please contact us.

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


Link to post
Share on other sites
Advertisement
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
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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!