Algoritmos de ordenação

Algoritmos de ordenação

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 )
    {
        for( int p = 1; p < a.length; p++ )
        {
            Comparable tmp = a[ p ];
            int j = p;

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

2. Implementação do algoritmo Heap Sort

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

    private static int leftChild( int i )
    {
        return 2 * 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 - 1 && a[ child ].compareTo( a[ child + 1 ] ) < 0 )
                child++;
            if( tmp.compareTo( a[ child ] ) < 0 )
                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 - 1 );
    }
    
    /**
     * 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 ] ) <= 0 )
                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
        for( int 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 )
    {
        for( int gap = a.length / 2; gap > 0;
                     gap = gap == 2 ? 1 : (int) ( gap / 2.2 ) )
            for( int 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;
            }
    }