Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > quick sort

Reply
Thread Tools

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

}
 
Reply With Quote
 
 
 
 
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
bubblesort, which has fewer overheads.

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

 
Reply With Quote
 
 
 
 
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@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999
 
Reply With Quote
 
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?
 
Reply With Quote
 
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."

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.

--
Eric Sosman
http://www.velocityreviews.com/forums/(E-Mail Removed)lid
 
Reply With Quote
 
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
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
 
Reply With Quote
 
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
 
Reply With Quote
 
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.
 
Reply With Quote
 
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.


 
Reply With Quote
 
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

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
HELP!! anyone ??can help me about my project "quick sort implemented with shell sort? comsciepartner General Computer Support 0 10-06-2008 01:02 PM
Quick Question Quick Answer JKop C++ 11 05-24-2004 09:46 PM
Quick Restore for a Compaq not so quick! Croos Bustamunky Computer Support 2 05-15-2004 04:17 AM
PanasonicBQ390 "quick" charger - How quick? Ol' Bab Digital Photography 1 01-17-2004 06:54 AM
Ado sort error-Ado Sort -Relate, Compute By, or Sort operations cannot be done on column(s) whose key length is unknown or exceeds 10 KB. Navin ASP General 1 09-09-2003 07:16 AM



Advertisments