## C and C++

Moderators: None (Apply to moderate this forum)
Number of posts: 94611

This Forum Only

Quick Sort Posted by nitin_747 on 2 Aug 2005 at 4:24 PM
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
Re: Quick Sort Posted by stober on 3 Aug 2005 at 4:21 AM
: 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.
j is a parameter, so it was initialized by the calling function, which was not shown in your post.
: 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
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
```: swap (&v[0], left, (left + right)/2; /*Move partition element to v[0]*/
```

Re: Quick Sort Posted by piccolor44 on 7 Aug 2005 at 4:01 PM
: 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].

## Recent Jobs

Official Programmer's Heaven Blogs
Web Hosting | Browser and Social Games | Gadgets

Popular resources on Programmersheaven.com
Assembly | Basic | C | C# | C++ | Delphi | Flash | Java | JavaScript | Pascal | Perl | PHP | Python | Ruby | Visual Basic