Groups | Search | Server Info | Keyboard shortcuts | Login | Register
Groups > comp.lang.java.programmer > #4012
| From | Joshua Cranmer <Pidgeot18@verizon.invalid> |
|---|---|
| Newsgroups | comp.lang.java.programmer |
| Subject | Re: Did the sort do anything? |
| Date | 2011-05-12 10:40 -0400 |
| Organization | A noiseless patient Spider |
| Message-ID | <iqgrhp$fh7$1@dont-email.me> (permalink) |
| References | <eskis656eeu0of5f5do1ogdpfbdau3d06i@4ax.com> <9303hcFq0nU1@mid.individual.net> |
On 05/11/2011 02:40 PM, Robert Klemme wrote: > Btw, couldn't option 3 be tricky? Depending on the sorting algorithm > things might be moved around but the final order might be the same as > before. Not that this would be desirable but I am pretty sure there are > sorting algorithms which have this property (probably quicksort). The term you are looking for is the stability of the sort. A stable sort preserves the order of equally-compared object; unstable sorts do not. Of the major sorts, heapsort and quicksort are the only sorts which are unstable, although a bad of implementation of any stable sort could be unstable. Wikipedia claims that quicksort can be implemented stably, but that comes at an O(n) space price. Java uses quicksort for primitive types in Arrays.sort and mergesort for reference types: since you can't distinguish two equal primitive types, you can't tell that quicksort isn't stable. -- Beware of bugs in the above code; I have only proved it correct, not tried it. -- Donald E. Knuth
Back to comp.lang.java.programmer | Previous | Next — Previous in thread | Next in thread | Find similar
Did the sort do anything? Roedy Green <see_website@mindprod.com.invalid> - 2011-05-10 08:06 -0700
Re: Did the sort do anything? markspace <-@.> - 2011-05-10 08:48 -0700
Re: Did the sort do anything? Lawrence D'Oliveiro <ldo@geek-central.gen.new_zealand> - 2011-05-14 15:33 +1200
Re: Did the sort do anything? Lew <noone@lewscanon.com> - 2011-05-14 08:56 -0400
Re: Did the sort do anything? Andreas Leitgeb <avl@gamma.logic.tuwien.ac.at> - 2011-05-14 13:54 +0000
Re: Did the sort do anything? Lawrence D'Oliveiro <ldo@geek-central.gen.new_zealand> - 2011-05-15 11:16 +1200
Re: Did the sort do anything? Lew <noone@lewscanon.com> - 2011-05-14 23:24 -0400
Re: Did the sort do anything? Tom Anderson <twic@urchin.earth.li> - 2011-05-15 11:20 +0100
Re: Did the sort do anything? Lew <noone@lewscanon.com> - 2011-05-15 07:00 -0400
Re: Did the sort do anything? Tom Anderson <twic@urchin.earth.li> - 2011-05-15 15:09 +0100
Re: Did the sort do anything? Lawrence D'Oliveiro <ldo@geek-central.gen.new_zealand> - 2011-05-16 14:28 +1200
Re: Did the sort do anything? Joshua Cranmer <Pidgeot18@verizon.invalid> - 2011-05-15 22:38 -0400
Re: Did the sort do anything? Lawrence D'Oliveiro <ldo@geek-central.gen.new_zealand> - 2011-05-16 19:11 +1200
Re: Did the sort do anything? Lew <noone@lewscanon.com> - 2011-05-16 03:47 -0400
Re: Did the sort do anything? markspace <-@.> - 2011-05-16 14:14 -0700
Re: Did the sort do anything? Lew <noone@lewscanon.com> - 2011-05-15 22:40 -0400
Re: Did the sort do anything? Tom Anderson <twic@urchin.earth.li> - 2011-05-16 21:31 +0100
Re: Did the sort do anything? Lawrence D'Oliveiro <ldo@geek-central.gen.new_zealand> - 2011-05-17 09:12 +1200
Re: Did the sort do anything? Lew <noone@lewscanon.com> - 2011-05-16 17:24 -0400
Re: Did the sort do anything? Tom Anderson <twic@urchin.earth.li> - 2011-05-17 13:26 +0100
Re: Did the sort do anything? markspace <-@.> - 2011-05-15 04:56 -0700
Re: Did the sort do anything? Tom Anderson <twic@urchin.earth.li> - 2011-05-15 15:12 +0100
Re: Did the sort do anything? markspace <-@.> - 2011-05-15 07:52 -0700
Re: Did the sort do anything? Michael Wojcik <mwojcik@newsguy.com> - 2011-05-18 11:14 -0400
Re: Did the sort do anything? Lew <noone@lewscanon.com> - 2011-05-18 13:02 -0400
Re: Did the sort do anything? Lawrence D'Oliveiro <ldo@geek-central.gen.new_zealand> - 2011-05-20 18:49 +1200
Re: Did the sort do anything? Robert Klemme <shortcutter@googlemail.com> - 2011-05-20 00:06 -0700
Re: Did the sort do anything? Lawrence D'Oliveiro <ldo@geek-central.gen.new_zealand> - 2011-05-20 22:37 +1200
Re: Did the sort do anything? Lew <noone@lewscanon.com> - 2011-05-20 07:09 -0400
Re: Did the sort do anything? Andreas Leitgeb <avl@gamma.logic.tuwien.ac.at> - 2011-05-10 16:11 +0000
Re: Did the sort do anything? Daniele Futtorovic <da.futt.news@laposte-dot-net.invalid> - 2011-05-10 21:26 +0200
Re: Did the sort do anything? Tom Anderson <twic@urchin.earth.li> - 2011-05-11 21:38 +0100
Re: Did the sort do anything? Daniele Futtorovic <da.futt.news@laposte-dot-net.invalid> - 2011-05-11 23:27 +0200
Re: Did the sort do anything? Roedy Green <see_website@mindprod.com.invalid> - 2011-05-13 07:40 -0700
Re: Did the sort do anything? Spock <spock@starfleet.ufp> - 2011-05-13 16:56 -0400
Re: Did the sort do anything? Lawrence D'Oliveiro <ldo@geek-central.gen.new_zealand> - 2011-05-15 13:58 +1200
Re: Did the sort do anything? Lew <noone@lewscanon.com> - 2011-05-14 23:27 -0400
Re: Did the sort do anything? Robert Klemme <shortcutter@googlemail.com> - 2011-05-11 20:40 +0200
Re: Did the sort do anything? Joshua Cranmer <Pidgeot18@verizon.invalid> - 2011-05-12 10:40 -0400
Re: Did the sort do anything? Robert Klemme <shortcutter@googlemail.com> - 2011-05-13 03:50 -0700
Re: Did the sort do anything? Roedy Green <see_website@mindprod.com.invalid> - 2011-05-13 07:46 -0700
Re: Did the sort do anything? Lawrence D'Oliveiro <ldo@geek-central.gen.new_zealand> - 2011-05-16 14:32 +1200
Re: Did the sort do anything? Patricia Shanahan <pats@acm.org> - 2011-05-15 19:50 -0700
Re: Did the sort do anything? Lawrence D'Oliveiro <ldo@geek-central.gen.new_zealand> - 2011-05-16 17:57 +1200
Re: Did the sort do anything? "javax.swing.JSnarker" <gharriman@boojum.mit.edu> - 2011-05-16 03:35 -0400
Re: Did the sort do anything? Lew <noone@lewscanon.com> - 2011-05-16 03:44 -0400
Re: Did the sort do anything? Patricia Shanahan <pats@acm.org> - 2011-05-16 03:53 -0700
Re: Did the sort do anything? Lawrence D'Oliveiro <ldo@geek-central.gen.new_zealand> - 2011-05-17 00:02 +1200
Re: Did the sort do anything? "javax.swing.JSnarker" <gharriman@boojum.mit.edu> - 2011-05-16 08:05 -0400
Re: Did the sort do anything? Lawrence D'Oliveiro <ldo@geek-central.gen.new_zealand> - 2011-05-17 09:12 +1200
Re: Did the sort do anything? Lew <noone@lewscanon.com> - 2011-05-16 17:32 -0400
Re: Did the sort do anything? thoolen <thoolen@tholenbot.thorium> - 2011-05-16 18:09 -0400
Re: Did the sort do anything? Lew <noone@lewscanon.com> - 2011-05-16 10:02 -0400
Re: Did the sort do anything? Patricia Shanahan <pats@acm.org> - 2011-05-16 07:16 -0700
Re: Did the sort do anything? Lawrence D'Oliveiro <ldo@geek-central.gen.new_zealand> - 2011-05-17 09:11 +1200
Re: Did the sort do anything? Patricia Shanahan <pats@acm.org> - 2011-05-16 15:00 -0700
Re: Did the sort do anything? Lew <noone@lewscanon.com> - 2011-05-16 21:08 -0400
Re: Did the sort do anything? Lawrence D'Oliveiro <ldo@geek-central.gen.new_zealand> - 2011-05-17 19:11 +1200
Re: Did the sort do anything? Patricia Shanahan <pats@acm.org> - 2011-05-17 02:34 -0700
Re: Did the sort do anything? Lew <noone@lewscanon.com> - 2011-05-17 07:19 -0400
[OT] Naming conventions. Was: Re: Did the sort do anything? Patricia Shanahan <pats@acm.org> - 2011-05-17 06:52 -0700
Re: Naming conventions. Was: Re: Did the sort do anything? Robert Klemme <shortcutter@googlemail.com> - 2011-05-18 01:22 -0700
Re: Naming conventions. Was: Re: Did the sort do anything? Patricia Shanahan <pats@acm.org> - 2011-05-18 03:42 -0700
Re: Naming conventions. Was: Re: Did the sort do anything? RedGrittyBrick <RedGrittyBrick@spamweary.invalid> - 2011-05-18 11:53 +0100
Re: Naming conventions. Was: Re: Did the sort do anything? Lew <noone@lewscanon.com> - 2011-05-18 13:07 -0400
Re: Naming conventions. Was: Re: Did the sort do anything? Patricia Shanahan <pats@acm.org> - 2011-05-18 10:37 -0700
Re: Naming conventions. Was: Re: Did the sort do anything? Heike Svensson <hsvensson.1093x1_q@hotmail.nospam.com.please> - 2011-05-19 01:29 -0400
Re: Naming conventions. Was: Re: Did the sort do anything? Robert Klemme <shortcutter@googlemail.com> - 2011-05-19 08:28 +0200
Re: Naming conventions. Was: Re: Did the sort do anything? Lew <noone@lewscanon.com> - 2011-05-19 08:50 -0400
OT: National stereotypes. Was Re: Naming conventions. Was: Re: Did the sort do anything? RedGrittyBrick <RedGrittyBrick@spamweary.invalid> - 2011-05-23 10:25 +0100
Re: OT: National stereotypes. Was Re: Naming conventions. Was: Re: Did the sort do anything? Lew <noone@lewscanon.com> - 2011-05-23 09:05 -0400
Re: OT: National stereotypes. Was Re: Naming conventions. Was: Re: Did the sort do anything? RedGrittyBrick <RedGrittyBrick@spamweary.invalid> - 2011-05-23 17:17 +0100
Re: OT: National stereotypes. Was Re: Naming conventions. Was: Re: Did the sort do anything? Lew <noone@lewscanon.com> - 2011-05-23 14:43 -0400
Re: OT: National stereotypes. Was Re: Naming conventions. Was: Re: Did the sort do anything? Steve Sobol <sjsobol@JustThe.net> - 2011-05-23 08:27 -0700
Re: OT: National stereotypes. Was Re: Naming conventions. Was: Re: Did the sort do anything? RedGrittyBrick <RedGrittyBrick@spamweary.invalid> - 2011-05-23 17:39 +0100
Re: OT: National stereotypes. Was Re: Naming conventions. Was: Re: Did the sort do anything? Robert Klemme <shortcutter@googlemail.com> - 2011-05-23 19:16 +0200
Re: OT: National stereotypes. Was Re: Naming conventions. Was: Re: Did the sort do anything? Lew <noone@lewscanon.com> - 2011-05-23 14:47 -0400
Re: Did the sort do anything? Boojum <boojum42@gmai1.c0m> - 2011-05-18 07:19 -0400
Re: Did the sort do anything? Lawrence D'Oliveiro <ldo@geek-central.gen.new_zealand> - 2011-05-20 18:46 +1200
Re: Did the sort do anything? Lew <noone@lewscanon.com> - 2011-05-20 07:10 -0400
Re: Did the sort do anything? Lew <noone@lewscanon.com> - 2011-05-17 07:16 -0400
Re: Did the sort do anything? Patricia Shanahan <pats@acm.org> - 2011-05-17 06:56 -0700
Re: Did the sort do anything? Lawrence D'Oliveiro <ldo@geek-central.gen.new_zealand> - 2011-05-20 18:46 +1200
Re: Did the sort do anything? Lew <noone@lewscanon.com> - 2011-05-20 07:11 -0400
Re: Did the sort do anything? Patricia Shanahan <pats@acm.org> - 2011-05-20 05:00 -0700
Re: Did the sort do anything? Patricia Shanahan <pats@acm.org> - 2011-05-20 05:20 -0700
Re: Did the sort do anything? Lawrence D'Oliveiro <ldo@geek-central.gen.new_zealand> - 2011-05-21 09:56 +1200
Re: Did the sort do anything? Lew <noone@lewscanon.com> - 2011-05-20 18:12 -0400
Re: Did the sort do anything? Patricia Shanahan <pats@acm.org> - 2011-05-20 21:26 -0700
Re: Did the sort do anything? Gheerax IV <gheerax.4@gmail.invalid> - 2011-05-17 06:58 +0000
Re: Did the sort do anything? Unitary Matrix <umatrix668@gmail.com> - 2011-05-17 00:13 -0700
Re: Did the sort do anything? markspace <-@.> - 2011-05-17 07:41 -0700
Re: Did the sort do anything? Roedy Green <see_website@mindprod.com.invalid> - 2011-05-13 07:42 -0700
Re: Did the sort do anything? Robert Klemme <shortcutter@googlemail.com> - 2011-05-13 21:28 +0200
Re: Did the sort do anything? Tom Anderson <twic@urchin.earth.li> - 2011-05-11 21:32 +0100
csiph-web