ordenamiento quicksort con C++
C/Visual C
Publicado el 8 de Octubre del 2018 por Guajardo (21 códigos)
4.489 visualizaciones desde el 8 de Octubre del 2018
#include <iostream>
#include <stdio.h>
#include <stdlib.h> //libreria para usar rand
//By Guajardo Pandiella
void quicksort(int *array, int start, int end);
using namespace std;
int main()
{
int x;
int const MAX = 100;
cout<<"introduzca tamaño del arreglo= "<< endl;
cin>>x;
int arreglo[x];
for (int i = 0; i < x; i++) {
arreglo[i] = rand() % MAX;
}
cout << "Array antes de ordenarse: " << endl;
for (int i = 0; i < x; i++) {
cout << arreglo[i] << " ";
}
cout << endl << endl;
quicksort(arreglo, 0, x - 1);
cout << "Array ordenado " << endl;
for (int i = 0; i < x; i++ ){
cout << arreglo[i] << "-";
}
cout << endl << endl;
return 0;
}
// Función para dividir el array y hacer los intercambios
int divide(int *array, int start, int end) {
int left;
int right;
int pivot;
int temp;
pivot = array[start];
left = start;
right = end;
// Mientras no se cruzen los índices
while (left < right) {
while (array[right] > pivot) {
right--;
}
while ((left < right) && (array[left] <= pivot)) {
left++;
}
// Si todavía no se cruzan los indices seguimos intercambiando
if (left < right) {
temp = array[left];
array[left] = array[right];
array[right] = temp;
}
}
// Los índices ya se han cruzado, ponemos el pivot en el lugar que le corresponde
temp = array[right];
array[right] = array[start];
array[start] = temp;
// La nueva posición del pivot
return right;
}
// Función recursiva para hacer el ordenamiento
void quicksort(int *array, int start, int end)
{
int pivot;
if (start < end) {
pivot = divide(array, start, end);
// Ordeno la lista de los menores
quicksort(array, start, pivot - 1);
// Ordeno la lista de los mayores
quicksort(array, pivot + 1, end);
}
}
Comentarios sobre la versión: 1.0 (0)
No hay comentarios