While were on this, I'm taking an intro to Data Structures class and were learning all about the different sorting methods ... Insertsort, mergesort etc. What kind of sorting method perl's sort() use?
Sid. -----Original Message----- From: Jeff 'japhy' Pinyan [mailto:[EMAIL PROTECTED]] Sent: Thursday, November 15, 2001 7:39 PM To: [EMAIL PROTECTED] Cc: [EMAIL PROTECTED] Subject: What is "bubble sort"? (Cross-posted to the Perl Beginners List) On Nov 15, Tommy Butler said: >What's a "bubble sort" ? I believe I heard the term used on this list >a while back. I have some kind of idea of what it is, and how it would >be implemented, but I'd like to find out for sure. Could someone tell >me what it is, under what circumstances is it beneficial, what are the >benefits, how it is implemented, and how does it work? Bubble sort is a naive sorting algorithm. It's called "bubble" sort because the larger elements "rise" to the "top" of the list, like a bubble in water. You compare two adjacent items in a list -- if the left is larger than the right, you swap them; if not, do nothing. Then, you move the bubble up one element. You continue this process until you don't need to swap any more. Here is a simple demonstration of the algorithm: LIST = 5 7 3 2 8 4 [5 7] 3 2 8 4 5 [7 3] 2 8 4 5 3 [7 2] 8 4 5 3 2 [7 8] 4 5 3 2 7 [8 4] 5 3 2 7 4 8 That was just ONE pass. In a list of N elements, you will need at most N passes (and that is when the list is in REVERSED order). If the list is already sorted, you only need ONE pass. Here is a Perl implementation of bubble sort. This sorting technique is not very useful anymore, since things like heaps are around. Still, it is one of the first sorting techniques computer science students learn. sub bubble { my $a = shift; my $swap = 1; # did we have to swap? while ($swap) { $swap = 0; # assume we don't have to swap for $i (0 .. @$a - 2) { if ($a->[$i] > $a->[$i+1]) { # if LEFT > RIGHT @$a[$i,$i+1] = @$a[$i+1,$i]; # swap them $swap = 1; # we had a swap } } } } And that's it. -- Jeff "japhy" Pinyan [EMAIL PROTECTED] http://www.pobox.com/~japhy/ RPI Acacia brother #734 http://www.perlmonks.org/ http://www.cpan.org/ ** Look for "Regular Expressions in Perl" published by Manning, in 2002 ** -- To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED] -- To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
