summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorGuido van Rossum <guido@python.org>1997-12-10 15:14:24 (GMT)
committerGuido van Rossum <guido@python.org>1997-12-10 15:14:24 (GMT)
commit24e62e2c7ce14562e45d142c266151d99bab9e3e (patch)
tree7fb295817e02568a797f7805797ff2da61e55099
parent3b99430808ce5f8cf844f1ba8b743d8736a2c469 (diff)
downloadcpython-24e62e2c7ce14562e45d142c266151d99bab9e3e.zip
cpython-24e62e2c7ce14562e45d142c266151d99bab9e3e.tar.gz
cpython-24e62e2c7ce14562e45d142c266151d99bab9e3e.tar.bz2
Modified quicksort by Raymund Galvin, after studying the GNU libg++
quicksort. This should be much faster if there are lots of duplicates, and otherwise at least as good.
-rw-r--r--Objects/listobject.c71
1 files changed, 48 insertions, 23 deletions
diff --git a/Objects/listobject.c b/Objects/listobject.c
index c9d4a6b..a5bd038 100644
--- a/Objects/listobject.c
+++ b/Objects/listobject.c
@@ -683,8 +683,10 @@ quicksort(array, size, compare)
/* If it's a small one, use straight insertion sort */
n = hi - lo;
if (n < MINSIZE) {
- if (insertionsort(lo, n, compare) < 0)
- return -1;
+ /*
+ * skip it. The insertion sort at the end will
+ * catch these
+ */
continue;
}
@@ -692,52 +694,64 @@ quicksort(array, size, compare)
l = lo + (n>>1); /* Middle */
r = hi - 1; /* Last */
- k = docompare(*lo, *l, compare);
+
+ k = docompare(*l, *lo, compare);
if (k == CMPERROR)
return -1;
if (k < 0)
{ tmp = *lo; *lo = *l; *l = tmp; }
+
k = docompare(*r, *l, compare);
if (k == CMPERROR)
return -1;
if (k < 0)
{ tmp = *r; *r = *l; *l = tmp; }
- k = docompare(*r, *lo, compare);
+
+ k = docompare(*l, *lo, compare);
if (k == CMPERROR)
return -1;
if (k < 0)
- { tmp = *r; *r = *lo; *lo = tmp; }
- pivot = *lo;
+ { tmp = *l; *l = *lo; *lo = tmp; }
+ pivot = *l;
/* Partition the array */
- l = lo;
- r = hi;
+ l = lo+1;
+ r = hi-2;
for (;;) {
/* Move left index to element > pivot */
- while (++l < hi) {
- k = docompare(*l, pivot, compare);
+ for (;;) {
+ k = docompare(*l, pivot, compare);
if (k == CMPERROR)
return -1;
- if (k > 0)
+ if (k >= 0)
break;
+ l++;
}
/* Move right index to element < pivot */
- while (--r > lo) {
- k = docompare(*r, pivot, compare);
+ for (;;) {
+ k = docompare(pivot, *r, compare);
if (k == CMPERROR)
return -1;
- if (k < 0)
+ if (k >= 0)
break;
+ r--;
}
+
/* If they met, we're through */
- if (r < l)
+ if (l < r) {
+ /* Swap elements and continue */
+ tmp = *l; *l = *r; *r = tmp;
+ l++; r--;
+ }
+ else if (l == r) {
+ l++; r--;
+ break;
+ }
+
+ if (l > r)
break;
- /* Swap elements and continue */
- { tmp = *l; *l = *r; *r = tmp; }
}
- /* Move the pivot into the middle */
- { tmp = *lo; *lo = *r; *r = tmp; }
/* We have now reached the following conditions:
lo <= r < l <= hi
@@ -752,20 +766,20 @@ quicksort(array, size, compare)
n2 = hi - l;
if (n > n2) {
/* First one is bigger */
- if (n > 1) {
+ if (n > MINSIZE) {
lostack[top] = lo;
histack[top++] = r;
- if (n2 > 1) {
+ if (n2 > MINSIZE) {
lostack[top] = l;
histack[top++] = hi;
}
}
} else {
/* Second one is bigger */
- if (n2 > 1) {
+ if (n2 > MINSIZE) {
lostack[top] = l;
histack[top++] = hi;
- if (n > 1) {
+ if (n > MINSIZE) {
lostack[top] = lo;
histack[top++] = r;
}
@@ -774,6 +788,17 @@ quicksort(array, size, compare)
/* Should assert top < STACKSIZE-1 */
}
+
+ /*
+ * Ouch - even if I screwed up the quicksort above, the
+ * insertionsort below will cover up the problem - just a
+ * performance hit would be noticable.
+ */
+
+ /* insertionsort is pretty fast on the partially sorted list */
+
+ if (insertionsort(array, size, compare) < 0)
+ return -1;
/* Succes */
return 0;