Efficient yet simple sorting algorithms

[Sir Fredrick]

As some of you know (thanks to my thread about typos), I recently had to develop an algorithm in C++ to sort a vector. The only sorting algorithm I could remember from data structures was bubblesort, which is horribly inefficient. I know that quicksort is pretty good, but I couldn't remember how it works, so I sort of just made up my own. It seems to be pretty good, when sorting 64 elements, it makes 66 recursive calls (the worst-case and best-case are the same). For my purposes, that's good enough, but what are some better sorting algorithms that aren't too complicated? Any links to good online explanations of them would be cool too.

 

[littleprince]

64 recursive calls that go through your vector?
so n+2 squared

how bout a merge sort?
i'm sure a google search would help
nlogn by the way

 

[Executor]

mergesort is good. Isnt there a binary sort too?

 

[Sir Fredrick]

Why squared? The vector is size 64, the function was executed 67 times (if you count the first one), so isn't that just n+3?
I never took analysis of algorithms

 

[Sir Fredrick]

Here's what I did:
select a pivot point (an element in the middle), move everything smaller than that value to the left, everything larger than it to the right, break that in half, and call the same function recursively on the left and right sides.

 

[Executor]

sir fred, thats binary sort btw.

 

[CSoup]

<< Here's what I did:
select a pivot point (an element in the middle), move everything smaller than that value to the left, everything larger than it to the right, break that in half, and call the same function recursively on the left and right sides. >>



That gives you an implementation of the quicksort algorithm.
Best and average case running time is O(n log n)
Worst case running time is O(n^2)

Most implementations of quicksort stop after the partitions are of some small size (like 10) and does insertion sort from their because of this bad behavior on mostly sorted lists.

Oh, and by the way, O(n log n) average case is the best that a classical sort algorithm can do.

 

[Sir Fredrick]

lol so is it binary sort or quicksort? Or are they one in the same?

 

[hwstock]

<< As some of you know (thanks to my thread about typos), I recently had to develop an algorithm in C++ to sort a vector. The only sorting algorithm I could remember from data structures was bubblesort, which is horribly inefficient. I know that quicksort is pretty good, but I couldn't remember how it works, so I sort of just made up my own. It seems to be pretty good, when sorting 64 elements, it makes 66 recursive calls (the worst-case and best-case are the same). For my purposes, that's good enough, but what are some better sorting algorithms that aren't too complicated? Any links to good online explanations of them would be cool too. >>



For small sorts, bubblesort isn't bad. You don't have to remember much about quicksort -- it is part of the standard C library. You merely need supply (quicksort) a pointer to a function that compares two of the items to be sorted.

 

[CyberZenn]

ive never heard of a quicksort, but in this sort of situation i believe binary sorts are the fastest. O(log n) if i recall correctly - its hard to get a more effecient alg. than that, and if you manage to find one you can probably be inducted into the computer science hall of fame. or something.

 

[ThisIsMatt]

bleah

 

[CSoup]

here is a page that explains quicksort with an animation. It does not do a running time analysis though, but the analysis of quicksort is interesting because its worst case and average case differ so much.

 

[CSoup]

Are you sure the best case number of recursive calls is 66? Your description of the algorithm seems to indicate a best case number of recursions of O(log n). This is if the pivot chosen is very near the middle.

 

[Sir Fredrick]

<< Are you sure the best case number of recursive calls is 66? Your description of the algorithm seems to indicate a best case number of recursions of O(log n). This is if the pivot chosen is very near the middle. >>



Well since I don't check to see if the list is sorted at any given point, I should have about the same number of recursive calls no matter what, right? I could be wrong, I'll verify on monday...

 

[breakit23]

Are you in AP comp science? I had the same assignment.

Their are a bunch of sorts you can do: Shell sort, merge sort, Insert sort, or select Sort. You can search for them online or just check sn

 

[lebe0024]

Quicksort is VERY simple and VERY fast. Java uses quicksort for their "javasort()" function.

Complexity:

Worst: O(n^2).

Average: either (n lg n) or Theta(n lg n), I can't remember.

 

[lebe0024]

Merge sort would be fastest, but an array can't be sorted within itself, it needs other arrays as storage. Quick sort is the fastest, with Heapsort coming in a close second. You don't want to use heapsort though, it's incredibly complicated.

 

[Sir Fredrick]

Ok, I just did a best-case on paper, and I get 63 calls, including the original. That's pretty close to 66.

Here's what I did, each line is another recursive call:

1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64

1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32
33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64

1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16
17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32
33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48
49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64

1,2,3,4,5,6,7,8
9,10,11,12,13,14,15,16
17,18,19,20,21,22,23,24
25,26,27,28,29,30,31,32
33,34,35,36,37,38,39,40
41,42,43,44,45,46,47,48
49,50,51,52,53,54,55,56
57,58,59,60,61,62,63,64

1,2,3,4
5,6,7,8
9,10,11,12
13,14,15,16
17,18,19,20
21,22,23,24
25,26,27,28
29,30,31,32
33,34,35,36
37,38,39,40
41,42,43,44
45,46,47,48
49,50,51,52
53,54,55,56
57,58,59,60
61,62,63,64


1,2
3,4
5,6
7,8
9,10
11,12
13,14
15,16
17,18
19,20
21,22
23,24
25,26
27,28
29,30
31,32
33,34
35,36
37,38
39,40
41,42
43,44
45,46
47,48
49,50
51,52
53,54
55,56
57,58
59,60
61,62
63,64

 

[ProviaFan]

Here is a helpful page I found some time ago while searching for information on the same topic.

Sorting

 

[charrison]

umm..you can let c++ do all the heavy lifting.
Include <algorythms> and write the compare function then you can

sort(vector.begin(),vector.end(),sortfunction);

almost too easy

 

[GtPrOjEcTX]

didn't read the thread so you might have what you need already but heres the web page from a class I took last semester

Sorting performance
Sorting Descriptions

 

[Mucman]

Here is a visual demo of many different sorting algorithms! They also have the java code for them too.

sort demos

 

[Sir Fredrick]

<< umm..you can let c++ do all the heavy lifting.
Include <algorythms> and write the compare function then you can

sort(vector.begin(),vector.end(),sortfunction);

almost too easy >>



Sounds too good to be true. I'll have to look into that. Thanks.

Some of those other references look good too, I'm going to bookmark this stuff in case I need it at a later date, rather than trying to reinvent the wheel every time.

 

[charrison]

example STL sort

enjoy!

 

[CSoup]

<<

<< Are you sure the best case number of recursive calls is 66? Your description of the algorithm seems to indicate a best case number of recursions of O(log n). This is if the pivot chosen is very near the middle. >>



Well since I don't check to see if the list is sorted at any given point, I should have about the same number of recursive calls no matter what, right? I could be wrong, I'll verify on monday... >>



Opps, I actually meant that the best and average case number of levels of recursions should be O(log n). This would happen in the case you show where you are splitting perfectly in the middle each time.

Normally if you run quicksort on the list you gave the performance will be really horrible since when it splits, it will normally put 1 item in the first half and the rest in the second half. This is because the basic implementation just takes the first number as the pivot. The reason for this is that it works well normally and runs faster then if you try to find the true median every time. Other modifications are to randomly pick a pivot, to take first, last, and middle elements from the list and average them, etc. People usually never find the true median like you are doing. In any case, yes, the number of recursions is about the same in all cases, but the level of recurions in worse case is O(n) and in best case is O(log n). Running time analysis is a little more complex than looking at the number of recursions because another factor is how much work you are doing in each recursion. If you want a more in-depth analysis of quicksort and other sorting algoritms, look in Introduction to Algorithms 1st ed by Cormem, Leiserson, and Rivest.