Come funziona il qsort di K & R?

Question

Come funziona il qsort di K & R?

#1 da (8 voti)

4

Nella sezione di ricorsione del libro ANSI C di K & R, essi dimostrano un

version of quicksort [that] is not the fastest possible, but it's one of the simplest.

--The C Programming Language (ANSI C) - pg. 87

Nella sua interezza:

/*qsort: sort v[left]...v[right] into increasing order*/
void qsort(int v[], int left, int right){

  int i, last;

  /*do nothing if array has less than 2 elements*/      
  if(left >= right)
    return;

  swap(v, left, (left + right) / 2); 
  last = left;

  /*partition*/
  for(i = left + 1; i <= right; i++)
    if(v[i] < v[left])
      swap(v, ++last, i);

  swap(v, left, last);  /*reset partition element*/
  qsort(v, left, last - 1);
  qsort(v, last + 1, right);
}

dove swap(v, i, j) scambia due membri dell'array v .

Sto cercando di capire come questo ordina la matrice. Sembra che last sia un elemento dell'array che separa l'array in due array più piccoli e poi viene scambiato con l'elemento di delimitazione sinistro. Viene quindi confrontato con tutti gli elementi fino al limite destro, scambiando ogni elemento più piccolo con ++last (perché?).

Infine, l'elemento della partizione viene reinserito e i due sottoarray sono ordinati separatamente.

Se comprendo correttamente la ricorsione, questo algoritmo indica che alla fine di un passaggio tutti gli elementi a sinistra di last sono più piccoli di tutti gli elementi a destra di last . Ho difficoltà a trovare una spiegazione perché la maggior parte degli algoritmi qsort sono più complicati di questo.

recursion c algorithms sorting ansi

posta user1717828 30.08.2016 - 20:56

fonte

1 risposta

Leggi altre domande sui tag recursion c algorithms sorting ansi

Come funziona un interprete? [chiuso] Come trovare il vettore più vicino a un determinato vettore?

score 8 · Accepted Answer

L'algoritmo qui è:

Prendi il valore nel mezzo dell'array e spostalo in avanti (scambiando). Questo valore è il pivot.
Passa attraverso il resto dell'array. Ogni volta che vedi un valore inferiore al pivot, scambialo più vicino alla parte anteriore dell'array. Nello specifico abbiamo un indice (chiamato last ) che tiene traccia di dove è stato scambiato l'ultimo valore inferiore. Ogni volta che troviamo un valore inferiore, lo incrementiamo per trovare un punto in cui mettere quel valore.
Quando raggiungi la fine, la matrice è composta da:
- il pivot
- tutti i valori inferiori al pivot
- tutti i valori maggiori o uguali al pivot
Scambia il pivot con la posizione dell'ultimo valore trovato minore.

A questo punto si sa di avere un sub-array su entrambi i lati del pivot. A sinistra hai i valori inferiori al pivot, a destra tutti i valori maggiori o uguali al pivot. Quindi sai che il pivot si trova esattamente nella posizione corretta per l'array ordinato finale. Sai anche che nessun valore di alcun sotto-array dovrà scambiare con quelli sull'altro lato. Quindi ora puoi:

ordina l'array secondario sinistro con lo stesso algoritmo
ordina la sub-array giusta con lo stesso algoritmo.

Ogni volta che si ricorre, si hanno sottosegmenti più piccoli, quindi il prossimo livello di ricorsione è più veloce. Inoltre, ogni volta che sposti un elemento nella posizione corretta, prima di andare più in profondità. Alla fine si raggiunge il punto in cui c'è solo zero o un elemento in un sotto-array, il che significa ovviamente che l'array secondario è già ordinato. Ciò che si ottiene a qualsiasi livello è un elemento nel punto giusto, con un sub-array ordinato di valori minori a sinistra e un sub-array ordinato di valori maggiori o uguali a destra, in modo da conoscere l'intero ( sub-) array a quel livello è ordinato.