Dev Faq
8
votes

Exemple K & R Qsort avec confusion des pointeurs et des tableaux

Je trouve difficile de comprendre l'extrait de code suivant. Je comprends que le pointeur pour fonctionner latérisme a montré, mais où je trouve que je trouve que la confusion est dans les lignes indiquées. 

void qsort(void **v, int left, int right, int (*comp) (void *, void *))
{
    int i, last;
    void swap(int **v, int i, int j);

    if (left >= right)   /* do nothing if array contains */
        return;           /* fewer than two elements */
    swap(v, left, (left + right)/2);   /* move partition elem */ [1]
    last = left;                       /* to v[0] */ [2]
    for (i = left + 1; i <= right; i++) /* partition */ [3]
        if ((*comp) (v[i], v[left]) < 0) [4]
            swap(v, ++last, i); [5]
    swap(v, left, last);        /* restore partition elem */ [6]
    qsort(v, left, last - 1); [7]
    qsort(v, last + 1, right);  [8]

}

0 commentaires

5 Réponses :

2
votes

Magic utile Google Mots-clés: Quicksort

E.g. Google: Comment TrickSort Works présente cette explication: http://www.angelfire.com/pq/jamesbarbetti/articles/sorting/001a_howquicksortworks. HTM entre autres.

Essentiellement, le code applique une variante de QuickSort aux éléments entre le gauche et droite limites spécifiées.

Pour les lignes que vous avez identifiées:

  1. échangez l'élément central avec le premier ( gauche ) un. Il deviendra le "pivot".

  2. Gardez une trace de la frontière entre des éléments plus petits et plus petits. C'est là que appartient le pivot.

  3. pour chaque élément après le premier,
  4. S'il est plus petit que le pivot,

  5. déplacez-le avant le premier plus grand élément.

  6. Déplacez le pivot en place.

  7. Appliquez récursivement Qsort aux éléments avant le pivot. (les plus petits)

  8. Appliquez récursivement Qsort aux éléments après le pivot. (les plus gros)

    Essayez d'appliquer le code vous-même dans une liste de numéros et voyez si cela a plus de sens que ...

0 commentaires
15
votes

Ceci est un beau morceau de code!

Tout d'abord, il est important que vous comprenez l'idée derrière quicksort:

1) Faites une liste des numéros.

2) choisir un, X l'appeler.

3) Faites deux listes, l'une de tous les nombres inférieurs à X, et l'un de tous les numéros plus.

4) Classer les nombres plus petits que X. Trier les nombres supérieurs à X.

L'idée est que si l'on a de la chance et choisir un bon rapport qualité-X, la liste des nombres plus petits que X est la même taille que la liste des nombres supérieurs à X. Si nous commençons avec 2 * N + 1 numéros , nous obtenons deux listes de numéros N. A chaque fois, nous espérons diviser par deux, mais nous devons trier N nombres. Combien de fois peut-on diviser par deux N? Ce Log (N). Donc, nous trions N Log (N) fois. C'est grand!

En ce qui concerne le fonctionnement du code, voici RUNTHROUGH, avec un petit croquis. Nous sélectionnerons un petit tableau:)

Voici notre tableau: [DACBE]

au début, à gauche = 0, pointant vers D. droite = 4, pointant vers E.

, le code suivant, avec votre étiquetage:

[1] swap (v, 0,2) [DACBE] -> [CADBE]

nous avons troqué notre valeur choisie et de le mettre au début du tableau.

[2] = 0 dernière

est un peu intelligent ... nous voulons garder un compteur afin que nous sachions quelles valeurs ont été plus et qui moins ... vous verrez comment ce progrès

[3] for (i = 1; i <= 4; i ++)

pour tous les autres éléments de la liste ...

[4] if ((* comp) (v [i], 'C') <0)

si la valeur à i est inférieure à 'C' ...

[5] swap (v, ++ dernière, i);

le mettre au début de la liste!

Lançons le code pour 3,4,5

i = 1:

[CADBE]

if ( 'A' < 'C')

swap ( 'A', 'A') (ET AUGMENTER ENFIN!)

[CADBE] -> [CADBE] (pas de changement)

last = 1

i = 2:

[CADBE]

if ( 'D' < 'C')

échoue. passer.

i = 3:

[CADBE]

if ( 'B' < 'C')

swap ( 'B', 'D') Enfin! Incrément

[CADBE] -> [CABDE] (! Lookit il est tri)

dernier = 2

i = 4:

[CABDE]

if ( 'E' < 'C')

échoue. passer.

Ok, as. de sorte que la boucle est donne [CABDE], last = 2 ( 'B')

ligne [6] .... swap (gauche, dernier) ... que de swap ( 'C', 'B') [CABDE] -> [BACDE]

Maintenant, la magie de c'est ... il est partiellement triée! BA

Alors maintenant, nous trions les sous-listes !!

[7] -> [BA] -> [AB]

[BACDE] -> [ABCDE]

[8] -> [DE] -> [DE]

[ABCDE] -> [ABCDE]

et nous fait!

0 commentaires
4
votes

K & R's's's's's's's's's's's's's est un exemple de bon codage, mais pas un excellent exemple de la façon dont les œuvres du QuickSort. Le but de la preswap n'est pas intuitif et que les swaps d'identité sont inefficaces et déroutants. J'ai écrit un programme pour aider à clarifier cela. Les commentaires du code expliquent les problèmes.

J'ai compilé et testé uniquement sous Linux, mais Visual Studio ne devrait pas avoir de problème avec cette application de console Vanilla ordinaire. P> 

Results of quick
This uses all defaults, which is most useful for comparing the performance
of the three different functions.

====== krQuick ======
4 0 2 5 1 3 
0 1 2 3 4 5 
Calls = 7, depth = 2, compares = 8, swaps = 20
---------------------------------
0 1 2 3 4 5 6 7 8 9 10 11 
0 1 2 3 4 5 6 7 8 9 10 11 
Calls = 15, depth = 3, compares = 25, swaps = 48
---------------------------------
11 10 9 8 7 6 5 4 3 2 1 0 
0 1 2 3 4 5 6 7 8 9 10 11 
Calls = 17, depth = 5, compares = 30, swaps = 62
---------------------------------
11 9 7 5 3 1 0 2 4 6 8 10 
0 1 2 3 4 5 6 7 8 9 10 11 
Calls = 13, depth = 5, compares = 33, swaps = 56
---------------------------------
11 0 10 1 9 2 8 3 7 4 6 5 
0 1 2 3 4 5 6 7 8 9 10 11 
Calls = 15, depth = 6, compares = 38, swaps = 60
---------------------------------
Total: calls = 67, depth = 21, compares = 134, swaps = 246
====== krQuick2 (no identity swaps) ======
4 0 2 5 1 3 
0 1 2 3 4 5 
Calls = 7, depth = 2, compares = 8, swaps = 16
---------------------------------
0 1 2 3 4 5 6 7 8 9 10 11 
0 1 2 3 4 5 6 7 8 9 10 11 
Calls = 15, depth = 3, compares = 25, swaps = 28
---------------------------------
11 10 9 8 7 6 5 4 3 2 1 0 
0 1 2 3 4 5 6 7 8 9 10 11 
Calls = 17, depth = 5, compares = 30, swaps = 52
---------------------------------
11 9 7 5 3 1 0 2 4 6 8 10 
0 1 2 3 4 5 6 7 8 9 10 11 
Calls = 13, depth = 5, compares = 33, swaps = 46
---------------------------------
11 0 10 1 9 2 8 3 7 4 6 5 
0 1 2 3 4 5 6 7 8 9 10 11 
Calls = 15, depth = 6, compares = 38, swaps = 44
---------------------------------
Total: calls = 67, depth = 21, compares = 134, swaps = 186
====== quick3 (no preswaps) ======
4 0 2 5 1 3 
0 1 2 3 4 5 
Calls = 7, depth = 3, compares = 10, swaps = 10
---------------------------------
0 1 2 3 4 5 6 7 8 9 10 11 
0 1 2 3 4 5 6 7 8 9 10 11 
Calls = 23, depth = 11, compares = 66, swaps = 22
---------------------------------
11 10 9 8 7 6 5 4 3 2 1 0 
0 1 2 3 4 5 6 7 8 9 10 11 
Calls = 23, depth = 11, compares = 66, swaps = 22
---------------------------------
11 9 7 5 3 1 0 2 4 6 8 10 
0 1 2 3 4 5 6 7 8 9 10 11 
Calls = 15, depth = 7, compares = 46, swaps = 54
---------------------------------
11 0 10 1 9 2 8 3 7 4 6 5 
0 1 2 3 4 5 6 7 8 9 10 11 
Calls = 19, depth = 6, compares = 37, swaps = 30
---------------------------------
Total: calls = 87, depth = 38, compares = 225, swaps = 138

*******************************************************************************

Results of quick f0 s5 d1
S5 format is best for displaying how the sublist changes during sorting. Since 
LOCAL is displayed only after a swap, superfluous identity swaps (many in this 
example) are readily apparent.

====== krQuick ======
0 1 2 3 4 5 6 7 8 9 10 11 
GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
Local1: 0 1 2 3 4 5 6 7 8 9 10 11 
Local2: 5 1 2 3 4 0 6 7 8 9 10 11 
Local3: 5 1 2 3 4 0 6 7 8 9 10 11 
Local3: 5 1 2 3 4 0 6 7 8 9 10 11 
Local3: 5 1 2 3 4 0 6 7 8 9 10 11 
Local3: 5 1 2 3 4 0 6 7 8 9 10 11 
Local3: 5 1 2 3 4 0 6 7 8 9 10 11 
Local4: 0 1 2 3 4 5 6 7 8 9 10 11 
GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
  Local1: 0 1 2 3 4 
  Local2: 2 1 0 3 4 
  Local3: 2 1 0 3 4 
  Local3: 2 1 0 3 4 
  Local4: 0 1 2 3 4 
GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
    Local1: 0 1 
    Local2: 0 1 
    Local4: 0 1 
GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
      Local1: 
GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
      Local1: 1 
GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
    Local1: 3 4 
    Local2: 3 4 
    Local4: 3 4 
GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
      Local1: 
GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
      Local1: 4 
GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
  Local1: 6 7 8 9 10 11 
  Local2: 8 7 6 9 10 11 
  Local3: 8 7 6 9 10 11 
  Local3: 8 7 6 9 10 11 
  Local4: 6 7 8 9 10 11 
GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
    Local1: 6 7 
    Local2: 6 7 
    Local4: 6 7 
GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
      Local1: 
GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
      Local1: 7 
GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
    Local1: 9 10 11 
    Local2: 10 9 11 
    Local3: 10 9 11 
    Local4: 9 10 11 
GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
      Local1: 9 
GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
      Local1: 11 
0 1 2 3 4 5 6 7 8 9 10 11 
Calls = 15, depth = 3, compares = 25, swaps = 48

********************************************************************************

Results of quick f0 sa d1
This is the same as the previous example but shows the additional detail of index
values that lead to the swapping decision. However, the clutter tends to obscure
what is actually happening to the sublist.

====== krQuick ======
0 1 2 3 4 5 6 7 8 9 10 11 
GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
Local1: 0 1 2 3 4 5 6 7 8 9 10 11 
Local2: 5 1 2 3 4 0 6 7 8 9 10 11 
i=1 @i=1 left=0 @left=5 last=0
Local3: 5 1 2 3 4 0 6 7 8 9 10 11 
i=2 @i=2 left=0 @left=5 last=1
Local3: 5 1 2 3 4 0 6 7 8 9 10 11 
i=3 @i=3 left=0 @left=5 last=2
Local3: 5 1 2 3 4 0 6 7 8 9 10 11 
i=4 @i=4 left=0 @left=5 last=3
Local3: 5 1 2 3 4 0 6 7 8 9 10 11 
i=5 @i=0 left=0 @left=5 last=4
Local3: 5 1 2 3 4 0 6 7 8 9 10 11 
Local4: 0 1 2 3 4 5 6 7 8 9 10 11 
GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
  Local1: 0 1 2 3 4 
  Local2: 2 1 0 3 4 
  i=1 @i=1 left=0 @left=2 last=0
  Local3: 2 1 0 3 4 
  i=2 @i=0 left=0 @left=2 last=1
  Local3: 2 1 0 3 4 
  Local4: 0 1 2 3 4 
GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
    Local1: 0 1 
    Local2: 0 1 
    Local4: 0 1 
GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
      Local1: 
GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
      Local1: 1 
GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
    Local1: 3 4 
    Local2: 3 4 
    Local4: 3 4 
GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
      Local1: 
GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
      Local1: 4 
GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
  Local1: 6 7 8 9 10 11 
  Local2: 8 7 6 9 10 11 
  i=7 @i=7 left=6 @left=8 last=6
  Local3: 8 7 6 9 10 11 
  i=8 @i=6 left=6 @left=8 last=7
  Local3: 8 7 6 9 10 11 
  Local4: 6 7 8 9 10 11 
GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
    Local1: 6 7 
    Local2: 6 7 
    Local4: 6 7 
GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
      Local1: 
GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
      Local1: 7 
GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
    Local1: 9 10 11 
    Local2: 10 9 11 
    i=10 @i=9 left=9 @left=10 last=9
    Local3: 10 9 11 
    Local4: 9 10 11 
GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
      Local1: 9 
GLOBAL 0 1 2 3 4 5 6 7 8 9 10 11 
      Local1: 11 
0 1 2 3 4 5 6 7 8 9 10 11 
Calls = 15, depth = 3, compares = 25, swaps = 48

0 commentaires
0
votes

Il y a un bogue dans votre code, les lignes à la fin: xxx

doit être: xxx

ou je manque quelque chose ?

En outre, il est mauvais style de réutiliser les noms de la bibliothèque standard, en particulier si la nouvelle fonction a une signature différente de celle de la lib. La fonction qsort de la bibliothèque standard a ce prototype: xxx

si votre programme est un peu plus grand (plus d'un fichier objet), cela peut donner des bugs intéressants. Imaginez un autre module appelant la fonction QSort standard, mais comme vous l'avez redéfinie, avec une signature compatible, mais avec une autre sémantique, vous obtenez un bug inattendu.

0 commentaires
0
votes

Bonjour, j'ai fait l'exemple de la page 87. Peut-être que quelqu'un comprendra de cela. Mais avant de partir pour ce code, voir Quicksort 

/**
 * qsort.c
 * Quick sort using recursion
 */

#include <stdio.h>

void qsort(int v[], int left, int right);

int main()
{
    int v[] = {9, 3, 4, 6, 7, 3, 1};
    qsort(v, 0, 6);

    int i;

    for (i = 0; i < 7; i++)
        printf(" %d ", v[i]);

    printf("\n");

    return 0;
}

void qsort(int v[], int left, int right)
{
    int i, last; /* last is pivot */

    void swap(int v[], int i, int j);

    if (left >= right)
        return;

    swap(v, left, (left + right) / 2); // swap mid element to front
    last = left;                       // set this position as pivot

    for (i = left + 1; i <= right; i++) { 
        /*loop through every other element 
          swap elements less than pivot i.e bigger to right, smaller to left
        */ 

        if (v[i] < v[left])
            swap(v, ++last, i);     // when swapping lesser element, record
                                    // where our pivot moves
        /*
           we don't swap elements that are bigger than pivot, and are to right.
           However we swap elements those are less than pivot.
           With ++pivot we are essentially going to find out, where our
           pivot will fit to be at the position, where all the elements
           before it are less than it and all after it greater.
        */
    }

    // swap left(our pivot) to last(where pivot must go
    // i.e all elements before pivot are less than it
    // and all elements above it are greater
    // remember they are lesser and greater 
    // but may not be sorted still
    // this is called partition
    swap(v, left, last);

    // Do same(qsort) for all the elements before our pivot
    // and above our pivot
    qsort(v, left, last - 1);   // last is our pivot position
    qsort(v, last + 1, right);

    // Each of above two qsort will use middle element as pivot and do
    // what we did above, because same code will be executed by recursive
    // functions

}                                       

void swap(int v[], int i, int j)
{
    int temp;

    temp = v[i];
    v[i] = v[j];
    v[j] = temp;
}

0 commentaires

Articles qui pourrait vous intéresser :

Que puis-je utiliser pour la conversion d'entrée au lieu de scanf?
Comment puis-je calculer a * b / c lorsque a et b sont tous deux plus petits que c, mais que a * b déborde?
Comment vérifier si un pointeur void (void *) est l'un des deux types de données?
L'écran LCD affiche des caractères aléatoires (MPLAB)