bi-directional sweep sort

bi-directional sweep sort

1.소스

/* bisweepsort.c by mwberryman on metalshell.com
 *
 * Based on the sort algorithm in bubblesort.c which is
 * as simple as it gets in the sorting business.
 *
 * Added basic improvements to make a bi-directional sweep
 * sort.  Added check to short-circuit sort operation as soon
 * as the program detects that the array is sorted.  Limit
 * sweeping of values to the unsorted middle of the array.
 *
 * Also added some debugging messages so one can follow the
 * progress of a sort.
 *
 * http://www.metalshell.com/
 *
 */

#include <stdlib.h>
#include <stdio.h>
#include <time.h>

#define ARRAY_SIZE 20

void print_array( int *arrary )
{
    int x;
    for( x = 0; x < ARRAY_SIZE ; x++ )
    {
        if( x!= ARRAY_SIZE -1 ){
        
            fprintf( stdout, "%d, ", arrary[x]);

        }else{
        
            fprintf( stdout, "%d\n", arrary[x]);
        }
    }
}

int main( int argc , char ** argv )
{
    int iarray[ARRAY_SIZE];
    int x,y, holder;
    
    // seed rand()
    srand(( unsigned int ) time( NULL ));

    for( x = 0; x < ARRAY_SIZE ; x++ )
    {
        iarray[x] = (int)(rand() % 100 );
    }

    fprintf( stdout , "before sort \n ");
    print_array( iarray );
    printf("n");


    // Bubble sort method with bi-directional sweeping.
    //
    // Check after each sweep if any more sweeps need
    // to be done. If any sweep results in no movement
    // of values then the array is sorted so short_circuit
    // the sort operation.
    //
    // After each sweep reduce the upper or lower limit
    // of array which must be swept.


    int ul=ARRAY_SIZE;
    int ll=0;
    int sorted=1;

    for(x = ll; x < ARRAY_SIZE; x++) 
    {

        /* Sweep largest value to end */
        printf("x=%d\n",x);
        sorted=1;
        for(y = ll; y < ul-1; y++) {

            printf("y=%d ",y);

            if(iarray[y] > iarray[y+1]) {

                holder = iarray[y+1];
                iarray[y+1] = iarray[y];
                iarray[y] = holder;
                sorted=0;
            }
        }

        printf("\n");
        print_array(iarray);

        /* short circuit the process if array is now sorted */
        if (sorted) { 
    
            printf("Found sorted A\n"); break; 
        }


        /* Reduce upper limit on array since the larger values have
        been swept to the end. */
        ul--;


        /* Bubble smallest value to beginning */

        sorted = 1;

        for(y = ul-1; y > ll; y--) {

            printf("y=%d ",y);

            if(iarray[y] < iarray[y-1]) {

                holder = iarray[y-1];
                iarray[y-1] = iarray[y];
                iarray[y] = holder;
                sorted=0;
            }
        }

        printf("\n");
        print_array(iarray);

        /* short circuit the process if array is now sorted */
        if (sorted) { 

            printf("Found sorted B\n"); break; 

        }

        /* Increase lower limit on array since the smaller values have */
        /* been swept to the beginning.                                */

        ll++;
    } // end for

    fprintf(stdout, "\nAfter Sort\n---------------\n");
    print_array(iarray);


return 0;
}

결과

hacker@ubuntu:~/c$ gcc -o bisweepsort bisweepsort.c 
hacker@ubuntu:~/c$ 
hacker@ubuntu:~/c$ 
hacker@ubuntu:~/c$ 
hacker@ubuntu:~/c$ ./bisweepsort 
before sort 
 97, 33, 93, 90, 37, 44, 99, 15, 93, 24, 57, 27, 51, 62, 40, 78, 16, 0, 84, 1
nx=0
y=0 y=1 y=2 y=3 y=4 y=5 y=6 y=7 y=8 y=9 y=10 y=11 y=12 y=13 y=14 y=15 y=16 y=17 y=18 
33, 93, 90, 37, 44, 97, 15, 93, 24, 57, 27, 51, 62, 40, 78, 16, 0, 84, 1, 99
y=18 y=17 y=16 y=15 y=14 y=13 y=12 y=11 y=10 y=9 y=8 y=7 y=6 y=5 y=4 y=3 y=2 y=1 
0, 33, 93, 90, 37, 44, 97, 15, 93, 24, 57, 27, 51, 62, 40, 78, 16, 1, 84, 99
x=1
y=1 y=2 y=3 y=4 y=5 y=6 y=7 y=8 y=9 y=10 y=11 y=12 y=13 y=14 y=15 y=16 y=17 
0, 33, 90, 37, 44, 93, 15, 93, 24, 57, 27, 51, 62, 40, 78, 16, 1, 84, 97, 99
y=17 y=16 y=15 y=14 y=13 y=12 y=11 y=10 y=9 y=8 y=7 y=6 y=5 y=4 y=3 y=2 
0, 1, 33, 90, 37, 44, 93, 15, 93, 24, 57, 27, 51, 62, 40, 78, 16, 84, 97, 99
x=2
y=2 y=3 y=4 y=5 y=6 y=7 y=8 y=9 y=10 y=11 y=12 y=13 y=14 y=15 y=16 
0, 1, 33, 37, 44, 90, 15, 93, 24, 57, 27, 51, 62, 40, 78, 16, 84, 93, 97, 99
y=16 y=15 y=14 y=13 y=12 y=11 y=10 y=9 y=8 y=7 y=6 y=5 y=4 y=3 
0, 1, 15, 33, 37, 44, 90, 16, 93, 24, 57, 27, 51, 62, 40, 78, 84, 93, 97, 99
x=3
y=3 y=4 y=5 y=6 y=7 y=8 y=9 y=10 y=11 y=12 y=13 y=14 y=15 
0, 1, 15, 33, 37, 44, 16, 90, 24, 57, 27, 51, 62, 40, 78, 84, 93, 93, 97, 99
y=15 y=14 y=13 y=12 y=11 y=10 y=9 y=8 y=7 y=6 y=5 y=4 
0, 1, 15, 16, 33, 37, 44, 24, 90, 27, 57, 40, 51, 62, 78, 84, 93, 93, 97, 99
x=4
y=4 y=5 y=6 y=7 y=8 y=9 y=10 y=11 y=12 y=13 y=14 
0, 1, 15, 16, 33, 37, 24, 44, 27, 57, 40, 51, 62, 78, 84, 90, 93, 93, 97, 99
y=14 y=13 y=12 y=11 y=10 y=9 y=8 y=7 y=6 y=5 
0, 1, 15, 16, 24, 33, 37, 27, 44, 40, 57, 51, 62, 78, 84, 90, 93, 93, 97, 99
x=5
y=5 y=6 y=7 y=8 y=9 y=10 y=11 y=12 y=13 
0, 1, 15, 16, 24, 33, 27, 37, 40, 44, 51, 57, 62, 78, 84, 90, 93, 93, 97, 99
y=13 y=12 y=11 y=10 y=9 y=8 y=7 y=6 
0, 1, 15, 16, 24, 27, 33, 37, 40, 44, 51, 57, 62, 78, 84, 90, 93, 93, 97, 99
x=6
y=6 y=7 y=8 y=9 y=10 y=11 y=12 
0, 1, 15, 16, 24, 27, 33, 37, 40, 44, 51, 57, 62, 78, 84, 90, 93, 93, 97, 99
Found sorted A

After Sort
---------------
0, 1, 15, 16, 24, 27, 33, 37, 40, 44, 51, 57, 62, 78, 84, 90, 93, 93, 97, 99
hacker@ubuntu:~/c$