Ordenamiento – Shell

Enunciado

Este método consiste en comparar elementos que se hallan a una cierta distancia que llamaremos salto en el algoritmo y en caso de no estar en el orden deseado se los intercambia de posición. Se elije como salto inicial la mitad entera de n. Cuando para un determinado salto ya no deben realizarse mas intercambios se repite el proceso dividiendo el salto por la mitad. El procedimiento finaliza cuando se llega a salto igual a 1.

Código

Python

def Shell( v ):
    n = len( v )
    salto = n
    while ( salto > 0 ):
        salto = salto // 2 
        while True:
            fin = True 
            k = n - salto 
            for i in range( k ):
                j = i + salto 
                if v[ i ] < v[ j ]:
                    aux = v[ i ]  
                    v[ i ] = v[ j ]  
                    v[ j ] = aux  
                    fin = False 
                
            if fin: break
    
def main():
    lista = [ 12, 18, 3, 22, 15, 48, 12 ]
    
    Shell( lista )

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

C++

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

void Shell ( int n , float v[ ] )
{
   int i, j, k, salto ; float aux ; bool fin ;

   salto = n ;
   while ( salto > 0 )
   {
      salto = salto / 2 ;
      do
      {
      	 fin = true ;
         k  = n - salto ;
         for ( i = 0 ; i < k ; i++ )
         {
            j = i + salto ;
            if ( v[ i ] < v[ j ] )
            {
            	aux = v[ i ] ; 
		v[ i ] = v[ j ] ; 
		v[ j ] = aux ; 
		fin = false ;
            }
         }
      }
      while ( !fin ) ;
   }
}

int main()
{
   int  i ;
   float v1[ 10 ] ;

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

   Shell( 5 , v1 ) ;

   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 Shell( n : rango ; var v : vectorReal ) ;
var 
    i, j, k, salto : rango ; 
    aux : real ; fin : boolean ;
begin
    salto := n ;
    while salto > 1 do
    begin
        salto := salto div 2 ;
        repeat
             fin := true ;
             k  := n - salto ;
             for i := 1 to k do
             begin
                 j := i + salto ;
                 if v [ i ] < v [ j ] 
                 then
                 begin
                     aux := v [ i ] ; 
                     v [ i ] := v [ j ] ; 
                     v [ j ] := aux ; 
                     fin := false
                 end
             end
        until fin
    end
end ;

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

    Shell( n , v1 ) ;
    
    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