SORT(버블,선택,삽입)

버블정렬(Bubble sort)

-인접한 데이터끼리 비교

-시간복잡도 O(n^2) => 최고:이미 정렬된 상태

                                => 최악:역순으로 정렬된 상태

ex)

#include<stdio.h>

#include<malloc.h>

int main(){

    int* arr;

    int i,j,n,temp;

    scanf("%d",&n);

    arr=(int*)calloc(n,sizeof(int));

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

        scanf("%d",arr+i);

    }

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

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

            if(arr[j]>arr[j+1]){

                temp=arr[j];

                arr[j]=arr[j+1];

                arr[j+1]=temp;

            }

        }

    }

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

        printf("%d",arr[i]);

    }

    printf("\n");

    

}

입력: 5 

         9 2 3 5 1

결과: 1 2 3 5 9

선택정렬(Selection sort)

- 배열 첫번째 위치부터 기준키로 설정

=>2~n번째 값과 비교 =>가장 작은 값과 기준키를 교환

-시간복잡도 O(n^2) => 최고:이미 정렬된 상태

                                => 최악:역순으로 정렬된 상태

ex)

#include<stdio.h>

int main(){

    int arr[10]={5,3,2,1,4,6,8,7,10,9};

    int i,j,temp,curr;

    for(i=0;i<9;i++){

        curr=i;

        for(j=i+1;j<10;j++){

            if(arr[curr]>arr[j]){

                curr=j;

            }

        }       

        if(arr[i]>arr[curr]){

            temp=arr[i];

            arr[i]=arr[curr];

            arr[curr]=temp;    

        }

    }

    for(i=0;i<10;i++){

        printf("%d ",arr[i]);

    }

    printf("\n");

    return 0;

}

결과값: 1 2 3 4 5 6 7 8 9 10

삽입정렬(Insertion sort)

-pivot을 잡고 그 전에 값들과 비교하면서 pivot보다 클 경우 오른쪽으로 한칸씩 이동한다.

시간복잡도 (http://i-bada.blogspot.kr/2012/05/blog-post_161.html)

- 최적 : 입력 데이터가 정렬하고자 하는 순서대로 배열되어 있는 경우 최소 비교 횟수 : n-1
- 최악 : 입력 데이터가 역순으로 정렬되어 있는 경우 최대 비교 횟수 : (n(n-1))/2
- 각 패스 별로 중간 정도에서 부분적인 정렬이 완료되었을 경우 평균 비교 횟수 : (n(n-1))/4
- n개의 레코드를 정렬한 때 n-1번 삽입이 발생되어 전체 수행시간 : O(n2)

예제

#include<stdio.h>

int main(){

    int arr[7]={7,2,8,1,3,9,4};

    int i,j,pivot;

    for(i=1;i<7;i++){

        pivot=arr[i];

        for(j=i-1;j>=0;j--){

            if(pivot<arr[j]){

                arr[j+1]=arr[j];

            }

            else{

                break;

            }    

        }

        arr[j+1]=pivot;      

    }

    for(i=0;i<7;i++){

        printf("%d ",arr[i]);

    }

    

}

결과값: 1 2 3 4 7 8 9

간단할 수 있지만 많은 생각을 요구함.

이제 자고 일어나서 generatic 하게 짤꺼임.

이 정렬 뿐만 아니라 다른 정렬들 설명 잘 되있는 사이트
http://yujuwon.tistory.com/entry/%EC%82%BD%EC%9E%85%EC%A0%95%EB%A0%ACInsert-Sort