[C] Algoritmi di Ordinamento - Versione stampabile

Salve a tutti,

studiando per un esame, ho dovuto imparare alcuni algoritmi per l'ordinamento di strutture dati. Ho deciso, quindi, di condividere questi algoritmi in modo che possiate usarli e studiarli anche voi.

Download
http://www.multiupload.com/G0DWSW2448

Di seguito, il listato del codice che potete trovare all'interno dei file.

- Bubble Sort

Codice:
/*Bubble Sort*/

void bubbleSort( tInfo a[], int n ){

    int i, k;

    bool modified = true;

    for( k = 0; k < n - 1 && modified; k++ ){

        modified = false;

        for( i = 0; i < n - k - 1; i++ )

            if( greater( a[i], a[i + 1] ) ){

                swap( &a[i], &a[i + 1] );

                modified = true;

            }

    }

}

/*______________________________*/

Tale ordinamento ha una complessità computazionale nel caso generico di T(n^2).

- Selection Sort

Codice:
/*Selection Sort*/

int searchMin( tInfo a[], int n ){

    int i, min = 0;

    for( i = 0; i < n; i++ )

        if( !greater( a[i], a[min] ) )

            min = i;

    return min;

}

void selectionSort( tInfo a[], int n ){

    int i, min;

    for( i = 0; i < n - 1; i++ ){

        min = i + searchMin( a + i, n - i );

        if( min != i )

            swap( &a[i], &a[min] );

    }

}

/*_______________________________*/

Tale ordinamento ha una complessità computazionale nel caso generico di T(n^2).

- Merge Sort

Codice:
/*Merge Sort*/

void merge( tInfo a1[], int n1, tInfo a2[], int n2, tInfo dest[] ){

    int pos1 = 0, pos2 = 0, k = 0;

    while( pos1 < n1 && pos2 < n2 ){

        if( greater( a1[pos1], a2[pos2] ) )

            dest[k++] = a1[pos1++];

        if( greater( a2[pos2], a1[pos1] ) )

            dest[k++] = a2[pos2++];

    }

    while( pos1 < n1 )

        dest[k++] = a1[pos1++];

    while( pos2 < n2 )

        dest[k++] = a2[pos2++];

}

void mergeSort( tInfo a[], int n, tInfo tmp[] ){

    int i, m = n/2;

    if( n < 2 )

        return;

    mergeSort( a, m, tmp );

    mergeSort( a + m, n - m, tmp );

    merge( a, m, a + m, n - m, tmp );

    for( i = 0; i < n; i++ )

        a[i] = tmp[i];

}

/*_____________________________________*/

Tale ordinamento ha una complessità computazionale nel caso generico di T(n * log n).

- Quick Sort

Codice:
/*Quick Sort */

int partition( tInfo a[], int n ){

    int i, k = 1;

    for( i = 1; i < n; i++ )

        if( !greater( a[i], a[0] ) )

            swap( &a[k++], &a[i] );

    swap( &a[0], &a[k-1] );

    return k - 1;

}

void quickSort( tInfo a[], int n ){

    int k;

    if( n < 2 )

        return;

    k = partition( a, n );

    quickSort( a, k );

    quickSort( a + k + 1, n - k - 1 );

}

/*___________________________________*/

Tale ordinamento ha una complessità computazionale nel caso generico di T(n * log n).

Bye!