La modifica di questa Quicksort di utilizzare sempre il l'ultimo elemento come il perno

Question

Ho il seguente Quicksort che sceglie sempre il primo elemento della sottosequenza come suo perno:

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

Ora, come potete vedere, questo algoritmo prende sempre il primo elemento ad essere il perno: int pivot = array[start];

Voglio modificare questo algoritmo per renderlo utilizzare sempre l'ultimo elemento al posto del primo elemento della sottosequenza, perché voglio analizzare i tempi di esecuzione fisiche di entrambe le implementazioni.

Ho provato a cambiare il int pivot = array[start]; linea int pivot = array[end]; ma l'algoritmo poi in uscita una sequenza non ordinata:

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

Per provare un altro pivot, ho anche provato ad utilizzare l'elemento centrale della sottosequenza ma l'algoritmo ancora non è riuscito:

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

---

Per favore qualcuno può aiutarmi a capire questo algoritmo in modo corretto e mi dica quali modifiche devo fare per avere successo questa implementazione scegliere sempre l'ultimo elemento della sottosequenza come il perno?

Answer 1

La causa del problema

Il problema è che si utilizza int k = end;. E 'stato bene usare int i = start; quando si aveva l'elemento pivot come il primo elemento della matrice, perché i controlli nel ciclo saranno scremare passato (array[i] <= pivot). Tuttavia, quando si utilizza l'ultimo elemento come perno, k arresta sull'indice estremità e passa il perno in una posizione nella metà sinistra della partizione. Già sei nei guai perché il perno sarà molto probabilmente da qualche parte all'interno della partizione di sinistra piuttosto che alla frontiera.

La soluzione

Per risolvere questo problema, è necessario impostare int k = end - 1; quando si utilizza l'elemento più a destra come perno. Avrete anche bisogno di cambiare le linee per scambiare il perno al confine tra la sinistra e la destra partizioni:

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

È necessario utilizzare i per questo, perché io finire al l'elemento più a sinistra della partizione destra (che possono poi essere scambiato con il perno essendo nell'elemento più a destra e sarà Preservatore l'ordine). Infine, ti consigliamo di cambiare k >= i al k > i nel mentre che decrementa k, altrimenti non v'è piccolo cambiamento di una matrice [-1] Errore di indicizzazione. Questo non era possibile che accada prima, perché ho sempre almeno è stato pari a i + 1 da questo punto.

Che dovrebbe farlo.

Nota a margine:

Questa è una quicksort scritta male che io non consiglierei imparare da. Ha un alcuni estranei, i confronti inutili insieme ad alcuni altri difetti che non voglio sprecare tempo lista. Ti consiglio di utilizzare i quicksorts in questa presentazione di Sedgewick e Bentley.

Answer 2

non ho la prova, ma controllare lo stesso:

questo

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

probabilmente dovrebbe essere

swap(array, end, i);

o qualcosa di simile, se scegliamo end come perno.

Modifica Questo è un algoritmo di partizionamento interessante, ma non è il standard uno.

Bene, il di rotazione è fissato nella logica del partizionamento.
L'algoritmo considera il primo elemento come il capo e gli elementi di riposo come il corpo ad essere partizionato.
Dopo il partizionamento è fatto, come fase finale, la testa (perno) viene scambiato con il ultima elemento della parte sinistra partizionato, per mantenere l'ordine.

L'unico modo ho pensato di utilizzare un perno diversa, senza cambiare l'algoritmo, è questa:

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

Answer 3

In primo suggerimento: Se i dati sono casuali, non importa, in media, il cui valore si sceglie come perno. L'unico modo per migliorare effettivamente la "qualità" del perno è di prendere più (ad esempio 3) indici e utilizzare quello con il valore mediano di questi.

Secondo suggerimento: se si modifica il valore di rotazione, è inoltre necessario modificare l'indice di rotazione. Questo non si chiama in modo esplicito, ma array[start] viene scambiato nel "mezzo" della sottosequenza ordinato ad un certo punto. È necessario modificare questa linea di conseguenza. Se si prende un indice che non è al bordo della sottosequenza, è necessario scambiare al bordo, prima iterazione.

Terzo suggerimento: il codice che hai fornito è troppo commentato. Si dovrebbe essere in grado di capire in realtà questa implementazione.

Answer 4

Mettere un singolo

swap(array, start, end)

prima di inizializzare perno

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

Se si avvia il monitoraggio ogni elemento dal primo elemento della matrice fino all'ultimo - 1, mantenendo l'ultimo elemento come perno ad ogni ricorsione, allora si otterrà la risposta in esatta O (nlogn) tempo.

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