ordenamiento rápido en C

Estoy tratando de usar una ordenación rápida para mi proyecto pero no funciona. Y no puedo averiguar dónde está el error. ¿Alguien que pueda ayudarme a resolverlo? Gracias.

void quicksort(int arr[],int a, int b){ if(a<=b){ int key=arr[a]; int index=a; int i=a, j=b; while(ikey;--j); int temp=arr[j]; arr[j]=key; arr[index]=temp; index=j; for(;arr[i]<key;++i); temp=arr[i]; arr[i]=key; arr[index]=temp; index=i; } quicksort(arr,a,index); quicksort(arr,index,b); } else return; } 

Tu bucle interno hace esto:

  • Verifique en el lado derecho de la matriz para encontrar un elemento que debería estar en el lado izquierdo de la key .
  • Intercambie cualquier elemento encontrado con key , ubicado en el index y actualice el index a la nueva ubicación de la key
  • Verifique en el lado izquierdo de la matriz para encontrar un elemento que debería estar en el lado derecho de la key .
  • Intercambie cualquier elemento encontrado con key , ubicado en el index y actualice el index a la nueva ubicación de la key

¿Por qué demonios querrías hacer esto? Usted debe hacer esto:

  • Verifique en el lado derecho de la matriz para encontrar un elemento que debería estar en el lado izquierdo de la key .
  • Verifique en el lado izquierdo de la matriz para encontrar un elemento que debería estar en el lado derecho de la key .
  • Si los encuentra, intercambíelos. Si no, coloque el pivote en la posición correcta y salga del bucle

No estoy seguro al 100%, pero creo que la confusión de la key en tu versión de quicksort puede ser la causa de tu problema. La mejor manera de averiguarlo es depurar su código paso a paso y ver dónde falla.

Aquí está la implementación de acuerdo con mi sugerencia anterior, junto con algunos casos de prueba:

 void swap(int arr[], int i, int j) { int temp = arr[j]; arr[j] = arr[i]; arr[i] = temp; } void quicksort0(int arr[], int a, int b) { if (a >= b) return; int key = arr[a]; int i = a + 1, j = b; while (i < j) { while (i < j && arr[j] >= key) --j; while (i < j && arr[i] <= key) ++i; if (i < j) swap(arr, i, j); } if (arr[a] > arr[i]) { swap(arr, a, i); quicksort0(arr, a, i - 1); quicksort0(arr, i + 1, b); } else { // there is no left-hand-side quicksort0(arr, a + 1, b); } } void quicksort(int arr[], int len) { quicksort0(arr, 0, len - 1); } int main() { int a1[] = { }; int a2[] = { 1 }; int a3[] = { 1, 1 }; int a4[] = { 1, 2, 3, 4, 5 }; int a5[] = { 5, 4, 3, 2, 1 }; int a6[] = { 9, 2, 6, 7, 5, 4, 0, 2, 7, 5 }; quicksort(a1, 0); quicksort(a2, 1); quicksort(a3, 2); quicksort(a4, 5); quicksort(a5, 5); quicksort(a6, 10); quicksort(a6, 10); } 

C ya viene con la función qsort que hace quicksort.

¿Por qué?

 arr[j]=key; 

Porque deberías poner tu pivote solo una vez en el lugar de popper.

y llamando

  quicksort(arr,a,index); quicksort(arr,index,b); 

También huele, porque tienes el mismo índice bajo y alto.

Mira este gran video en qucksort de google (incluye gran cantidad de códigos y explicaciones)

https://www.youtube.com/watch?v=aMnn0Jq0J-E