L'argomento comune per la stabilità in un algoritmo di ordinamento in genere implica un esempio in cui una lista è ordinata secondo due criteri. Ad esempio:
1,4,5,7,2,6,8,9,15,65,24,27
sort by evenness/oddness and then by value
2,4,6,8,24,1,5,7,9,15,27,65
L'affermazione è che, scegliendo un algoritmo di ordinamento stabile, puoi ordinare questo elenco due volte - in base al valore e poi alla uniformità - e avrai quindi la lista ordinata come volevi.
Non potrei essere più in disaccordo con questa ideologia, però. Prima di tutto, l'ordinamento è fatto all'indietro (valore, uniformità, in cui l'uniformità è il criterio principale), che non è intuitivo. In secondo luogo, facendo ciò, si chiama sort () due volte .
Ora diamo un'occhiata ad alcuni documenti. Abbiamo C qsort (3) e JavaScript Array.prototype.sort . Entrambe queste funzioni, per quanto ne so, implementano algoritmi di ordinamento instabili ...
If two members compare as equal, their order in the sorted array is undefined.
e
If compareFunction(a, b) returns 0, leave a and b unchanged with respect to each other, but sorted with respect to all different elements. Note: the ECMAscript standard does not guarantee this behaviour, and thus not all browsers (e.g. Mozilla versions dating back to at least 2003) respect this.
... ed entrambi accettano una funzione come argomento. Questa funzione è ciò che io considero un comparatore: una funzione che prende due valori A e B e restituisce -1, 0 o 1 a seconda che A sia considerato rispettivamente "minore di", "uguale a" o "maggiore" di "B, in base a qualsiasi criterio arbitrario scelto dall'implementatore.
Detto questo, quello che ho trovato è che, indipendentemente da ciò che lancio alle rispettive funzioni di ordinamento, indipendentemente dal fatto che li implemento da me o che usi quello della libreria standard, è che la stabilità non ha assolutamente alcuna influenza sul risultato del ordina quando la funzione di ordinamento viene utilizzata correttamente.
Usiamo il qsort di C come esempio. qsort implementa l'ordinamento rapido ed è noto per essere instabile.
If two members compare as equal, their order in the sorted array is undefined.
Per chiarire, questo non significa che l'implementazione sia per sé instabile. Ciò che significa è che la stabilità è non garantita , quindi fare affidamento su quella semantica è una pessima idea. Che è abbastanza vicino.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define INT(p) \
( *((int *)(p)) )
#define ISEVEN(p) \
(INT(p) % 2 == 0)
void
randomize(int *list, size_t len)
{
for(size_t i = 0; i < len; ++i)
list[i] = rand() % (len * 10);
}
void
printlist(int *list, size_t len)
{
for(size_t i = 0; i < len; ++i)
printf("%i, ", list[i]);
putchar('\n');
}
int
by_even(void const *a, void const *b)
{
return (ISEVEN(a) && !ISEVEN(b)) ? (-1) : (ISEVEN(b) && !ISEVEN(a));
}
int
by_value(void const *a, void const *b)
{
return (INT(a) < INT(b)) ? (-1) : (INT(a) > INT(b));
}
int
by_even_and_value(void const *a, void const *b)
{
return by_even(a, b) != 0 ? by_even(a, b) : by_value(a, b);
}
int
main(void)
{
static size_t const listsz = 20;
int list[listsz];
srand(time(NULL));
randomize(list, listsz);
printlist(list, listsz);
qsort(list, listsz, sizeof list[0], by_even_and_value);
printlist(list, listsz);
return 0;
}
E questo è l'output:
$ cc qsort.c
$ ./a.out
100, 111, 12, 122, 96, 50, 52, 96, 173, 125, 135, 173, 78, 144, 108, 60, 75, 116, 24, 180,
12, 24, 50, 52, 60, 78, 96, 96, 100, 108, 116, 122, 144, 180, 75, 111, 125, 135, 173, 173,
Quindi, inserendo tutti i criteri di ordinamento all'interno del comparatore e ordinando una volta mi ha dato la lista ordinata che volevo. Mi è bastato un solo ordinamento e il criterio poteva essere dato in ordine (anche primo, secondo valore).
Poiché ciò rende la stabilità apparentemente irrilevante per il risultato, perché dovremmo preoccuparci della stabilità di un algoritmo di ordinamento?
