Date: Thu, 21 Apr 2016 06:18:09 +1000 From: Peter Jeremy <peter@rulingia.com> To: Hans Petter Selasky <hps@selasky.org> Cc: FreeBSD Current <freebsd-current@freebsd.org> Subject: Re: qsort() documentation Message-ID: <20160420201809.GA46988@server.rulingia.com> In-Reply-To: <5717256C.5080805@selasky.org> References: <5714C86A.8050204@selasky.org> <alpine.BSF.2.20.1604181250450.68720@wonkity.com> <20160419113430.69e41a0b@fujitsu> <alpine.BSF.2.20.1604192002111.59174@wonkity.com> <5717256C.5080805@selasky.org>
next in thread | previous in thread | raw e-mail | index | archive | help
--cWoXeonUoKmBZSoM Content-Type: text/plain; charset=iso-8859-1 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable On 2016-Apr-20 08:45:00 +0200, Hans Petter Selasky <hps@selasky.org> wrote: >There is something which I don't understand. Why is quicksort falling=20 >back to insertion sort which is an O(N**2) algorithm, when there exist a= =20 >O(log(N)*log(N)*N) algorithms, which I propose as a solution to the=20 >"bad" characteristics of qsort. O() notation just describes the (normally, worst case) ratio of input size to runtime for a given algorithm: Increasing the input size by (say) 100=D7 means an insertion sort will take about 10000=D7 as long to run, whilst the "best" algorithms would take about 2000=D7 as long. It says nothing about = how fast sorting (say) 1000 items takes with either sort or how they behave on "typical" inputs. In general, the fancier algorithms might have better worst-case O() numbers but they have higher overheads and may not perform any better on typical inputs - so, for small inputs, insertion sort or bubble sort may be faster. IMO: - If you're only sorting a small number of items and/or doing it infrequent= ly, the sort performance doesn't really matter and you can use any algorithm. - If you're sorting lots of items and sort performance is a real issue, you need to examine the performance of a variety of algorithms on your input data and may need to roll your own implementation. As long as qsort() behaves reasonably and its behaviour is documented sufficiently well that someone can decide whether or not to rule it out for their specific application, that is (IMHO) sufficient. --=20 Peter Jeremy --cWoXeonUoKmBZSoM Content-Type: application/pgp-signature; name="signature.asc" -----BEGIN PGP SIGNATURE----- Version: GnuPG v2 iQJ8BAEBCgBmBQJXF+QBXxSAAAAAAC4AKGlzc3Vlci1mcHJAbm90YXRpb25zLm9w ZW5wZ3AuZmlmdGhob3JzZW1hbi5uZXRFRUIyOTg2QzMwNjcxRTc0RTY1QzIyN0Ux NkE1OTdBMEU0QTIwQjM0AAoJEBall6Dkogs0S/0P/0ZJGxcT1MXsZ6toqSKXfjcJ Sh+ZXRx/OMP/kiF2MI575njiY9KNtUOz52DTTBQAuw7yJR/mnHaqujdvnSOuzFHq k+mv+0RPb7gDBlMp4TxS177xKF0h6Tnlg4MBWpmLtvb4ZpZR/byRx+LvwvYS+Fff GU4Fa3eQKKzlAyFHt3Fgd8+zJH+SLAMCgJvZX3v3KZajK20NEKsi1I6eyV3lN2VI vpVmECDMEueTEBx5H2vlNEgzKYM/yOmvMtBuB80d6ps5UBiV/ASz87AOR69eN/6M YaVaKxt4HUGGSoWsR741Ng2gDw2ET0GdXWri3lwkgL4YZVo63Pa+krqkyQ2uWVvD l6ylZSZb0z2oIwZhfdxzb5eoLtJBwRYz/etxAWZHb6gwDDmoxbXHSJPyeARqWBzP jlXON6Q3qTNHfa6X4VnV0Ax/Wwa1fG7kcHDBDm8ikg/y6+nHGYVxH/7BMautQsTG nmztkEE4nxc1Me8gdhYc3kd9PYbWpVzrQGpBrdieYJuT/AML4bWATRxPeCkHUOnR MdPiuvh/d53G8w3f+mACJ/pK8fAXT0XXxMaxOsHc+ddLjOUEQURrlVQtS3ujDZxY qs+ROXB96C0HjuXLr4Zkc3mmqpkXeQnjlHSZcon2UJ1BFEzdP3o25+10XCRtD6n7 K5OPAtxMGK+1o7DV5oeo =/9mq -----END PGP SIGNATURE----- --cWoXeonUoKmBZSoM--
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20160420201809.GA46988>