Quick Sort Partition explain please
I have problem with this quick sort partition implementation, but can not figure it out for a whole day. Please help
Here is the codes:
void swap(int arr[], int a, int b)
{
int temp;
temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
int Partition(int a[], int start, int end)
{
int p = start;
int pivod = a[start];
for(int i = start + 1; i < end; i++)
{
if(pivod > a[i])
{
p++;
swap(a, p, i);
}
}
swap(a, start, p);
return p;
}
I don't understand at p++ before swap function.
for example we have the array with:
{9,5,11,3,2,90,76,18,76,55,43, 10};
----i
p
with the array above, we assigned (i) = start + 1, therefore, (i) will be under number 5, and p = start, therefore p under number 9 (array start 0-11 then p index = 0, I index = 1)
In the first forloop we check pivod = 9 compare to 5 = if(pivod > a[i]) true
then inside of forloop we increase p++ means p now at the same position with i, therefore p move up 1 point, therefore we have this one below:
{9,5,11,3,2,90,76,18,76,55,43, 10};
----i
----p
then we swap these two values. HOW can it be? We swap itself? a[i] = a[p]=> 5 = 5?
That's what I understand. As first I swap first then increase p++ but when ran program will show incorrect answer. This is what I understand but ran incorrect:
if(pivod > a[i])
{
swap(a, p, i);
p++;
}
Thank you very much!
Here is the codes:
void swap(int arr[], int a, int b)
{
int temp;
temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
int Partition(int a[], int start, int end)
{
int p = start;
int pivod = a[start];
for(int i = start + 1; i < end; i++)
{
if(pivod > a[i])
{
p++;
swap(a, p, i);
}
}
swap(a, start, p);
return p;
}
I don't understand at p++ before swap function.
for example we have the array with:
{9,5,11,3,2,90,76,18,76,55,43, 10};
----i
p
with the array above, we assigned (i) = start + 1, therefore, (i) will be under number 5, and p = start, therefore p under number 9 (array start 0-11 then p index = 0, I index = 1)
In the first forloop we check pivod = 9 compare to 5 = if(pivod > a[i]) true
then inside of forloop we increase p++ means p now at the same position with i, therefore p move up 1 point, therefore we have this one below:
{9,5,11,3,2,90,76,18,76,55,43, 10};
----i
----p
then we swap these two values. HOW can it be? We swap itself? a[i] = a[p]=> 5 = 5?
That's what I understand. As first I swap first then increase p++ but when ran program will show incorrect answer. This is what I understand but ran incorrect:
if(pivod > a[i])
{
swap(a, p, i);
p++;
}
Thank you very much!
Last edited on
Topic archived. No new replies allowed.