Ταξινόμηση με διαμερισμό και αντιμετάθεση

Στην ταξινόμηση με διαμερισμό (partition exchange sort) (ή γρήγορη ταξινόμηση (quick sort)) επιλέγεται ένα στοιχείο του πίνακα και τα υπόλοιπα στοιχεία μοιράζονται σε δύο υποπίνακες ανάλογα με τη σχέση τους με το στοιχείο αυτό.
Στη συνέχεια ο αλγόριθμος καλείται αναδρομικά για τους δύο υποπίνακες.

Η βιβλιοθήκη της C υλοποιεί τον αλγόριθμο αυτό στη συνάρτηση qsort:

#include <stdlib.h>

void qsort(void *base, size_t num, size_t width, int (*compare)(const void *elem1, const void *elem2));

Η συνάρτηση ταξινομεί έναν πίνακα δεδομένων με βάση μια συνάρτηση σύγκρισης.
Η συνάρτηση έχει τις παρακάτω παραμέτρους:

base
Δείκτης στην αρχή του πίνακα των δεδομένων που πρέπει να ταξινομηθούν.
num
Αριθμός των δεδομένων που πρέπει να ταξινομηθούν.
width
Το μέγεθος κάθε στοιχείου του πίνακα (π.χ. sizeof(int), sizeof(struct s_elem *)).
compare
Δείκτης σε συνάρτηση που συγκρίνει δύο στοιχεία με βάση δείκτες σε αυτά. Η συνάρτηση compare πρέπει να επιστρέφει τις παρακάτω τιμές:

< 0
αν το elem1 < elem2,
0
αν το elem1 == elem2 και
> 0
αν το elem1 > elem2.

Παράδειγμα

Το παρακάτω παράδειγμα ταξινομεί το πίνακα ακεραίων ivals και τυπώνει το αποτέλεσμα:

#include <stdlib.h>
#include <stdio.h>

/*
 * Integer compare function (passed to qsort)
 */
static int
icmp(const void *arg1, const void *arg2)
{
	return (*(int *)arg1 - *(int *)arg2);
}

main()
{
	int ivals[] = {100, 5, 6, 2, 8, 3, 45, 23};
	int i;

	qsort((void *)ivals, sizeof(ivals) / sizeof(int), sizeof(int), icmp);
	for (i = 0; i < sizeof(ivals) / sizeof(int); i++)
		printf("%d\n", ivals[i]);
}