
Quick sort
Publicado por Sarah (29 intervenciones) el 09/06/2022 02:57:38
Hola, alguien tendrá un ejercicio por el método de quick sort?
Valora esta pregunta


0
#include <iostream>
using namespace std;
void quicksort( int *array, int start, int end );
int divide( int *array, int start, int end );
void imprimir( int *array, int size );
int main(){
int size;
cout << "Tamanyo del array: "; cin >> size;
int a[size];
cout << "\nIntroduzca los valores del array:\n";
for (int i = 0; i < size; i++) {
cout << "(" << i << "/" << size << "): ";
cin >> a[i];
}
cout << "\nArray introducido:\n";
imprimir( a, size );
cout << endl << endl;
quicksort(a, 0, size - 1);
cout << "\nArray ordenado:\n";
imprimir( a, size );
cout << endl;
return 0;
}
//! 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);
}
}
//! 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;
}
void imprimir( int *array, int size ){
for (int i = 0; i < size; i++) {
cout << array[i] << " ";
}
}