quick sort

[sophia.agnes]

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]

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
bubblesort, which has fewer overheads.

 

[Richard Heathfield]

Malcolm McLean said:

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.

 

[Mark Bluemel]

Malcolm McLean said:



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]

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

One peculiarity that stands out about this version is its
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.

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.

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.

 

[pete]

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
depth of recursion. The standard doesn't say much about this,
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]

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.

 

[smartwhizguy_t]

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]

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]

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.

 

[spaglia]

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

 

[robertwessel2]

     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.

 

[Dann Corbit]

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

 

[user923005]

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.

 

[Dann Corbit]

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.

 

[Richard Bos]

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

 

[Ben Bacarisse]

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.