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

Question

je le Quicksort suivant qui choisit toujours le premier élément de la sous-séquence comme 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 toujours prend le premier élément à être le pivot: int pivot = array[start];

Je veux modifier cet algorithme pour qu'il utilise toujours le dernier élément au lieu du premier élément de la sous-séquence, car je veux analyser les temps de fonctionnement physiques des deux implémentations.

J'ai essayé de changer la ligne int pivot = array[start];-int pivot = array[end]; mais l'algorithme puis en sortie une séquence non triés:

//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 Suc ont cessfully 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 bon d'utiliser int i = start; lorsque vous aviez l'élément pivot comme premier élément dans le tableau car vos vérifications dans la boucle passeront devant lui (array[i] <= pivot). Cependant, lorsque vous utilisez le dernier élément comme pivot, k s'arrête sur l'index de fin et place le pivot sur une position dans la moitié gauche de la partition. Vous avez déjà des problèmes parce que votre pivot sera 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 de la frontière entre les partitions gauche et 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 gauche à droite la partition (qui peut alors être permuté avec le pivot étant dans l'élément le plus à droite et il conservera la commande). Enfin, vous voudrez changer k >= i en k > i dans le temps qui décrémente k ou bien il y a un petit changement d'une erreur d'indexation de tableau [-1]. Ce n'était pas possible avant parce que j'ai toujours au moins été é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 quelques comparaisons inutiles et inutiles avec quelques autres défauts que je ne perdrai pas de temps. Je recommande d'utiliser les quicksorts dans this presentation par Sedgewick et Bentley.

Answer 2

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

ce

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

devrait probablement

swap(array, end, i); 

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

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

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

La seule façon que je pensais 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, dont la valeur vous 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 ceux-ci.

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 index qui n'est pas au bord de la sous-séquence, vous devez d'abord l'échanger sur le bord avant l'itération.

Troisième indice: Le code que vous avez fourni est excessivement commenté. Vous devriez être capable de comprendre réellement cette implémentation.

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); 
} 
}