quick sort descendente

Foro de elhacker.net

Programación

Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)

quick sort descendente

0 Usuarios y 1 Visitante están viendo este tema.

Páginas: [1]

Autor

Tema: quick sort descendente (Leído 4,307 veces)

mari2diaz

Desconectado

Mensajes: 24

quick sort descendente

« en: 27 Enero 2023, 02:06 am »

tengo un error en el quick sort descendente pero no lo encuentro

Código

void swap(int &a,int &b){
	int aux = a;
	a = b;
    b = aux;
}
 
int particion(std::vector<int>& array, int inicio, int final){
	int piv = array[inicio];
	int i = inicio + 1;
	for(int j = i; j <= final; j++){
		if(array[j] > piv){
			swap(array[i], array[j]);
			i++;
		}
	}
	swap(array[inicio], array[i - 1]);
	return i - 1;
}
 
void quickSort(std::vector<int>& array, int inicio, int final){
	if(inicio < final){
		int piv = particion(array, inicio, final);
		quickSort(array, inicio, piv - 1);
		quickSort(array, piv + 1, final);
	}
}

esto es ejemplo d lo que aparece en pantalla
arreglo desordenado
10
3
4
9
7
1
5
8
2
6
ordenado
1066696018
10
9
8
7
6
5
4
3
2


	En línea

Serapis

Colaborador

Desconectado

Mensajes: 3.391

Re: quick sort descendente

« Respuesta #1 en: 31 Enero 2023, 21:54 pm »

Tu función 'partition' está incompleta...

Código:

entero = funcion Partition(entero array[], entero inicio, entero final)
    entero j, k, pivot

    pivot = array[inicio]
    j = pivot - 1
    k = final + 1
    
    Hacer //mientras true
        hacer
            j += 1
        Repetir mientras (array[j] < pivot)

        Hacer
            k -= 1
        Repetir mientras (array[k] > pivot)

        Si (j < k)
            swap(array, j, k)  // <--- nota* 
        sino
            devolver k
        Fin si
    Repetir
fin funcion

*nota: que yo paso el array y los índices, cámbialo al gusto...

Con este código, se debe cambiar ligeramente la función quicksort. En la línea

Código:

quickSort(array, inicio, piv - 1);

Borra el '-1', si no, dará algunos errores...

Es posible subsumir ambas funciones (Partition y Quicksort) en una sola, lo que lo hace más óptimo... la de 'swap' también ya que utiliza muy pocas líneas y se invoca desde un único sitio...

p.d.: Perdón el pseudocódigo es para un orden ascendente, no había caído en ese detalle. Mañana saco un tiempito para modificarlo (o mejor adjuntar otro pseudocódigo). ...aunque puedes intentar modificarlo tú mismo :silbar:


« Última modificación: 31 Enero 2023, 22:41 pm por Serapis »	En línea

Serapis

Colaborador

Desconectado

Mensajes: 3.391

Re: quick sort descendente

« Respuesta #2 en: 1 Febrero 2023, 23:49 pm »

Veo, que no hay feedback... en fin...

...en realidad convertir el pseudocódigo de mi mensaje previo para ordenar en descendente basta cambiar exclusivamente 2 caracteres, lo dejo ahí... Si discurres por tu cuenta, bien, y si no, ya contarás...


	En línea

Páginas: [1]

Ir a:

Mensajes similares
	Asunto	Iniciado por	Respuestas	Vistas	Último mensaje
	auxilio metodo de ordenamiento quick sort Java	genteseria	2	3,146	2 Julio 2007, 22:33 pm por alvk4r
	Algoritmos quick union y wighted quick union? Programación General	carlmycol	1	2,482	11 Septiembre 2014, 18:05 pm por rir3760
	bubble sort ascendente y descendente en un solo codigo Programación C/C++	Paul Young	7	5,042	7 Marzo 2016, 16:15 pm por engel lex
	ordenar por apellido ascendente, y por nombre descendente Programación C/C++	matiapache12	1	2,985	26 Octubre 2016, 18:08 pm por palacio29
	[C#] algoritmo quick sort .NET (C#, VB.NET, ASP)	amie-Reyna	3	3,567	19 Diciembre 2016, 15:38 pm por bvislao