La modificación de esta ordenación rápida de utilizar siempre el último elemento como el pivote
https://stackoverflow.com/questions/2316756
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Tengo la siguiente ordenación rápida que siempre elige el primer elemento de la subsecuencia como su pivote:
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;
}
}
Ahora bien, como se puede ver, este algoritmo siempre toma el primer elemento a ser el eje: int pivot = array[start];
Quiero modificar este algoritmo para que sea siempre utilizar el último elemento en lugar del primer elemento de la subsecuencia, porque quiero analizar los tiempos de funcionamiento de ambas implementaciones físicas.
I intentado cambiar la int pivot = array[start]; línea a int pivot = array[end]; pero el algoritmo entonces emite una secuencia sin clasificar:
//Changes: int pivot = array[end];
unsorted: {5 4 3 2 1}
*sorted*: {1 2 5 4 3}
Para probar otro pivote, también probé usando el elemento central de la subsecuencia pero el algoritmo todavía no se pudo:
//Changes: int pivot = array[(start + end) / 2];
unsorted: {5 3 4 2 1}
*sorted*: {3 2 4 1 5}
Puede alguien por favor me ayuda a entender este algoritmo correctamente y dime qué cambios necesito hacer para tener éxito esta aplicación siempre elige el último elemento de la subsecuencia como el pivote?
Solución
la causa del problema
El problema es que utilice int k = end;. Fue muy bien utilizar int i = start; cuando se tenía el elemento de pivote como el primer elemento de la matriz debido a sus cheques en el bucle se descremada pasado (array[i] <= pivot). Sin embargo, cuando se utiliza el último elemento como el pivote, k se detiene en el índice final y conmuta el pivote a una posición en la mitad izquierda de la partición. Ya que estás en problemas porque su pivote más probable es que en algún lugar dentro de la partición izquierda en lugar de en la frontera.
La solución
Para solucionar este problema, es necesario int k = end - 1; conjunto cuando se utiliza el elemento más a la derecha como pivote. También tendrá que cambiar las líneas para el bombeo del pivote de la frontera entre las particiones izquierda y derecha:
swap(array, i, end);
qqsort(array, start, i - 1);
qqsort(array, i + 1, end);
Usted tiene que usar i para esto porque voy a terminar en el elemento más a la izquierda de la partición de la derecha (que puede ser intercambiado con el ser de pivote en el elemento más a la derecha y que va a preservador de la orden). Por último, tendrá que cambiar k >= i a k > i en el tiempo, que disminuye k o de lo contrario hay un pequeño cambio de una matriz [-1] Error de indexación. Esto no era posible que ocurrir antes porque siempre al menos era igual a i + 1 por este punto.
Eso debería hacerlo.
Nota al margen:
Esta es una clasificación rápida mal escrito que yo no recomendaría el aprendizaje a partir. Tiene un algunas comparaciones innecesarias extraños, junto con algunos otros fallos que no voy a perder listado de horas. Yo recomendaría el uso de los quicksorts en esta presentación por Sedgewick y Bentley.
Otros consejos
no he probado, pero compruebo que de todos modos:
// after the indices have crossed,
// swap the last element in the left partition with the pivot
swap(array, start, k);
probablemente debería ser
swap(array, end, i);
o algo similar, si elegimos end como pivote.
Editar Eso es un algoritmo de partición interesante, pero no es el estándar uno.
Bueno, el pivote se fija en la lógica de la partición.
Las golosinas algoritmo del primer elemento como la cabeza y los elementos de apoyo como el organismo al dividirse.
Después se realiza la partición, como un paso final, la cabeza (pivote) se intercambia con el última elemento de la parte con particiones izquierda, para mantener el pedido.
La única manera de que pensé utilizar un pivote diferente, sin cambiar el algoritmo, es la siguiente:
...
if (end - start >= 1) {
// Swap the 1st element (Head) with the pivot
swap(array, start, pivot_index);
int pivot = array[start];
...
Primera pista: Si los datos son al azar, no importa, en promedio, cuyo valor se elige como pivote. La única manera de mejorar realmente la "calidad" del pivote es tomar más (3) por ejemplo, los índices y usar el uno con valor de la mediana de estos.
Segunda pista: Si cambia el valor de pivote, también hay que cambiar el índice de pivote. Esto no es nombrado explícitamente, pero array[start] se intercambia en el "medio" de la subsecuencia ordenada en un punto. Es necesario modificar esta línea en consecuencia. Si se toma un índice que no está en el borde de la subsecuencia, es necesario cambiarlo al borde primero, antes de la iteración.
Tercera pista: El código que ya ha proporcionado se comenta en exceso. Usted debe ser capaz de entender realmente esta aplicación.
Ponga un solo
swap(array, start, end)
antes de inicializar pivote
int pivot = array[start]
#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;
}
Si se inicia el seguimiento de cada elemento de la primera elemento de la matriz a la última - 1, manteniendo el último elemento como el pivote en cada recursividad, por lo que recibirá la respuesta en exacta O (nlogn) tiempo.
#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);
}
}
