Dev - C++ - Quick sort

 
Vista:
Imágen de perfil de Sarah

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
Me gusta: Está pregunta es útil y esta claraNo me gusta: Está pregunta no esta clara o no es útil
0
Responder
Imágen de perfil de Alfil
Val: 4.344
Oro
Ha mantenido su posición en Dev - C++ (en relación al último mes)
Gráfica de Dev - C++

Quick sort

Publicado por Alfil (1444 intervenciones) el 09/06/2022 16:31:37
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#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] << " ";
    }
}
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar