From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: weis
Received: (from weis@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id IAA06448 for caml-redistribution@pauillac.inria.fr; Mon, 8 Mar 1999 08:58:23 +0100 (MET)
Resent-Message-Id: <199903080758.IAA06448@pauillac.inria.fr>
Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id BAA24503 for <caml-list@pauillac.inria.fr>; Sat, 6 Mar 1999 01:27:32 +0100 (MET)
Received: from miss.wu-wien.ac.at (miss.wu-wien.ac.at [137.208.107.17])
	by nez-perce.inria.fr (8.8.7/8.8.7) with ESMTP id BAA04239
	for <caml-list@inria.fr>; Sat, 6 Mar 1999 01:27:30 +0100 (MET)
Received: (from mottl@localhost)
	by miss.wu-wien.ac.at (8.9.0/8.9.0) id BAA03901
	for caml-list@inria.fr; Sat, 6 Mar 1999 01:27:30 +0100 (MET)
From: Markus Mottl <mottl@miss.wu-wien.ac.at>
Message-Id: <199903060027.BAA03901@miss.wu-wien.ac.at>
Subject: Sort.array easily degenerates
To: caml-list@inria.fr (OCAML)
Date: Sat, 6 Mar 1999 01:27:29 +0100 (MET)
X-Mailer: ELM [version 2.4 PL21]
MIME-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 8bit
Resent-From: weis@pauillac.inria.fr
Resent-Date: Mon, 8 Mar 1999 08:58:23 +0100
Resent-To: caml-redistribution@pauillac.inria.fr

Hello,

I have played around with the new functions and modules in the new
OCAML-release. Besides other things I have tested the new function for
sorting arrays (Sort.array).

I am not sure where the problem in the implementation is, but the
"qsort"-function, which is applied in "Sort.array" degenerates easily
on pre-sorted and/or non-unique data. E.g.:

-----  SNIP -----
let _ =
  let size = 5000 in
  let ar = Array.create size 0 in
  for i = 0 to (size-1) do ar.(i) <- i done;
  Sort.array (>=) ar
-----  SNIP -----

The array to be sorted is initialized with its index. Then it is sorted
with descending order.

Running the same test with larger arrays clearly shows that we encounter
the worst-case behaviour (n^2) of quicksort.

Even worse:

If we initialize the array with the same number, the time complexity
stays at its worst-case but with an even higher constant factor.

Initializing the array with random integers (of a large range) shows
that in such cases "Sort.array" does not perform this badly (actually
quite well).

I have compared this to "qsort" in "stdlib.h", the standard library of
C. It is faster than the OCAML-version, as was to be expected. But in
contrast to OCAML it behaves very nicely on low-entropy data.

E.g.: (C-Code):

-----  SNIP -----
#include <stdlib.h>

int int_comp (const void * a, const void * b) {
  return *(int *) a - *(int *) b;
}

const int size = 5000;

int main () {
  int ar[size];
  for (int i = 0; i < size; ++i) ar[i] = i;
  qsort (ar, size, sizeof(int), int_comp);
}
-----  SNIP -----

It would probably be a good idea to change the implementation of
"Sort.array" so as to make it more unlikely to encounter such worst-case
behaviour. Especially with data, where elements may occur more than once,
the current implementation performs really badly.

So here a question: has someone already written a quicksort-function
with in-place modification for arrays which demonstrates nicer behaviour?

Best regards,
Markus

-- 
Markus Mottl, mottl@miss.wu-wien.ac.at, http://miss.wu-wien.ac.at/~mottl