Sorting A List

vizskywalker

Mar 7 2005, 05:55 PM

Okay, I'm not looking for code here, just the steps the algorithem would go through. I am trying to find the fastest algorithem to sort a list of elements. So far the fastest I have come up with is as follows (demonstrated on a five element list).
Step List Procedure
0 dbace this is the starting list
1 bdace compare spots 1 and 2, switch if necessary
2 bdace compare spots 5 and 4, switch if necessary
3 adbce compare spots 1 and 3, switch if necessary
4 adbce compare spots 5 and 3, switch if necessary
5 adbce compare spots 1 and 4, switch if necessary
6 adbce compare spots 5 and 2, switch if necessary
7 abdce compare spots 3 and 2, switch if necessary
8 abcde compare spots 3 and 4, switch if necessary
9 abcde compare spots 3 and 2, switch if necessary (this last step is
needed occasionally even though it appears redundant)

If you have a faster method or comments on this one, I'd love to see it. The purpose here is to find an algorithem that can be aplied to any language.

Comment/Reply (w/o sign-up)

qwijibow

Mar 11 2005, 05:01 PM

Looks confusing, the nodes you compare seem random ?
it would be hard and ocnfusing to actually implement that.

Why not use Bubble sort ?

although you are not looking for code, its easyer to explain with code... i hole you understand.

CODE

// sort characters in a string into alphabetical order (must be lovercase)

const int MAX=10;
char array[MAX];

bool chaned=true;

//TODO: Code to fill array with MAX-1 random characters

while(changed) { // (if changed is false, the list is already in order)
changed=false; // reset variable
for(int n=0; n<MAX-1; n++) {

if( array[ n ] > array[ n+1 ]) {
// TODO: swap the 2 characters over
changed = true; (we made a change, so we are not in order)
}
}
}

// String is sorted !

Comment/Reply (w/o sign-up)

vizskywalker

Mar 11 2005, 05:57 PM

The problem with Bubble sort is that it has the potential to take twice as long. If we assume that each step takes up one unit of time, then all of the checks add up and make the time twice as long. I do admit that Bubble sort has the potential to be very fast, and may actually be the best option. I'm still looking for a method with a definite short amount of time. And my method isn't random, it is the same principle as sort spot 1, then spot 2, then spot 3, et.c, except running from both ends at the same time.

Comment/Reply (w/o sign-up)

Dizasta

Apr 5 2005, 08:55 AM

so what happens when the list is already sorted to start with?

Comment/Reply (w/o sign-up)

vizskywalker

Apr 5 2005, 11:27 AM

For Bubble sort it stops early, and for my method, it goes through the steps and just doesn't switch anything. But I took another look at BubbleSort and continued the experimentation with my method, and for large numbers of items, my method quits being as effective, and with a couple modifications done to the assembly code BubbleSort becomes really fast and can take at most about 1.5 times as long instead of 2 times as long.

Comment/Reply (w/o sign-up)

FearfullyMade

Apr 9 2005, 03:28 PM

I would suggest that you look into a sorting algorithm like quicksort. Bubblesort is actually a very slow algorithm, its running time is N^2 (N is the number of elements in the list). The running time for quicksort, on the other hand, is N log N. The only drawback of quicksort is it is a little more complicated to write. Here are the basic steps:

1. Choose one element at random
2. Split remaining elements into two groups as follows:
Compare each remaining element with chosen one
Put smaller elements to left of chosen one
Put larger elements to right of chosen one
3. Repeat step 2 for all subgroups
4. When all groups have one element, they are in ascending order

I'm sure that if search for quicksort on the interent you can find examples of it (and probably a better explaination than the one I gave). I hope this helps.

Comment/Reply (w/o sign-up)

vizskywalker

Apr 10 2005, 09:10 PM

Thanks, I knew bubblesort was slow, but the more I looked at the code the less I could figure out why. Your instructions actually made sense, so I don't think I will have to do an internet search.

~Viz

Comment/Reply (w/o sign-up)

iamrockandroll13

Apr 22 2005, 11:51 PM

QUOTE (FearfullyMade @ Apr 9 2005, 11:28 AM)

Is this basically a binary search based sorting algorithm? if so, that puts it at a running time of O(ln N) which is definately better than O(N^2)

Comment/Reply (w/o sign-up)

FearfullyMade

Apr 23 2005, 04:45 AM

Quicksort does have a lot in common with the binary search algorithim. The basic idea of both is splitting the list in half multiple times.

I can't remember for sure why quicksort is O(N In N) while binary search is O(In N). I believe it has something to do with the fact that with quicksort you have to compare items at each step and then move them around. I don't learn why algorithims like quicksort work like they do until next semester, so that might not be right.

BTW, I noticed in my earlier post I used log in the running time of quicksort. I meant log base 2 when I put log.

Comment/Reply (w/o sign-up)

vizskywalker

Apr 23 2005, 04:53 AM

I figured you meant log base 2, we are after all, essentially dealing with binary. Thanks for all the help with this algorithm, I will probably have another algorithm question soon, os keep your eyes open.

~Viz

Comment/Reply (w/o sign-up)

Latest Entries

evought

May 10 2006, 01:03 AM

qsort or quicksort is already implemented in many languages or their add-on libraries (e.g. C++ STL, Java, Python, Ruby) there is seldom a need to write your own sort method these days unless it is just as a learning exercise.

Note that many of these libraries come with source code if you want to look at how they are done.

Comment/Reply (w/o sign-up)

BitShift

May 10 2006, 12:51 AM

Many programmers consider the quicksort to be the fastest sorting algorithm available.

Technically its not.

There is a sort called the Merge Sort which takes a recursive means of sorting.

Let me give you a comparison. I hope you understand Big O notation, its pretty easy.

Bubble Sort:

Data are in completely random order: O(n^2)
Data are ordereed from lowest to highest: O(n)
Data are ordered from highest to lowest: O(n^2)

Insertion Sort:

Data are in completely random order: O(n log(n))
Data are ordereed from lowest to highest: O(n)
Data are ordered from highest to lowest: O(n log(n))

-I'm not 100% sure that these are the correct Big O runtimes for the Insertion sort.

Quick Sort:

Data are in completely random order: O(n log(n) )
Data are ordereed from lowest to highest: O(n^2)
Data are ordered from highest to lowest: O(n^2)

Merge Sort:

Data are in completely random order: O(n log(n) )
Data are ordereed from lowest to highest: O(n log(n) )
Data are ordered from highest to lowest: O(n log(n) )

As you can see, the Bubble sort is only good, when the list is already sorted. However your not going to sort an already sorted list.

The Quick sort is awesome when the list is random. However, if the list isn't completely random, and is only off by a few elements, it takes longer.

The Merge sort is consistent, providing O(n log(n) )

If you don't know, "n" is the number of elements in the list you are sorting.

People say the Quick Sort and Binary Search are related, because Binary Search uses the same technique and a Binary Search also has O(n log(n) ).

I have no code on the merge sort in any language I just know its there. One of the reasons that the Merge Sort proves to be more effective then the Quick Sort is that the Quick Sort is implemented in such a way to save Memory. The Merge Sort uses a recursive method and therefore, uses a ton of memory.

The Insertion sort looks better then the Merge sort, but I'm not 100% sure that I have the correct Big O runtimes for the insertion sort.

Anyways, I just posted this because I wanted to share information that I had.

Comment/Reply (w/o sign-up)

wykurz

Jul 19 2005, 07:02 PM

i think that in most cases the best choice is to use common library algorithms, like C++ quicksort. it's a very smart modification of insertion sort (much better than bubble sort, because it leaves the same element's in order they were in the beginning) and original quicksort. takes one line to write it.

if you don't want to use libraries, you can easily write insertion sort. works pretty fast with lists up to 50 elements (if larger think about QS).

if sorting integers from a certain range you can use algorithm that would work in O(n) (easy to guess how it works, i hope

)

if you're just interested in theoretical algorythmic aspect of how fast can i sort a list of X elements (where X is constant), than it's quite easy to think out how can you do it with list of up to 6 elements. for a list of 24 elements it took 3 weeks to compute the result with 3 PCs (pentium III 1GHz).

regards

Comment/Reply (w/o sign-up)

mdchurchill

May 27 2005, 10:43 AM

Quicksort is average O(log N) time, but at worst O(N^2) if the data is annoyingly constructed. There are algorithms that run in more consistent log time (e.g. mergesort, heapsort) but there algorithms are much simpler. Well definately in the second case. In the former case (in Haskell notation which is so beautiful I AM introducing these forums to the lovely world of FP):

Merge (x:xs) (y:ys) = if (x < y) then x:Merge(xs, y:ys) else
Merge [] ys = ys
Merge xs [] = xs

MergeSort xs = Merge (Mergesort ys) (MergeSort zs)
where ys = odds xs
zs = evens xs

odds (x:y:xs) = x:odds(xs)
odds [x] = x
odds [] = []

evens (x:y:xs) = y:evens(ys)
evens [y] = []
evens [] = []

Where here x:xs represents x at the front of a list of xs, [] the empty list and [] the singleton list.

(In other words - to sort a list [3,2,4,1] we split into odds and evens - [3,4] and [2,1], then sort these recursively into [3,4] and [1,2] and then Merge them together into [1,2,3,4]. Merge takes to (ordered) lists and produces an (ordered) list by looking at the first element of both (see above.))

Comment/Reply (w/o sign-up)

Sorting A List - Algorithem Search

Sorting A List - Algorithem Search

Latest Entries