[ManHunter]

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!