La modification de cette Quicksort d'utiliser toujours le dernier élément comme le pivot

Question

Je le Quicksort qui choisit toujours le premier élément de la séquence en son pivot:

void qqsort(int array[], int start, int end) {
    int i = start; // index of left-to-right scan
    int k = end; // index of right-to-left scan

    if (end - start >= 1) { // check that there are at least two elements to sort 
        int pivot = array[start]; // set the pivot as the first element in the partition
        while (k > i) { // while the scan indices from left and right have not met, 
            while (array[i] <= pivot && i <= end && k > i)  // from the left, look for the first element greater than the pivot
                i++;
            while (array[k] > pivot && k >= start && k >= i) // from the right, look for the first element not greater than the pivot
                k--;
            if (k > i) // if the left seekindex is still smaller than the right index, swap the corresponding elements
                swap(array, i, k);              
        }
        swap(array, start, k); // after the indices have crossed, swap the last element in the left partition with the pivot 
        qqsort(array, start, k - 1); // quicksort the left partition
        qqsort(array, k + 1, end); // quicksort the right partition
    } else { // if there is only one element in the partition, do not do any sorting 
        return;
    }
}

Maintenant, comme vous pouvez le voir, cet algorithme prend toujours le premier élément à être le pivot: int pivot = array[start];

Je veux modifier cet algorithme pour le rendre toujours utiliser le dernier élément à la place du premier élément de la sous-séquence, parce que je veux analyser les temps de fonctionnement physique des deux implémentations.

Je l'ai essayé de changer int pivot = array[start]; ligne à int pivot = array[end]; mais l'algorithme puis une séquence non trié émis:

//Changes: int pivot = array[end]; 
unsorted: {5 4 3 2 1}
*sorted*: {1 2 5 4 3}

Pour tester un autre pivot, j'ai aussi essayé d'utiliser l'élément central de la sous-séquence, mais l'algorithme toujours pas:

//Changes: int pivot = array[(start + end) / 2]; 
unsorted: {5 3 4 2 1}
*sorted*: {3 2 4 1 5}

---

Quelqu'un peut-il s'il vous plaît me aider à comprendre cet algorithme correctement et me dire quels changements dois-je faire pour avoir avec succès cette mise en œuvre toujours choisir le dernier élément de la sous-séquence comme le pivot?

Answer 1

La Cause du problème

Le problème est que vous utilisez int k = end;. Il était bien utiliser int i = start; lorsque vous aviez l'élément pivot comme le premier élément du tableau parce que vos contrôles dans la boucle écrémé passé, il (array[i] <= pivot). Cependant, lors de l'utilisation du dernier élément de pivot, k arrête l'indice d'extrémité et le pivot passe à une position dans la moitié gauche de la cloison. Déjà vous êtes en difficulté parce que votre pivot sera très probablement quelque part à l'intérieur de la partition gauche plutôt qu'à la frontière.

La solution

Pour résoudre ce problème, vous devez définir int k = end - 1; lorsque vous utilisez l'élément le plus à droite comme le pivot. Vous aurez également besoin de changer les lignes pour échanger le pivot à la frontière entre la gauche et les partitions droite:

swap(array, i, end);
qqsort(array, start, i - 1);
qqsort(array, i + 1, end);

Vous devez j'utiliser pour cela parce que je vais finir par l'élément de la gauche partition droite (qui peut ensuite être échangé avec le pivot étant dans l'élément le plus à droite et il preserver l'ordre). Enfin, vous aurez envie de changer k >= i à k > i dans le tout qui décrémente k ou bien il est petit changement d'un tableau [-1] d'erreur d'indexation. Cela n'a pas été possible d'arriver avant parce que je toujours au moins était égal à i + 1 par ce point.

Cela devrait le faire.

Sidenote:

Ceci est un quicksort mal écrit que je ne recommanderais pas d'apprendre. Il a une des comparaisons inutiles étrangères, ainsi que quelques autres défauts que je ne perdrai pas de temps liste. Je recommande d'utiliser les quicksorts cette présentation par Sedgewick et Bentley.

Answer 2

Je n'ai pas testé, mais le vérifier quand même:

// after the indices have crossed,
// swap the last element in the left partition with the pivot
swap(array, start, k);

devrait probablement être

swap(array, end, i);

ou quelque chose de similaire, si nous choisissons end comme pivot.

Edit: est un algorithme de partitionnement intéressant, mais ce n'est pas standard un.

Eh bien, pivot est fixé dans la logique du cloisonnement.
L'algorithme traite le premier élément que la tête et les éléments de repos que le corps à partitionner.
Après la séparation se fait, comme une étape finale, la tête (pivot) est échangé avec dernier élément de la partie gauche divisée, pour garder l'ordre.

La seule façon je me suis dit d'utiliser un pivot différent, sans changer l'algorithme, est la suivante:

...
if (end - start >= 1) {
    // Swap the 1st element (Head) with the pivot
    swap(array, start, pivot_index);
    int pivot = array[start];
...

Answer 3

Première indication: Si les données sont aléatoires, il n'a pas d'importance, en moyenne, que vous appreciez choisissez comme pivot. La seule façon d'améliorer réellement la « qualité » du pivot est de prendre plus (par exemple 3) indices et utiliser celui avec la valeur médiane de ces derniers.

Deuxième indice: Si vous modifiez la valeur de pivot, vous devez également modifier l'indice de pivot. Ce n'est pas nommé explicitement, mais array[start] est permuté dans le « milieu » de la sous-séquence triée à un moment donné. Vous devez modifier cette ligne en conséquence. Si vous prenez un indice qui n'est pas au bord de la sous-séquence, vous devez échanger au bord d'abord, avant l'itération.

Troisième indice: Le code que vous avez fourni est trop commenté. Vous devriez être en mesure de comprendre réellement cette mise en œuvre.

Answer 4

Mettre un

swap(array, start, end)

avant d'initialiser pivot

int pivot = array[start]

Answer 5

#include <time.h>
#include <stdlib.h>
#include<iostream>
#include<fstream>
using namespace std;

int counter=0;
void disp(int *a,int n)
{
for(int i=0;i<n;i++)
cout<<a[i]<<" ";
cout<<endl;
}

void swap(int a[],int p,int q)
{

int temp;
temp=a[p];
a[p]=a[q];
a[q]=temp;

}

int partition(int a[], int p, int start, int end)
{
swap(a,p,start);// to swap the pivot with the first element of the partition
counter+=end-start;  // instead of (end-start+1)
int i=start+1;
for(int j=start+1 ; j<=end ; j++)
{
    if(a[j]<a[start])
    {
        swap(a,j,i);
        i++;

    }


}
swap(a,start,i-1);  // not swap(a,p,i-1) because p and start were already swaped.....    this was the earlier mistake comitted
return i-1; // returning the adress of pivot
}

void quicksort(int a[],int start,int end)
{
if(start>=end)
    return;


int p=end; // here we are choosing last element of the sub array as pivot
// here p is the index of the array where pivot is chosen randomly

int index=partition(a,p,start,end);

quicksort(a,start,index-1);
quicksort(a,index+1,end);

}

int main()
{

ifstream fin("data.txt");
int count=0;

int array[100000];

while(fin>>array[count])
{
    count++;
}
quicksort(array,0,count-1);
/*
int a[]={32,56,34,45,23,54,78};
int n=sizeof(a)/sizeof(int);
disp(a,n);

quicksort(a,0,n-1);
disp(a,n);*/
cout<<endl<<counter;
return 0;

}

Answer 6

Si vous commencer à surveiller chaque élément du 1er élément du tableau à la dernière - 1, en gardant le dernier élément comme le pivot à chaque récursion, alors vous obtiendrez la réponse exacte O (nlogn) temps.

#include<stdio.h>
void quicksort(int [], int, int);
int main()
{
int n, i = 0, a[20];
scanf("%d", &n);
while(i < n)
scanf("%d", &a[i++]);

quicksort(a, 0, n - 1);
i = 0;
while(i < n)
printf("%d", a[i++]);

}
void quicksort(int a[], int p, int r)
{
int i, j, x, temp;
if(p < r)
{
    i = p;
    x = a[r];
    for(j = p; j < r; j++)
    {
        if(a[j] <= x)
        {
            if(a[j] <a[i])
            {
                temp = a[j];
                a[j] = a[i];
                a[i] = temp;
            }
            i++;
        }

        else
        {
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    }
    if(x != i)
    {
        temp = a[r];
        a[r] = a[i];
        a[i] = temp;
    }

    quicksort(a, p, i - 1);
    quicksort(a, i + 1, r);
}
}