쉬운 정렬 알고리즘

어려서 부터 사용하던 정렬 알고리즘입니다. (순차 정렬)
기본적으로는 N2(제곱)이라고 생각해서 버블이나 선택 삽입 정렬보다 쉽습니다.
이번기회에 정리해 보았습니다.

소스를 통해서 random data로 bubble sort와 비교해 보았습니다.

아주 근소한 차이지만 조금 더 빠르긴한데요 비슷한 성능만 나오기만 한다면 만족합니다.

외우기 쉽게 제작하였습니다.

기본적으로 루프를 2개 도는데 밖의 루프는 당연히 N까지 돌고 안쪽도 N까지 돕니다. 그리고 j의 시작은 i+1이며 비교대상은 data[i] data[j]를 비교해서 크거나 혹은 작거나 조건에 만족하면 swap을 하게 됩니다.

    int i,j;
    for(i=0;i<N_MAX;i++){
        for(j=i+1;j<N_MAX;j++){
            if(data[i]>data[j]){
                swap(i,j);
            }        
        }
    }

C, pasted 1 second ago:  #include <stdio.h> #include <stdlib.h> #include "time.h" #define N_MAX 10000 int datarand[N_MAX]; int dataresult[N_MAX]; int data[N_MAX]; int swap(int a,int b) { int temp; temp = data[a]; data[a]=data[b]; data[b]=temp; return 0; } int sort1() { int i,j; for(i=0;i<N_MAX;i++){ for(j=i+1;j<N_MAX;j++){ if(data[i]>data[j]){ swap(i,j); } } } printf("%d %d %d\n",data[0],data[N_MAX/2],data[N_MAX-1]); } int bubble() { int i,loop; for (loop = 0; loop < N_MAX - 1; loop++) { for (i = 0; i < N_MAX - 1 - loop; i++) { if (data[i] > data[i+1]) { swap(i,i+1); } } } printf("%d %d %d\n",data[0],data[N_MAX/2],data[N_MAX-1]); } int main() { int i; clock_t before; double result; for(i=0;i<N_MAX;i++){ datarand[i]=(int)(rand()%N_MAX); } memcpy(data,datarand,sizeof(data)); before = clock(); bubble(); result = (double)(clock() - before) / CLOCKS_PER_SEC; printf("%5.2f\n", result); memcpy(dataresult,data,sizeof(data)); memcpy(data,datarand,sizeof(data)); before = clock(); sort1(); result = (double)(clock() - before) / CLOCKS_PER_SEC; printf("%5.2f\n", result); if( memcmp(data,dataresult,sizeof(data))==0 ) printf("same\n"); memcpy(data,datarand,sizeof(data)); before = clock(); bubble(); result = (double)(clock() - before) / CLOCKS_PER_SEC; printf("%5.2f\n", result); if( memcmp(data,dataresult,sizeof(data))==0 ) printf("same\n"); return 0; } Output: 0 5054 9999 0.40 0 5054 9999 0.38 same 0 5054 9999 0.40 same