Algoritmos de ordenação

Você precisa estar logado para dar um feedback. Clique aqui para efetuar o login
Para efetuar o download você precisa estar logado. Clique aqui para efetuar o login
Confirmar voto
0
 (8)  (2)

Veja nesta dica quatro algoritmos de ordenação (Insertion Sort, Heap Sort, Merge Sort e Shell Sort)

 

Veja nesta dica quatro algoritmos de ordenação (Insertion Sort, Heap Sort, Merge Sort e Shell Sort)

 

1. Implementação do algoritmo Insertion Sort

 

    /**
     * Algoritmo Insertion Sort.
     */
    public static void insertionSort( Comparable [ ] a )
    {
        forint p = 1; p < a.length; p++ )
        {
            Comparable tmp = a[ p ];
            int j = p;

            for( ; j > && tmp.compareTo( a[ j - ] ) < 0; j-- )
                a[ j ] = a[ j - ];
            a[ j ] = tmp;
        }
    }

 

 

2. Implementação do algoritmo Heap Sort

 

    /**
     * Algoritmo Heap Sort.
     */
    public static void heapsort( Comparable [ ] a )
    {
        forint i = a.length / 2; i >= 0; i-- )  /* buildHeap */
            percDown( a, i, a.length );
        forint i = a.length - 1; i > 0; i-- )
        {
            swapReferences( a, 0, i );            /* deleteMax */
            percDown( a, 0, i );
        }
    }

    private static int leftChild( int i )
    {
        return * i + 1;
    }

    private static void percDown( Comparable [ ] a, int i, int n )
    {
        int child;
        Comparable tmp;

        for( tmp = a[ i ]; leftChild( i ) < n; i = child )
        {
            child = leftChild( i );
            if( child != n - && a[ child ].compareTo( a[ child + ] ) < )
                child++;
            if( tmp.compareTo( a[ child ] ) < )
                a[ i ] = a[ child ];
            else
                break;
        }
        a[ i ] = tmp;
    }
    
    
    /**
     * Method para trocar elementos em um array.
     */
    public static final void swapReferences( Object [ ] a, int index1, int index2 )
    {
        Object tmp = a[ index1 ];
        a[ index1 ] = a[ index2 ];
        a[ index2 ] = tmp;
    }

 

 

3. Implementação do algoritmo Merge Sort

 

    /**
     * Algoritmo Merge Sort.
     */
    public static void mergeSort( Comparable [ ] a ) {
        Comparable [ ] tmpArray = new Comparable[ a.length ];
        mergeSort( a, tmpArray, 0, a.length - );
    }
    
    /**
     * Método interno que faz chamadas recursivas
     */
    private static void mergeSort( Comparable [ ] a, Comparable [ ] tmpArray,
            int left, int right ) {
        if( left < right ) {
            int center = ( left + right ) / 2;
            mergeSort( a, tmpArray, left, center );
            mergeSort( a, tmpArray, center + 1, right );
            merge( a, tmpArray, left, center + 1, right );
        }
    }
    
    /**
     * Metódo interno que ordena duas partes de um subarray.
     */
    private static void merge( Comparable [ ] a, Comparable [ ] tmpArray,
            int leftPos, int rightPos, int rightEnd ) {
        int leftEnd = rightPos - 1;
        int tmpPos = leftPos;
        int numElements = rightEnd - leftPos + 1;
        
        // loop principal
        while( leftPos <= leftEnd && rightPos <= rightEnd )
            if( a[ leftPos ].compareTo( a[ rightPos ] ) <= )
                tmpArray[ tmpPos++ ] = a[ leftPos++ ];
            else
                tmpArray[ tmpPos++ ] = a[ rightPos++ ];
        
        while( leftPos <= leftEnd )    
            tmpArray[ tmpPos++ ] = a[ leftPos++ ];
        
        while( rightPos <= rightEnd )  
            tmpArray[ tmpPos++ ] = a[ rightPos++ ];
        
        // Copiando o array temporário de volta
        forint i = 0; i < numElements; i++, rightEnd-- )
            a[ rightEnd ] = tmpArray[ rightEnd ];
    }

 

 

4. Implementação do algoritmo Shell Sort

 

    /**
     * Algoritmo Shell Sort.
     */

    public static void shellsort( Comparable [ ] a )
    {
        forint gap = a.length / 2; gap > 0;
                     gap = gap == : (int) ( gap / 2.2 ) )
            forint i = gap; i < a.length; i++ )
            {
                Comparable tmp = a[ i ];
                int j = i;

                for( ; j >= gap && tmp.compareTo( a[ j - gap ] ) < 0; j -= gap )
                    a[ j ] = a[ j - gap ];
                a[ j ] = tmp;
            }
    }

 
Você precisa estar logado para dar um feedback. Clique aqui para efetuar o login
Receba nossas novidades
Ficou com alguma dúvida?