visitor (0 QPoints)
  • FR
  • EN
  • NL
  • DE
  • ES
315 experts, 1193 registered users, 1659 questions already answered
European Experts Exchange, the very best site for high-quality IT solutions

New Improved Search!

 


05/10/2011 1h30 : Steve Jobs is dead, the father of Apple ][ is gone, we are all orphaned.

Algorithms :: Sorting :: programming algos(bubblesort,quicksort,insertsort e.t.c)
By: riv9394 U.S.A.  Date: 07/06/2003 00:00:00  English  Points: 80 Status: Answered
Quality : Excellent
hi friends
can some one clarify the differences between different "sorts" and how and where to apply
them.normally i see a series of integers and u r asked to aplly some sort on them.
i wouls really appreciate if some one explains by examples.

many thanks

riv
By: sunnycoder Date: 07/06/2003 23:13:00 English  Type : Comment
It is difficult to explain alla algorithms here cause it will take a lot of time to post

If you click the link below, you will be able to see the animations depicting various sorting algorithm and will give you a very clear picture of the algorithms

<A HREF="http://www.cs.ubc.ca/spider/harrison/Java/">http://www.cs.ubc.ca/spider/harrison/Java/</a>
<A HREF="http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html">http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html</a>


more sorting algorithms
<A HREF="http://www.concentric.net/~ttwang/sort/sort.htm">http://www.concentric.net/~ttwang/sort/sort.htm</a>
By: riv9394 Date: 07/06/2003 23:37:00 English  Type : Comment
thanks coder but ur links refered to programming in algos but as a beginner
i was lookin 4 theory.thanks agin 4 ur effort
By: ifsu Date: 08/06/2003 00:14:00 English  Type : Comment
This is what you need if you want really basic introductory material:
<A HREF="http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/niemann/s_man.htm">http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/niemann/s_man.htm</a>
By: VGR Date: 08/06/2003 22:04:00 English  Type : Answer
well, sorting algorithms are a vast topic, as was already written above.

Anyway, to sort a set of integers, they are not required nor wanted. It's better to use the "instantaneous sort" technique from Vasiljevic

Roughly :
1. a selection algorithm searches the minimum value, puts it in first place, then iterates
O(n²) comparisons + costly memory swaps in O(3(n-1))

-one of those algorithms is the "bubble sort" which, as its name implies, examines sequentially (linearly) each element and "pops up" the element (like a bubble) towards it's place
Example : 4 1 3 2 will produce swaps combinations 4 1 2 3, 1 4 2 3, 1 2 4 3, 1 2 3 4 [end]
O(n²) comparisons + costly elements swaps in O(3n(n-1)/2)

2. an insertion method sorts successively the first elements of the list ("cards player method")
-sequential insert in O(n²) comparisons, + costly insertions in O(n(n+3)/2 -2)
-dichotomic insertion in O(n.Log n) comparisons, + costly insertions in O(n(n+3)/2 -2)

3. QuickSort is a dichotomic sort algorithm, usually recursive
the worst-case comparisons number is O(n²) as usual, with 3(n-1) memory swaps
the mean-case (equiprobability 1/P of the p positions) is in O(n.Log2(n))
the essential is the method to choose the pivot around which are split the two list's halves

Quick Sort is a generalization of selection algorithms

4. Fusion Sort : takes the way around : two recursive calls, then a treatment phase (hence "fusion")
Needs an auxiliary list for intersorting
Worst-case comparisons complexity is O(n.Log2(n)), as is its number of memory transfers (no swaps, direct inserts here)
That's very good

5. Heap Sort
The list is implemented as a binary tree ; general algorithm is :
-1-build heap with the n values
-2-search minimum, put it at the end of newly sorted list (no comparison)
-3-suppress that minimum from the heap and reorganize it (O(Log(n)) comparisons)
-4- loop n times to -2-, until the heap is empty

O(nLog2(n)) comparisons in worst case


6. Instantaneous Sort : no comparisons at all, but a memory (array) initialization phase required [except in PHP or languages like it, where data is initialized by default to 0, amongst other things like garbage collection, etc]

here's a demonstration of it :
<?
// instantaneous sort with no comparisons, no swap...
//
// original concept @1984 D. Vasiljevic in Théoric#3, ORIC Ltd
//
// PHP port by VGR
//

// demo data
//$original=array(1,1,2,3,4,4,5);
$original=array(1,4,4,3,2,5,1); // to demonstrate sorting

// display original data
echo "original unsorted array :
";
for ($i=0;$i<count($original);$i++) echo "element $i : value ".$original[$i].'
';

// instantaneous sort
$result=array(); // considered initialized to zero values
$cMax=10; // maximum expected limit for values' range
for ($i=0;$i<count($original);$i++) $result[$original[$i]]++;

// display results
echo "sorted array is :
";
for ($i=0;$i<=$cMax;$i++) if ($result[$i]>0) for ($j=0;$j<$result[$i];$j++) echo "$i
";

// extra : display only values present (in order, though)
echo "unique values array is :
";
for ($i=0;$i<=$cMax;$i++) if ($result[$i]>0) echo "$i
";
?>
By: spoonman Date: 24/05/2007 14:21:50 English  Type : Comment
Wikipedia has a fantasic page on sorting algorithms. This explains the theory quite clearly and examples of many of the algorithms (in java) can be found here. At the address given in a previous example. These 2 resources and a little experimentation you should give you a good feel for which is most suitable for different sorting tasks.

Do register to be able to answer

©2010 These pages are served without commercial sponsorship. (No popup ads, etc...). Bandwidth abuse increases hosting cost forcing sponsorship or shutdown. This server aggressively defends against automated copying for any reason including offline viewing, duplication, etc... Please respect this requirement and DO NOT RIP THIS SITE.
Please DO link to this page! Post to Twitter Post to Plurk Post to Yahoo Buzz Post to Delicious Post to Digg Post to Facebook Post to MySpace Post to Ping.fm Post to Reddit Post to StumbleUpon

EContact
browser fav
page generated in 303.535940 milliseconds

Why Google AdSense ads ?
compteur
 Ranking-Hits PageRank for this page