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;
}
}