# quick sort

Discussion in 'C Programming' started by sophia.agnes@gmail.com, Jan 18, 2008.

1. ### Guest

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);
}

}

, Jan 18, 2008

2. ### Malcolm McLeanGuest

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

Malcolm McLean, Jan 18, 2008

3. ### Richard HeathfieldGuest

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

Richard Heathfield, Jan 18, 2008
4. ### Mark BluemelGuest

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?

Mark Bluemel, Jan 18, 2008
5. ### Eric SosmanGuest

Malcolm McLean wrote:
> <> 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
lid

Eric Sosman, Jan 18, 2008
6. ### peteGuest

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, Jan 18, 2008
7. ### peteGuest

pete wrote:
>
> 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

pete, Jan 18, 2008
8. ### Guest

On Jan 18, 5:46 pm, 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.

, Jan 18, 2008
9. ### osmiumGuest

<> 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.

osmium, Jan 18, 2008
10. ### Malcolm McLeanGuest

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

Malcolm McLean, Jan 18, 2008
11. ### spagliaGuest

On Jan 18, 4:46 am, 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 -

A simple solution is to use a 'random' pivot.
-Steve

spaglia, Jan 18, 2008
12. ### Guest

On Jan 18, 7:52 am, Eric Sosman <> wrote:
>      As a "pure" Quicksort, your function is prone to behave badly
> 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.

Fixing the sort order will not prevent order N stack usage (unless
your compiler does tail recursion elimination in this case). The
usual approach is to recurse on the smaller partition, and then loop
on the larger one.

, Jan 19, 2008
13. ### Dann CorbitGuest

<> wrote in message
news:...
> 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);
> }
>
> }

For the discussion below, imagine that an array of 'n' elements is a line of
boxes lying on its side, like this:

[0][1]....[n-1][n]

Left is towards the nth or last element and right is towards the 0th or
first element.

As far as code quality, I would say it is not a good implementation of
quicksort. Pete explained the right way to do it elsethread (actually, the
_real_ right way is even a bit quirkier, as Pete well knows). At any rate,
for a simple routine like this I would say that it is *ideal* for one
particular purpose:
Understanding, fundamentally, how the sort routine works. You can see at a
glance that it is grabbing an element (the choice of which element is a poor
one, but that is not important for understanding how quicksort works) and
then moving smaller things to the left and larger things to the right. That
gives you two piles now, where you used to have one pile. One pile (the one
on the left) is a pile of little things. And the other pile (the one on the
right) is a pile of little things. You can easily imagine that if we repeat
this procedure on the pile of big things and the pile of little things, that
we will then have 4 ordered piles of big things and little things. Then we
will get 8 piles and then 16 ordered piles (smallest on the left to largest
on the right) and so on. Eventually, these piles will have a size of 1
element each and our data will be sorted.

I would encourage you to try the routine out with some data in a debugger.
(Aside: If you find a bug, then fix it. ) The main thing that you will be
driving for is to understand what is going on. Then, after you understand
it, give it an array full of data that is already correctly ordered. You
will see that it behaves badly. Ask yourself, "How could I make it behave
in a more civilized manner if the data is already in order?" This is a
problem that other people have already worked out, but it will be better for
your understanding to work it out yourself.

IMO-YMMV.

P.S.
Your question is not a C question, but a programming question. So, the next
time you have a puzzle like this one, try it on newsgroup
news:comp.programming. Many of the regulars of this group frequent that one
as well and you will find that a well posed question in a well targeted
questions in the wrong place.

--
Posted via a free Usenet account from http://www.teranews.com

Dann Corbit, Jan 19, 2008
14. ### user923005Guest

On Jan 18, 8:44 pm, "Dann Corbit" <> wrote:
> <> wrote in message
>
> news:...
>
>
>
>
>
> > 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);
> > }

>
> > }

>
> For the discussion below, imagine that an array of 'n' elements is a line of
> boxes lying on its side, like this:
>
> [0][1]....[n-1][n]
>
> Left is towards the nth or last element and right is towards the 0th or
> first element.

Sorry, I'm dyslexic. But I guess you figured out what I meant.
Right is towards the nth or last element and left is towards the 0th
or first element. I hope I have not botched up right or left in the
stuff below because I ahve a time of it with right and left for some
reason. I probably should have stuck with 'bigger' and 'smaller' or
something like that.

> As far as code quality, I would say it is not a good implementation of
> quicksort.  Pete explained the right way to do it elsethread (actually, the
> _real_ right way is even a bit quirkier, as Pete well knows).  At any rate,
> for a simple routine like this I would say that it is *ideal* for one
> particular purpose:
> Understanding, fundamentally, how the sort routine works.  You can see at a
> glance that it is grabbing an element (the choice of which element is a poor
> one, but that is not important for understanding how quicksort works) and
> then moving smaller things to the left and larger things to the right.  That
> gives you two piles now, where you used to have one pile.  One pile (the one
> on the left) is a pile of little things.  And the other pile (the one on the
> right) is a pile of little things.  You can easily imagine that if we repeat
> this procedure on the pile of big things and the pile of little things, that
> we will then have 4 ordered piles of big things and little things.  Then we
> will get 8 piles and then 16 ordered piles (smallest on the left to largest
> on the right) and so on.  Eventually, these piles will have a size of 1
> element each and our data will be sorted.
>
> I would encourage you to try the routine out with some data in a debugger.
> (Aside: If you find a bug, then fix it. ) The main thing that you will be
> driving for is to understand what is going on.  Then, after you understand
> it, give it an array full of data that is already correctly ordered.  You
> will see that it behaves badly.  Ask yourself, "How could I make it behave
> in a more civilized manner if the data is already in order?"  This is a
> problem that other people have already worked out, but it will be better for
> your understanding to work it out yourself.
>
> IMO-YMMV.
>
> P.S.
> Your question is not a C question, but a programming question.  So, the next
> time you have a puzzle like this one, try it on newsgroup
> news:comp.programming.  Many of the regulars of this group frequent that one
> as well and you will find that a well posed question in a well targeted
> newsgroup can elicit well posed answers better than asking the wrong
> questions in the wrong place.
>
> --
> Posted via a free Usenet account fromhttp://www.teranews.com- Hide quoted text -
>
> - Show quoted text -

user923005, Jan 19, 2008
15. ### Dann CorbitGuest

"user923005" <> wrote in message
news:...
On Jan 18, 8:44 pm, "Dann Corbit" <> wrote:
> <> wrote in message
>
> news:...
>
>
>
>
>
> > 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);
> > }

>
> > }

>
> For the discussion below, imagine that an array of 'n' elements is a line
> of
> boxes lying on its side, like this:
>
> [0][1]....[n-1][n]
>
> Left is towards the nth or last element and right is towards the 0th or
> first element.

Sorry, I'm dyslexic. But I guess you figured out what I meant.
Right is towards the nth or last element and left is towards the 0th
or first element. I hope I have not botched up right or left in the
stuff below because I ahve a time of it with right and left for some
reason. I probably should have stuck with 'bigger' and 'smaller' or
something like that.

> As far as code quality, I would say it is not a good implementation of
> quicksort. Pete explained the right way to do it elsethread (actually, the
> _real_ right way is even a bit quirkier, as Pete well knows). At any rate,
> for a simple routine like this I would say that it is *ideal* for one
> particular purpose:
> Understanding, fundamentally, how the sort routine works. You can see at a
> glance that it is grabbing an element (the choice of which element is a
> poor
> one, but that is not important for understanding how quicksort works) and
> then moving smaller things to the left and larger things to the right.
> That
> gives you two piles now, where you used to have one pile. One pile (the
> one
> on the left) is a pile of little things. And the other pile (the one on
> the
> right) is a pile of little things. You can easily imagine that if we
> repeat

AAARG. The pile on the *right* is a pile of *big* things. I just got back
from 4 hours at the dentist, and so I will try to beg for mercy and
sympathy.

> this procedure on the pile of big things and the pile of little things,
> that
> we will then have 4 ordered piles of big things and little things. Then we
> will get 8 piles and then 16 ordered piles (smallest on the left to
> largest
> on the right) and so on. Eventually, these piles will have a size of 1
> element each and our data will be sorted.
>
> I would encourage you to try the routine out with some data in a debugger.
> (Aside: If you find a bug, then fix it. ) The main thing that you will be
> driving for is to understand what is going on. Then, after you understand
> it, give it an array full of data that is already correctly ordered. You
> will see that it behaves badly. Ask yourself, "How could I make it behave
> in a more civilized manner if the data is already in order?" This is a
> problem that other people have already worked out, but it will be better
> for
> your understanding to work it out yourself.
>
> IMO-YMMV.
>
> P.S.
> Your question is not a C question, but a programming question. So, the
> next
> time you have a puzzle like this one, try it on newsgroup
> news:comp.programming. Many of the regulars of this group frequent that
> one
> as well and you will find that a well posed question in a well targeted
> newsgroup can elicit well posed answers better than asking the wrong
> questions in the wrong place.
>
> --
> Posted via a free Usenet account fromhttp://www.teranews.com- Hide quoted
> text -
>
> - Show quoted text -

--
Posted via a free Usenet account from http://www.teranews.com

Dann Corbit, Jan 19, 2008
16. ### Richard BosGuest

"osmium" <> wrote:

> <> 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.

IMO, binary trees are a much better example. You don't _have_ to start
with AA or RB[1]-trees; for studying recursion, unbalanced trees work
fine.

Richard

[1] No relation - R. Bos

Richard Bos, Jan 21, 2008
17. ### Ben BacarisseGuest

(Richard Bos) writes:

> "osmium" <> wrote:
>
>> <> 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.

>
> IMO, binary trees are a much better example. You don't _have_ to start
> with AA or RB[1]-trees; for studying recursion, unbalanced trees work
> fine.

Seconded. However even the simplest trees do require a fair amount of
"boilerplate" code. There are some reasonable numerical examples such
as Euler's GCD algorithm, printing decimals, counting ways to make
change and so on that are natural uses of recursion.

--
Ben.

Ben Bacarisse, Jan 21, 2008