Ancient implementation of qsort. More...

#include "util.h"

Include dependency graph for ucbqsort.c:

Data Structures
struct	info_t
	Miscellaneous information. More...

Macros
#define	THRESH 4
	Threshold for insertion.

#define	MTHRESH 6
	Threshold for median.

Functions
void	util_qsort (void *vbase, int n, int size, QSFP compar)
	Implements the quicksort algorithm. More...

static void	qst (char base, char max, info_t const *info)
	Do a quicksort. More...

Detailed Description

Ancient implementation of qsort.

This is shipped with CUDD so that results of reordering may be more reproducible across different platforms.

qsort.c 4.2 (Berkeley) 3/9/83

Our own version of the system qsort routine which is faster by an average of 25%, with lows and highs of 10% and 50%. The THRESHold below is the insertion sort threshold, and has been adjusted for records of size 48 bytes. The MTHREShold is where we stop finding a better median.

Copyright

Permission is hereby granted, without written agreement and without license or royalty fees, to use, copy, modify, and distribute this software and its documentation for any purpose, provided that the above copyright notice and the following two paragraphs appear in all copies of this software.

IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS ON AN "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.

Copyright

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.

Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.

Neither the name of the University of Colorado nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

Function Documentation

◆ qst()

static void qst	(	char *	base,
		char *	max,
		info_t const *	info
	)

static

Do a quicksort.

First, find the median element, and put that one in the first place as the discriminator. (This "median" is just the median of the first, last and middle elements). (Using this median instead of the first element is a big win). Then, the usual partitioning/swapping, followed by moving the discriminator into the right place. Then, figure out the sizes of the two partions, do the smaller one recursively and the larger one via a repeat of this code. Stopping when there are less than THRESH elements in a partition and cleaning up with an insertion sort (in our caller) is a huge win. All data swaps are done in-line, which is space-losing but time-saving. (And there are only three places where this is done).

◆ util_qsort()

void util_qsort	(	void *	vbase,
		int	n,
		int	size,
		QSFP	compar
	)

Implements the quicksort algorithm.

First, set up some global parameters for qst to share. Then, quicksort with qst(), and then a cleanup insertion sort ourselves. Sound simple? It's not...

Parameters

vbase	start address of array
n	number of items
size	size of each item
compar	comparison function

Data Structures

Macros

Functions

Detailed Description

Function Documentation

◆ qst()

◆ util_qsort()