Sorting A List Algorithem Search

[vizskywalker 0]

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 Procedure0 dbace this is the starting list1 bdace compare spots 1 and 2, switch if necessary2 bdace compare spots 5 and 4, switch if necessary3 adbce compare spots 1 and 3, switch if necessary4 adbce compare spots 5 and 3, switch if necessary5 adbce compare spots 1 and 4, switch if necessary6 adbce compare spots 5 and 2, switch if necessary7 abdce compare spots 3 and 2, switch if necessary8 abcde compare spots 3 and 4, switch if necessary9 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.

[qwijibow 0]

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.

// 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 characterswhile(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 !

[vizskywalker 0]

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.

[Dizasta 0]

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

[vizskywalker 0]

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.

[FearfullyMade 0]

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 random2. 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 one3. Repeat step 2 for all subgroups4. When all groups have one element, they are in ascending orderI'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.

[vizskywalker 0]

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

[iamrockandroll13 0]

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.

<{POST_SNAPBACK}>

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)

[FearfullyMade 0]

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.

[vizskywalker 0]

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

[iamrockandroll13 0]

yeah I meant log base 2, I was kind of out of it when I posted

[mdchurchill 0]

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 = ysMerge xs [] = xsMergeSort xs = Merge (Mergesort ys) (MergeSort zs) where ys = odds xs zs = evens xsodds (x:y:xs) = x:odds(xs)odds [x] = xodds [] = []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.))

[wykurz 0]

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

[BitShift 0]

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.

Edited May 10, 2006 by BitShift (see edit history)

[evought 0]

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.