Ordenamiento – Quick

Enunciado

El algoritmo elige un elemento del conjunto de elementos a ordenar, llamado pivote.
Se reubican los demás elementos del vector a cada lado del pivote, de manera que a un lado queden todos los menores que él, y al otro lado los mayores. Los elementos iguales al pivote pueden ser colocados tanto a su derecha como a su izquierda, dependiendo de la implementación deseada. De esta forma, el pivote ocupará exactamente el lugar que le corresponderá en el vector ordenado.
El vector queda separado en dos subvectores, uno formado por los elementos a la izquierda del pivote, y otro por los elementos a su derecha.
Este proceso se repite de forma recursiva para cada subvector mientras éstos contengan más de un elemento. Una vez terminado este proceso todos los elementos estarán ordenados.

Código

Python

def Quick( v, ini, fin ):
    i = ini ;
    j = fin ;
    m = ( i + j ) // 2 ;
    p = v[ m ] ;
    
    while True:   
        while v[ i ] > p and i < fin:
            i += 1
        while v[ j ] < p and j > ini:
            j -= 1
        if i <= j:
            aux = v[ i ]
            v[ i ] = v[ j ]
            v[ j ] = aux 
            i += 1 ; j -= 1
        if i > j: break
        
    if ini <= j: Quick( v , ini , j )
    if fin > i: Quick( v , i , fin )

def main():
    lista = [ 12, 18, 3, 22, 15, 48, 12 ]
    
    Quick( lista , 0 , len(lista)-1 )

    print( lista )
    
    input( "Presionar/Press Enter to exit " )
main()

C++

#include <iostream>
#include <iomanip>
using namespace std ;
#include <conio.h>

void Quick( float v[ ] , int ini , int fin )
{
   int i , j , m ; float p, aux ;
	
   i = ini ;
   j = fin ;
   m = ( i + j ) / 2 ;
   p = v[ m ] ;
   do
   {
       while ( v[ i ] > p && i < fin ) 
	   i++ ;
       while ( v[ j ] < p && j > ini ) 
	   j-- ;
       if ( i <=j )
       {
	   aux = v[ i ] ; 
	   v[ i ] = v[ j ] ; 
	   v[ j ] = aux ; 
	   i++ ; j-- ;
       }
   } while ( i <= j ) ;
   if ( ini <= j ) Quick( v , ini , j ) ;
   if ( fin > i ) Quick( v , i , fin ) ;
}

int main()
{
   int  i , n = 5 ;
   float v1[ 10 ] ;

   cout << "Ingresar 5 numeros/" ;
   cout << "Enter 5 numbers: " << endl ;
   for ( i = 0 ; i < n ; i++)
       cin >> v1[ i ] ;

   Quick( v1 , 0 , n-1 ) ;

   cout << "Vector ordenado/" ;
   cout << "Ordered vector" << endl ;
   for ( i = 0 ; i < 5 ; i++ )
       cout << setw(8) << v1[ i ] << endl ;
	
   cout << endl ;
   cout << "Presionar/Press Enter to exit " ;
   getch() ;
   return 0 ;
}

Pascal

program prueba ;
uses crt ;
const n = 5 ;
type
    rango = 0..n ;
    vectorReal = array [ 0..n ] of real ;
var
    i : rango ;
    v1 : vectorReal ;

procedure Quick( var v: vectorReal ; 
                 ini , fin: integer ) ;  
var
    i, j, m: integer ; p, aux: real ;
begin
    i := ini ; 
    j := fin ;
    m := ( i + j ) DIV 2 ;
    p := v[ m ] ;
    repeat
         while v[ i ] > p do i := i + 1 ;
         while v[ j ] < p do j := j - 1 ; 
         if i <= j 
         then
         begin
	     aux := v[i] ; v[i] := v[j] ; v[j] := aux ;
	     i := i + 1 ; j := j - 1 ;
         end ;
    until i > j ;
    if ini < j then Quick( v , ini , j ) ;
    if fin > i then Quick( v , i , fin ) ;
end ;

begin
    ClrScr ;
    write( 'Ingresar 5 numeros/' ) ;
    writeln( 'Enter 5 numbers: ' ) ;
    for i:=1 to n do
    begin
         readln( v1[ i ] ) ;
    end;
    writeln ;

    Quick( v1 , 1 , n ) ; 
    
    writeln( 'Vector ordenado/Ordered vector' ) ;
    for i:=1 to n do
        writeln( v1[ i ]:8:2 ) ;

    writeln ;
    writeln( 'Presionar/Press Enter to exit ' ) ;
    readln ;
end.

Diagramas