Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories

Welcome to the new platform of Programmer's Heaven! We apologize for the inconvenience caused, if you visited us from a broken link of the previous version. The main reason to move to a new platform is to provide more effective and collaborative experience to you all. Please feel free to experience the new platform and use its exciting features. Contact us for any issue that you need to get clarified. We are more than happy to help you.

Quick Sort

nitin_747nitin_747 Posts: 8Member
Hi there,
I was having a small problem in understanding the command swap
Plz look at this quick sort program
It uses the middle element of each subarray for partitioning

/* qsort : sort v[left]...v[right] into increasing order*/
void qsort (int v[], int left, int right)

{
int i, last;
void swap(int v[], int i, int j);

if (left >= right) /*do nothing if array contains fewer than 2 elements*/
return;
swap (v, left, (left + right)/2; /*Move partition element to v[0]*/
last = left;
for (i = left + 1; i <= right; i++) /*partition*/
if (v[i] < v[left])
swap (v, ++last,i); /* Shouldn't it be v[]*/
swap (v,left,last); /* restore partition element*/

qsort(v, left,last-1);

qsort(v, last + 1, right);

}


O.K..this program is from page #87 of the Ernighan and Ritchie book for 'C' programming
WHat I am wondering is what is the term 'j' in the program. It has never been initialized.
and secondly could any one tell me what does v and v[] mean in context with the above program.
I mean v is an array i.e. v[], so how could it simply be used as 'v'.
while being used in the swap command.
What does the swap(v,++last ,i); mean exactly
Thanks
Nitin

Comments

  • stoberstober Posts: 9,765Member ✭✭✭
    : Hi there,
    : I was having a small problem in understanding the command swap
    : Plz look at this quick sort program
    : It uses the middle element of each subarray for partitioning
    :
    [code]
    : /* qsort : sort v[left]...v[right] into increasing order*/
    : void qsort (int v[], int left, int right)
    :
    : {
    : int i, last;
    : void swap(int v[], int i, int j);
    :
    : if (left >= right) /*do nothing if array contains fewer than 2 elements*/
    : return;
    : swap (v, left, (left + right)/2; /*Move partition element to v[0]*/
    : last = left;
    : for (i = left + 1; i <= right; i++) /*partition*/
    : if (v[i] < v[left])
    : swap (v, ++last,i); /* Shouldn't it be v[]*/
    : swap (v,left,last); /* restore partition element*/
    :
    : qsort(v, left,last-1);
    :
    : qsort(v, last + 1, right);
    :
    : }
    [/code]:
    :
    : O.K..this program is from page #87 of the Ernighan and Ritchie book for 'C' programming
    : WHat I am wondering is what is the term 'j' in the program. It has never been initialized.
    [blue]j is a parameter, so it was initialized by the calling function, which was not shown in your post.[/blue]
    : and secondly could any one tell me what does v and v[] mean in context with the above program.
    : I mean v is an array i.e. v[], so how could it simply be used as 'v'.
    : while being used in the swap command.
    : What does the swap(v,++last ,i); mean exactly
    [blue]when you want to pass an array all you need to do is put the name of the array in the parameter list as illustrated in the call to the swap function. that line could also have been written like this
    [code]
    : swap ([red]&v[0][/red], left, (left + right)/2; /*Move partition element to v[0]*/
    [/code]
  • piccolor44piccolor44 Posts: 2Member
    : Hi there,
    : I was having a small problem in understanding the command swap
    : Plz look at this quick sort program
    : It uses the middle element of each subarray for partitioning
    :
    : /* qsort : sort v[left]...v[right] into increasing order*/
    : void qsort (int v[], int left, int right)
    :
    : {
    : int i, last;
    : void swap(int v[], int i, int j);
    :
    : if (left >= right) /*do nothing if array contains fewer than 2 elements*/
    : return;
    : swap (v, left, (left + right)/2; /*Move partition element to v[0]*/
    : last = left;
    : for (i = left + 1; i <= right; i++) /*partition*/
    : if (v[i] < v[left])
    : swap (v, ++last,i); /* Shouldn't it be v[]*/
    : swap (v,left,last); /* restore partition element*/
    :
    : qsort(v, left,last-1);
    :
    : qsort(v, last + 1, right);
    :
    : }
    :
    :
    : O.K..this program is from page #87 of the Ernighan and Ritchie book for 'C' programming
    : WHat I am wondering is what is the term 'j' in the program. It has never been initialized.
    : and secondly could any one tell me what does v and v[] mean in context with the above program.
    : I mean v is an array i.e. v[], so how could it simply be used as 'v'.
    : while being used in the swap command.
    : What does the swap(v,++last ,i); mean exactly
    : Thanks
    : Nitin
    :

    Swapping means to exchange the content in v[i] and v[j]. Of course, the function swap() should be defined. In your code here, swap should be defined outside the quicksort function. Note that 'i' in quicksort() is not the same 'i' in swap(). 'i' and 'j' in swap() will be initialize when you call swap() and pass arguments.


    When you use 'v' by itself, you are refering to the starting address of the array. You can also get the starting address of the array using &v[0], but just sending v produces the same result. You use v[] in a declaration or when you access an element, for example, v[1].


Sign In or Register to comment.