quicksort una parte

bien aqui estan estas funciones

Código:

void swapE( int *array, int posA, int posB )
{
int temp = array[ posA ];
array[ posA ] = array[ posB ];
array[ posB ] = temp;
}

void partition( int *array, int size )
{
int currentE = 0;

for( int i = size - 1; i > 0; i-- )
{
if( array[ i ] < array[ currentE ] );
{
swapE( array, i, currentE );
return;
}
}
}

digamos que tengo este array

int unsortedAr[ 10 ] = { 37, 2, 6, 4, 89, 8, 10, 12, 68, 45 };

y llamo a
partition( unsortedAr, 10 );

unsortedAr deberia kedar { 12, 2, 6, 4, 89, 8, 10, 37, 68, 45 };
pero keda { 45, 2, 6, 4, 89, 8, 10, 12, 68, 37 };

cual es el error?

Buenas...

Ese me suena mas a bublesort mas que a quicksort. El quicksort toma un elemento como pivote y deja a cada lado de este los menores y mayores y hace lo mismo para ambas particiones. Busca en wiki que hay un algoritmo bastante bueno

Salu2, FreakMind

bien primero ya tengo internet y computadora otra ves asi que ya posteare mas seguido, como antes =P

(Quicksort) You have previously seen the sorting techniques of the bucket sort and selection sort. We now present the recursive sorting technique called Quicksort. The basic algorithm for a single-subscripted array of values is as follows:

Partitioning Step: Take the first element of the unsorted array and determine its final location in the sorted array (i.e., all values to the left of the element in the array are less than the element, and all values to the right of the element in the array are greater than the element). We now have one element in its proper location and two unsorted subarrays.

Recursive Step: Perform Step 1 on each unsorted subarray.

Each time Step 1 is performed on a subarray, another element is placed in its final location of the sorted array, and two unsorted subarrays are created. When a subarray consists of one element, that subarray must be sorted; therefore, that element is in its final location.

The basic algorithm seems simple enough, but how do we determine the final position of the first element of each subarray? As an example, consider the following set of values (the element in bold is the partitioning elementit will be placed in its final location in the sorted array):

37 2 6 4 89 8 10 12 68 45

Starting from the rightmost element of the array, compare each element with 37 until an element less than 37 is found. Then swap 37 and that element. The first element less than 37 is 12, so 37 and 12 are swapped. The values now reside in the array as follows:

12 2 6 4 89 8 10 37 68 45

Element 12 is in italics to indicate that it was just swapped with 37.

--------------------------------------------------------------------------------

[Page 472]
Starting from the left of the array, but beginning with the element after 12, compare each element with 37 until an element greater than 37 is found. Then swap 37 and that element. The first element greater than 37 is 89, so 37 and 89 are swapped. The values now reside in the array as follows:

12 2 6 4 37 8 10 89 68 45

Starting from the right, but beginning with the element before 89, compare each element with 37 until an element less than 37 is found. Then swap 37 and that element. The first element less than 37 is 10, so 37 and 10 are swapped. The values now reside in the array as follows:

12 2 6 4 10 8 37 89 68 45

Starting from the left, but beginning with the element after 10, compare each element with 37 until an element greater than 37 is found. Then swap 37 and that element. There are no more elements greater than 37, so when we compare 37 with itself, we know that 37 has been placed in its final location of the sorted array.

Once the partition has been applied to the array, there are two unsorted subarrays. The subarray with values less than 37 contains 12, 2, 6, 4, 10 and 8. The subarray with values greater than 37 contains 89, 68 and 45. The sort continues with both subarrays being partitioned in the same manner as the original array.

Based on the preceding discussion, write recursive function quickSort to sort a single-subscripted integer array. The function should receive as arguments an integer array, a starting subscript and an ending subscript. Function partition should be called by quickSort to perform the partitioning step.

no busco algoritmos para ordenar solo es para resolver esto

Buenas

Si te entendi bien, lo que vos queres hacer es una sola pasada del quicksort, es decir, hacer la primera particion.

Cita de: lann en Enero 18, 2008, 01:12:04

You have previously seen the sorting techniques of the bucket sort and selection sort. We now present the recursive sorting technique called Quicksort.

Que sea recursivo significa que el algoritmo va a hacer algo como esto
controlar_condicion_final
realizar_solucion_parcial
llamada_recursiva

Entonces, lo que vos necesitas es la parte de realizar_solucion_parcial

Referido a tu problema

Cita de: lann en Enero 17, 2008, 10:30:35

Código:

void partition( int *array, int size )
{
int currentE = 0;

for( int i = size - 1; i > 0; i-- )
{
if( array[ i ] < array[ currentE ] );
{
swapE( array, i, currentE );
return;
}
}
}

Aqui array es 45 y array[currentE] es 37. La condicion se cumple, por lo que 45 toma el lugar de 37 y viceversa, y la funcion retorna. Las condiciones son que el elemento sea mayor o menor al pivote (dependiendo de la particion)

Salu2, FreakMind

bueno lo que pide es que la funcion quickSort sea recursiva, pero las unicas funciones que cree fueron la de partition y la de swapE. la funcion quickSort llamara a la funcion iterativa partition.

como ke la condicion se cumple eso es lo ke se me hace medio raro y la vdd lo ke parece es ke ando muy despistado Tongue

pero si

array[ i latina ] es mayor a array[ currentE ] la condicion no se deberia cumplir... no se por que pero es asi como de lo mas simple y me etoy confundiendo

	Bienvenido(a), Visitante. Favor de ingresar o registrarse. ¿Perdiste tu email de activación? - Julio 26, 2008, 07:43:38 Boton Buscar