Groups > comp.arch.embedded > #19011

Re: validity of ... reasons for preferring C over C++

From	glen herrmannsfeldt <gah@ugcs.caltech.edu>
Newsgroups	comp.arch.embedded
Subject	Re: validity of ... reasons for preferring C over C++
Date	2014-10-31 08:45 +0000
Organization	Aioe.org NNTP Server
Message-ID	<m2vi72$8g3$1@speranza.aioe.org> (permalink)
References	(6 earlier) <m2nhhu$god$1@dont-email.me> <1vlv4atj2266ehd1281g9j899ia6q19b78@4ax.com> <43125adf3vif04dabja4m8fo9vlifcf23s@4ax.com> <m2rhtp$ju1$1@speranza.aioe.org> <pan.2014.10.31.07.32.14.520000@nowhere.invalid>

Show all headers | View raw

Nobody <nobody@nowhere.invalid> wrote:

(snip, I wrote)
>> (Good quicksort doesn't use a fixed array element as the pivot for a
>> partition, but maybe the median of three elemennts.  That pretty much
>> avoids the O(N**2) worst case.)

> Not really. It just cuts the number of steps in half: rather than the
> worst case consistently choosing the highest/lowest element as the
> partition, the worst case consistently chooses the second highest/lowest
> element.

OK, if you don't like it use the random pivot selector.

The problem with original quicksort wasn't that the worst case was
so bad, but that it was so common. 

Note that the worst case for you is that all the air molecules 
randomly move to the side of the room you are not sitting in.
Thermodynamics doesn't say that it is impossible, only that it
is unlikely.

As someone noted, in some cases a worst case can be supplied
by a malicious user. For large N, not likely if you use a random
pivot selector and the user can't guess the seed.

-- glen

Thread

validity of ... reasons for preferring C over C++ Nobody <nobody@nowhere.invalid> - 2014-10-17 00:00 +0100
  Re: validity of ... reasons for preferring C over C++ Wouter van Ooijen <wouter@voti.nl> - 2014-10-17 07:38 +0200
  Re: validity of ... reasons for preferring C over C++ David Brown <david.brown@hesbynett.no> - 2014-10-17 09:27 +0200
    Re: validity of ... reasons for preferring C over C++ Tom Gardner <spamjunk@blueyonder.co.uk> - 2014-10-17 09:29 +0100
      Re: validity of ... reasons for preferring C over C++ David Brown <david.brown@hesbynett.no> - 2014-10-17 11:19 +0200
        Re: validity of ... reasons for preferring C over C++ Paul Rubin <no.email@nospam.invalid> - 2014-10-17 02:35 -0700
          Re: validity of ... reasons for preferring C over C++ Arlet Ottens <usenet+5@c-scape.nl> - 2014-10-17 11:43 +0200
            Re: validity of ... reasons for preferring C over C++ Tom Gardner <spamjunk@blueyonder.co.uk> - 2014-10-17 12:12 +0100
              Re: validity of ... reasons for preferring C over C++ Arlet Ottens <usenet+5@c-scape.nl> - 2014-10-17 13:25 +0200
                Re: validity of ... reasons for preferring C over C++ Tom Gardner <spamjunk@blueyonder.co.uk> - 2014-10-17 12:40 +0100
            Re: validity of ... reasons for preferring C over C++ Niklas Holsti <niklas.holsti@tidorum.invalid> - 2014-10-17 20:12 +0300
              Re: validity of ... reasons for preferring C over C++ Rob Gaddi <rgaddi@technologyhighland.invalid> - 2014-10-17 10:18 -0700
                Re: validity of ... reasons for preferring C over C++ upsidedown@downunder.com - 2014-10-17 21:53 +0300
                Re: validity of ... reasons for preferring C over C++ Niklas Holsti <niklas.holsti@tidorum.invalid> - 2014-10-17 22:59 +0300
                Re: validity of ... reasons for preferring C over C++ Paul Rubin <no.email@nospam.invalid> - 2014-10-17 13:23 -0700
                Re: validity of ... reasons for preferring C over C++ Jacob Sparre Andersen <jacob@jacob-sparre.dk> - 2014-10-18 17:46 +0200
                Re: validity of ... reasons for preferring C over C++ Paul Rubin <no.email@nospam.invalid> - 2014-10-18 11:45 -0700
                Re: validity of ... reasons for preferring C over C++ Niklas Holsti <niklas.holsti@tidorum.invalid> - 2014-10-19 01:51 +0300
                Re: validity of ... reasons for preferring C over C++ Jacob Sparre Andersen <jacob@jacob-sparre.dk> - 2014-10-19 12:43 +0200
                Re: validity of ... reasons for preferring C over C++ Jacob Sparre Andersen <jacob@jacob-sparre.dk> - 2014-10-18 17:44 +0200
          Re: validity of ... reasons for preferring C over C++ David Brown <david.brown@hesbynett.no> - 2014-10-17 12:44 +0200
            Re: validity of ... reasons for preferring C over C++ Tom Gardner <spamjunk@blueyonder.co.uk> - 2014-10-17 12:13 +0100
            Re: validity of ... reasons for preferring C over C++ Niklas Holsti <niklas.holsti@tidorum.invalid> - 2014-10-17 20:15 +0300
              Re: validity of ... reasons for preferring C over C++ Arlet Ottens <usenet+5@c-scape.nl> - 2014-10-17 19:18 +0200
              Re: validity of ... reasons for preferring C over C++ David Brown <david.brown@hesbynett.no> - 2014-10-17 23:03 +0200
                Re: validity of ... reasons for preferring C over C++ Paul Rubin <no.email@nospam.invalid> - 2014-10-17 14:11 -0700
                Re: validity of ... reasons for preferring C over C++ David Brown <david.brown@hesbynett.no> - 2014-10-18 20:14 +0200
                Re: validity of ... reasons for preferring C over C++ Tom Gardner <spamjunk@blueyonder.co.uk> - 2014-10-18 22:15 +0100
                Re: validity of ... reasons for preferring C over C++ glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-10-18 23:07 +0000
                Re: validity of ... reasons for preferring C over C++ Tom Gardner <spamjunk@blueyonder.co.uk> - 2014-10-19 00:36 +0100
                Re: validity of ... reasons for preferring C over C++ Niklas Holsti <niklas.holsti@tidorum.invalid> - 2014-10-19 10:55 +0300
                Re: validity of ... reasons for preferring C over C++ Tom Gardner <spamjunk@blueyonder.co.uk> - 2014-10-19 09:33 +0100
                Re: validity of ... reasons for preferring C over C++ "Boudewijn Dijkstra" <sp4mtr4p.boudewijn@indes.com> - 2014-10-20 15:04 +0200
                Re: validity of ... reasons for preferring C over C++ David Brown <david.brown@hesbynett.no> - 2014-10-19 13:32 +0200
                Re: validity of ... reasons for preferring C over C++ Wouter van Ooijen <wouter@voti.nl> - 2014-10-17 23:44 +0200
                Re: validity of ... reasons for preferring C over C++ David Brown <david.brown@hesbynett.no> - 2014-10-18 20:10 +0200
                Re: validity of ... reasons for preferring C over C++ Niklas Holsti <niklas.holsti@tidorum.invalid> - 2014-10-18 23:38 +0300
                Re: validity of ... reasons for preferring C over C++ Tom Gardner <spamjunk@blueyonder.co.uk> - 2014-10-18 22:21 +0100
                Re: validity of ... reasons for preferring C over C++ Niklas Holsti <niklas.holsti@tidorum.invalid> - 2014-10-19 10:43 +0300
                Re: validity of ... reasons for preferring C over C++ Simon Clubley <clubley@remove_me.eisner.decus.org-Earth.UFP> - 2014-10-19 09:38 +0000
                Re: validity of ... reasons for preferring C over C++ David Brown <david.brown@hesbynett.no> - 2014-10-19 14:07 +0200
                Re: validity of ... reasons for preferring C over C++ Paul Rubin <no.email@nospam.invalid> - 2014-10-19 19:47 -0700
                Re: validity of ... reasons for preferring C over C++ Niklas Holsti <niklas.holsti@tidorum.invalid> - 2014-10-20 06:55 +0300
                Re: validity of ... reasons for preferring C over C++ Paul Rubin <no.email@nospam.invalid> - 2014-10-19 21:02 -0700
                Re: validity of ... reasons for preferring C over C++ britt.snodgrass@gmail.com - 2014-10-20 04:02 -0700
                Re: validity of ... reasons for preferring C over C++ Niklas Holsti <niklas.holsti@tidorum.invalid> - 2014-10-20 18:51 +0300
                C and Ada, was: Re: validity of ... reasons for preferring C over C++ Simon Clubley <clubley@remove_me.eisner.decus.org-Earth.UFP> - 2014-10-21 00:30 +0000
                Re: C and Ada, was: Re: validity of ... reasons for preferring C over C++ Les Cargill <lcargill99@comcast.com> - 2014-10-20 20:49 -0500
                Re: C and Ada, was: Re: validity of ... reasons for preferring C over C++ Jacob Sparre Andersen <jacob@jacob-sparre.dk> - 2014-10-21 09:11 +0200
                Re: C and Ada, was: Re: validity of ... reasons for preferring C over C++ Les Cargill <lcargill99@comcast.com> - 2014-10-21 08:34 -0500
                Re: validity of ... reasons for preferring C over C++ Niklas Holsti <niklas.holsti@tidorum.invalid> - 2014-10-19 21:23 +0300
                Re: validity of ... reasons for preferring C over C++ Nobody <nobody@nowhere.invalid> - 2014-10-20 03:39 +0100
          Re: validity of ... reasons for preferring C over C++ Tom Gardner <spamjunk@blueyonder.co.uk> - 2014-10-17 12:07 +0100
        Re: validity of ... reasons for preferring C over C++ Tom Gardner <spamjunk@blueyonder.co.uk> - 2014-10-17 12:06 +0100
          Re: validity of ... reasons for preferring C over C++ David Brown <david.brown@hesbynett.no> - 2014-10-17 14:12 +0200
            Re: validity of ... reasons for preferring C over C++ Tom Gardner <spamjunk@blueyonder.co.uk> - 2014-10-17 13:16 +0100
          Re: validity of ... reasons for preferring C over C++ Stef <stef33d@yahooI-N-V-A-L-I-D.com.invalid> - 2014-10-17 14:13 +0200
            Re: validity of ... reasons for preferring C over C++ Arlet Ottens <usenet+5@c-scape.nl> - 2014-10-17 14:35 +0200
              Re: validity of ... reasons for preferring C over C++ Tom Gardner <spamjunk@blueyonder.co.uk> - 2014-10-17 13:59 +0100
            Re: validity of ... reasons for preferring C over C++ Wouter van Ooijen <wouter@voti.nl> - 2014-10-17 17:06 +0200
            Re: validity of ... reasons for preferring C over C++ upsidedown@downunder.com - 2014-10-17 19:41 +0300
      Re: validity of ... reasons for preferring C over C++ Clifford Heath <no.spam@please.net> - 2014-10-18 10:14 +1100
        Re: validity of ... reasons for preferring C over C++ Tom Gardner <spamjunk@blueyonder.co.uk> - 2014-10-18 00:36 +0100
          Re: validity of ... reasons for preferring C over C++ Clifford Heath <no.spam@please.net> - 2014-10-20 09:45 +1100
        Re: validity of ... reasons for preferring C over C++ Niklas Holsti <niklas.holsti@tidorum.invalid> - 2014-10-18 08:52 +0300
          Re: validity of ... reasons for preferring C over C++ Tom Gardner <spamjunk@blueyonder.co.uk> - 2014-10-18 09:41 +0100
  Re: validity of ... reasons for preferring C over C++ Dave Nadler <drn@nadler.com> - 2014-10-20 09:46 -0700
    Re: validity of ... reasons for preferring C over C++ Paul Rubin <no.email@nospam.invalid> - 2014-10-20 16:26 -0700
      Re: validity of ... reasons for preferring C over C++ Dave Nadler <drn@nadler.com> - 2014-10-20 16:42 -0700
        Re: validity of ... reasons for preferring C over C++ Paul Rubin <no.email@nospam.invalid> - 2014-10-20 17:24 -0700
          Re: validity of ... reasons for preferring C over C++ John Devereux <john@devereux.me.uk> - 2014-10-21 19:09 +0100
            Re: validity of ... reasons for preferring C over C++ Wouter van Ooijen <wouter@voti.nl> - 2014-10-24 16:38 +0200
          Re: validity of ... reasons for preferring C over C++ Dave Nadler <drn@nadler.com> - 2014-10-21 15:12 -0700
            Re: validity of ... reasons for preferring C over C++ Paul Rubin <no.email@nospam.invalid> - 2014-10-21 16:39 -0700
              Re: validity of ... reasons for preferring C over C++ Nobody <nobody@nowhere.invalid> - 2014-10-22 01:43 +0100
              Re: validity of ... reasons for preferring C over C++ Hans-Bernhard Bröker <HBBroeker@t-online.de> - 2014-10-22 20:00 +0200
          Re: validity of ... reasons for preferring C over C++ Stefan Reuther <stefan.news@arcor.de> - 2014-10-22 18:49 +0200
      Re: validity of ... reasons for preferring C over C++ Dave Nadler <drn@nadler.com> - 2014-10-21 15:15 -0700
      Re: validity of ... reasons for preferring C over C++ Dave Nadler <drn@nadler.com> - 2014-10-22 04:45 -0700
        Re: validity of ... reasons for preferring C over C++ Paul Rubin <no.email@nospam.invalid> - 2014-10-22 09:30 -0700
          Re: validity of ... reasons for preferring C over C++ Dave Nadler <drn@nadler.com> - 2014-10-23 12:25 -0700
            Re: validity of ... reasons for preferring C over C++ Paul Rubin <no.email@nospam.invalid> - 2014-10-23 15:17 -0700
              Re: validity of ... reasons for preferring C over C++ glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-10-23 22:59 +0000
                Re: validity of ... reasons for preferring C over C++ Paul Rubin <no.email@nospam.invalid> - 2014-10-23 16:02 -0700
              Re: validity of ... reasons for preferring C over C++ Dave Nadler <drn@nadler.com> - 2014-10-27 08:30 -0700
                Re: validity of ... reasons for preferring C over C++ Paul Rubin <no.email@nospam.invalid> - 2014-10-27 09:00 -0700
                Re: validity of ... reasons for preferring C over C++ Dave Nadler <drn@nadler.com> - 2014-10-27 09:24 -0700
                Re: validity of ... reasons for preferring C over C++ Paul Rubin <no.email@nospam.invalid> - 2014-10-27 09:30 -0700
                Re: validity of ... reasons for preferring C over C++ glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-10-28 00:52 +0000
              Re: validity of ... reasons for preferring C over C++ David Brown <david.brown@hesbynett.no> - 2014-10-28 08:45 +0100
                Re: validity of ... reasons for preferring C over C++ Paul Rubin <no.email@nospam.invalid> - 2014-10-28 02:00 -0700
                Re: validity of ... reasons for preferring C over C++ George Neuner <gneuner2@comcast.net> - 2014-10-30 11:56 -0400
                Re: validity of ... reasons for preferring C over C++ upsidedown@downunder.com - 2014-10-28 19:59 +0200
                Re: validity of ... reasons for preferring C over C++ David Brown <david.brown@hesbynett.no> - 2014-10-28 23:46 +0100
                Re: validity of ... reasons for preferring C over C++ upsidedown@downunder.com - 2014-10-29 07:27 +0200
                Re: validity of ... reasons for preferring C over C++ David Brown <david.brown@hesbynett.no> - 2014-10-29 10:11 +0100
                Re: validity of ... reasons for preferring C over C++ Robert Wessel <robertwessel2@yahoo.com> - 2014-10-29 10:21 -0500
                Re: validity of ... reasons for preferring C over C++ glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-10-29 20:15 +0000
                Re: validity of ... reasons for preferring C over C++ Robert Wessel <robertwessel2@yahoo.com> - 2014-10-30 11:33 -0500
                Re: validity of ... reasons for preferring C over C++ glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-10-30 19:07 +0000
                Re: validity of ... reasons for preferring C over C++ Robert Wessel <robertwessel2@yahoo.com> - 2014-10-30 16:19 -0500
                Re: validity of ... reasons for preferring C over C++ Nobody <nobody@nowhere.invalid> - 2014-10-31 07:32 +0000
                Re: validity of ... reasons for preferring C over C++ glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-10-31 08:45 +0000
                Re: validity of ... reasons for preferring C over C++ Reinhardt Behm <rbehm@hushmail.com> - 2014-10-31 18:15 +0800
                Re: validity of ... reasons for preferring C over C++ glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-10-31 22:03 +0000
                Re: validity of ... reasons for preferring C over C++ Robert Wessel <robertwessel2@yahoo.com> - 2014-10-31 09:53 -0500
                Re: validity of ... reasons for preferring C over C++ glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-10-31 22:17 +0000
                Re: validity of ... reasons for preferring C over C++ Les Cargill <lcargill99@comcast.com> - 2014-10-31 17:50 -0500
            Re: validity of ... reasons for preferring C over C++ Nobody <nobody@nowhere.invalid> - 2014-10-28 04:37 +0000
    Re: validity of ... reasons for preferring C over C++ Stefan Reuther <stefan.news@arcor.de> - 2014-10-21 19:12 +0200
      Re: validity of ... reasons for preferring C over C++ Dave Nadler <drn@nadler.com> - 2014-10-21 15:06 -0700
        Re: validity of ... reasons for preferring C over C++ Stefan Reuther <stefan.news@arcor.de> - 2014-10-22 19:06 +0200

csiph-web