Velocity Reviews > quick sort

quick sort

sophia.agnes@gmail.com
Guest
Posts: n/a

 01-18-2008
Dear all,

The following is the quick sort function which i have seen in my note
book
how good is this function ?

void sort(int a[], int begin, int end)
{
int pivot,l,r;

if( (end -begin) > 1)
{

pivot = a[begin];
l = begin + 1;
r = end;

while(l < r)
{

if(a[l] <= pivot)
l++;
else
{
r--;
swap(&a[l],&a[r])
}

}

l--;
swap(&a[begin],&a[l]);
sort(a,begin,l);
sort(a,r,end);
}

}

Malcolm McLean
Guest
Posts: n/a

 01-18-2008
<(E-Mail Removed)> wrote in message
> Dear all,
>
> The following is the quick sort function which i have seen in my note
> book
> how good is this function ?
>
> void sort(int a[], int begin, int end)
> {
> int pivot,l,r;
>
> if( (end -begin) > 1)
> {
>
> pivot = a[begin];
> l = begin + 1;
> r = end;
>
> while(l < r)
> {
>
> if(a[l] <= pivot)
> l++;
> else
> {
> r--;
> swap(&a[l],&a[r])
> }
>
> }
>
> l--;
> swap(&a[begin],&a[l]);
> sort(a,begin,l);
> sort(a,r,end);
> }
>
> }
>

It uses element 1 as the pivot, which means that it degenerates into an
O(N^2) algorithm is passed sorted data.
However it is a quicksort, and I cannot see any bugs.
Take a random element as the pivot to fix, some take median of three random
points.
Also when the arrays get very small you can often speed things up by using a

--
Free games and programming goodies.
http://www.personal.leeds.ac.uk/~bgy1mm

Richard Heathfield
Guest
Posts: n/a

 01-18-2008
Malcolm McLean said:

<snip>

> Also when the arrays get very small you can often speed things up by
> using a bubblesort, which has fewer overheads.

Please don't do that! Switching to a Shell sort or an insertion sort is a
much better idea.

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
"Usenet is a strange place" - dmr 29 July 1999

Mark Bluemel
Guest
Posts: n/a

 01-18-2008
Richard Heathfield wrote:
> Malcolm McLean said:
>
> <snip>
>
>> Also when the arrays get very small you can often speed things up by
>> using a bubblesort, which has fewer overheads.

>
> Please don't do that! Switching to a Shell sort or an insertion sort is a
> much better idea.
>

Isn't this whole subject better suited to comp.programming or
alt.sorting.algorithms.discussion?

Eric Sosman
Guest
Posts: n/a

 01-18-2008
Malcolm McLean wrote:
> <(E-Mail Removed)> wrote in message
>> Dear all,
>>
>> The following is the quick sort function which i have seen in my note
>> book
>> how good is this function ?
>> [... code snipped; see up-thread ...]

First, define "good."

choice of which elements to swap. Consider what happens, for
example, if the first part of the array is nicely jumbled but
the latter part contains only large numbers, all larger than
the pivot. Whenever you find a large number near the beginning,
you swap it to the current end, thus bringing a large value
toward the beginning of the array. At the next iteration you
swap that value back to the new endpoint and bring yet another
large value toward the beginning. Roughly speaking, you put
all the large values near the end through a sort of square dance
whose effect is just to move them one place leftward.

The usual scheme is to increment `l' until it reaches an
out-of-position value, then to decrement `r' until it, too,
reaches an out-of-position value, and then to swap those two
values. You don't need all those other swaps; I don't think
they'll hurt the sort's correctness, but they'll burn CPU time
unnecessarily.

on some inputs that would seem easy: an array that's already in
ascending or descending order, for instance. Also, when sort()
calls itself to sort the two pieces, it's a good idea to sort the
shorter piece before the longer; that limits the recursion depth
to the log of the array length, instead of risking trying to make
as many calls as there are elements.

> Also when the arrays get very small you can often speed things up by
> using a bubblesort, which has fewer overheads.

Ick. Bubblesort is not only slower than straight insertion,
but more complicated to boot. The only situation I can think of
where bubblesort might be appropriate is when you have an array
that is known to be "almost sorted," with just a few close-together
elements out of order. That's not the case here; don't use it.

--
Eric Sosman
http://www.velocityreviews.com/forums/(E-Mail Removed)lid

pete
Guest
Posts: n/a

 01-18-2008
(E-Mail Removed) wrote:
>
> Dear all,
>
> The following is the quick sort function which i have seen in my note
> book
> how good is this function ?
>
> void sort(int a[], int begin, int end)
> {
> int pivot,l,r;
>
> if( (end -begin) > 1)
> {
>
> pivot = a[begin];
> l = begin + 1;
> r = end;
>
> while(l < r)
> {
>
> if(a[l] <= pivot)
> l++;
> else
> {
> r--;
> swap(&a[l],&a[r])
> }
>
> }
>
> l--;
> swap(&a[begin],&a[l]);
> sort(a,begin,l);
> sort(a,r,end);
> }
>
> }

It's major problems are when sorting presorted arrays.
The first problem is that it goes quadratic,
that is to say that the running time of the sort quadruples
as the size of the array doubles.
If that happens then there is a problem with excessive
but a large ordered array, could cause a program crash
with a sort like that. It's safer to recurse the smaller
partition and reiterate the larger one.

I also don't like examples of sorting algorithms
where everything is type int.
int pivot,l,r;
It makes it look like (pivot) is more similar to (l) and (r)
in meaning than it really is.
At first glance I thought that (pivot) was the index value
of the pivot element in the array,
but (pivot) is actually a temporary element variable.

I prefer the element_type interface for showing sorting algorithms:

void sort(e_type a[], size_t begin, size_t end)
{
size_t l, r;
e_type pivot;

if (end - begin > 1) {
pivot = a[begin];
l = begin + 1;
r = end;
while (l < r) {
if (GT(&pivot, a + l)) {
l++;
} else {
r--;
swap(a + l, a + r);
}
}
l--;
swap(a + begin, a + l);
sort(a, begin, l);
sort(a, r, end);
}
}

The small partition can be recursed
and the large partition looped, this way:

void sort(e_type a[], size_t begin, size_t end)
{
size_t l, r;
e_type pivot;

while (end - begin > 1) {
pivot = a[begin];
l = begin + 1;
r = end;
while (l < r) {
if (GT(&pivot, a + l)) {
l++;
} else {
r--;
swap(a + l, a + r);
}
}
l--;
swap(a + begin, a + l);
if (end - r > l - begin) {
sort(a, begin, l);
begin = r;
} else {
sort(a, r, end);
end = l;
}
}
}

Here's the rest of the e_type inteface for the sort function:

#define GT(A, B) (*(A) > *(B))
#define E_TYPE int
typedef E_TYPE e_type;

--
pete

pete
Guest
Posts: n/a

 01-18-2008
pete wrote:
>
> (E-Mail Removed) wrote:
> >
> > Dear all,
> >
> > The following is the quick sort function
> > which i have seen in my note book
> > how good is this function ?
> >
> > void sort(int a[], int begin, int end)
> > {
> > int pivot,l,r;
> >
> > if( (end -begin) > 1)
> > {
> >
> > pivot = a[begin];
> > l = begin + 1;
> > r = end;
> >
> > while(l < r)
> > {
> >
> > if(a[l] <= pivot)
> > l++;
> > else
> > {
> > r--;
> > swap(&a[l],&a[r])

and it's missing a defintion for swap and maybe also a semicolon,
depending on just exactly how swap defined.

> > }
> >
> > }
> >
> > l--;
> > swap(&a[begin],&a[l]);
> > sort(a,begin,l);
> > sort(a,r,end);
> > }
> >
> > }

>
> It's major problems are when sorting presorted arrays.

--
pete

smartwhizguy_t@yahoo.com
Guest
Posts: n/a

 01-18-2008
On Jan 18, 5:46*pm, (E-Mail Removed) wrote:
> Dear all,
>
> The following is the quick sort function which i have seen in my note
> book
> how good is this function ?
>
> void sort(int a[], int begin, int end)
> {
> * * int pivot,l,r;
>
> * * if( (end -begin) *> 1)
> * * {
>
> * * * *pivot = a[begin];
> * * * * * * l *= begin + 1;
> * * * * * * r *= end;
>
> * * * * *while(l < r)
> * * * * *{
>
> * * * * * * if(a[l] <= pivot)
> * * * * * * * *l++;
> * * * * * *else
> * * * * * * {
> * * * * * * * * r--;
> * * * * * * * * swap(&a[l],&a[r])
> * * * * * * }
>
> * * * * }
>
> * * * l--;
> * * *swap(&a[begin],&a[l]);
> * * *sort(a,begin,l);
> * * *sort(a,r,end);
>
>
>
> }
> }- Hide quoted text -
>
> - Show quoted text -

i want to become a good programmer but i can failing to understand a
simple program.wat will i do to do so ,please reply as soon as
possible.

osmium
Guest
Posts: n/a

 01-18-2008
<(E-Mail Removed)> wrote:

>i want to become a good programmer but i can failing to understand a
>simple program.wat will i do to do so ,please reply as soon as
>possible.

Recursion is far from simple and Quick Sort uses recursion. Find something
simpler to focus on. If you feel you must master recursion and RIGHT NOW,
find a recursive version of the factorial function. It is usually pointless
and wasteful way to approach the problem, but it can still be a very useful
crutch to learn from.

Malcolm McLean
Guest
Posts: n/a

 01-18-2008

<(E-Mail Removed)> wrote in message

>i want to become a good programmer but i can failing to understand a
>simple program.wat will i do to do so ,please reply as soon as
>possible.
>

Write a program to sort a list of integers. Hardcode the integers, call a
function with this prototype

void sort(int *array, int N)

Then print them out to show that they are sorted.

Use the strategy that occurs to you naturally.

Then write sort2() using a different strategy, and compare running time (you
may have to call the sorts several thousand times, in a loop).

Then look up some canonical sorting algorithms, and you'll be well on the
way to being a competent programmmer.

--
Free games and programming goodies.
http://www.personal.leeds.ac.uk/~bgy1mm