정렬 알고리즘 / Sort Algorithm + C구현

Bubble Sort Algorithm,버블정렬 알고리즘]

-버블 정렬은 1st index와 2nd index, 그리고 3rd index를 교환하는 방식을 반복하는 Sort Algorithm이다. 

1회전 수행 후 , element값이 가장 큰 index가 가장 후위로, element값이 가장 작은 index는 가장 전위로 배치된다.

-장점 : 구현이 매우 간단하므로 차지하는 용량이 비교적 작다

-단점 : 하나의 element가 전위로 나오기 위해서는 배열에서 모든 다른 element들과 교환돼야 한다. 따라서, 정렬되는 시간이 매우 오래걸리며, 일반적으로 Swap이 Move보다 복잡하다.

 

Select Sort Algorithm,선택정렬 알고리즘]

-선택 정렬은 1st index와 ((i+1))th index를 비교하여 정렬하는 알고리즘이다. 이 과정을 마지막 index까지 반복하여 배열을 정렬한다. 

11회전시, 가장 작은 element가 가장 전위 Index로 배치된다.

-장점 : 자료 이동 횟수가 [배열의 길이-1]로 미리 결정된다. 즉, 시간 효율성을 알고리즘 활용 전에 파악할 수 있다.

-단점 : 같은 record가 있는 경우, 상대적인 위치가 변경될 가능성이 있다.

 

Insertation Sort Algorithm,삽입정렬 알고리즘]

-삽입 정렬은 배열의 모든 element를 앞에서부터 차례대로 정렬된 부분과 비교하여 자신의 위치를 찾아 삽입하는 알고리즘이다. 이 과정을 다회 반복하여 배열을 정렬한다.

-장점 : 앞선 알고리즘에 비해 안정된 정렬 방식이다. 알고리즘 자체가 매우 간단하므로 record 수가 적으면 매우 유리한 알고리즘이다.

-단점 : Record의 수가 많을 경우, 과정이 복잡하므로 시간효율성이 상대적으로 떨어진다.

 

Bubble Sort 구현-C]

#include <stdio.h>

void bubble_Sort(int arr[], int n){
    int temp;

    //0~i-1까지 반복
    for(int i=n-1; i>0; i--){
        //j번째 index와 j+1번째의 index가 크기순이 아니면 교환
        for(int j=0; j<i; j++){
            if(arr[j]>arr[j+1]){
                temp=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=temp;
            }
        }
    }
}

 

Select Sort구현-C]

void SelectSort(int arr[], int n){
    int temp;
    for(int i=0; i<n-1; i++){
        int min=i;
        //최소값 찾기
        for(int j=i+1; j<n; j++){
            if(arr[j]<arr[min])
                min=j;
        }

        //최소값과 index교환
        temp=arr[i];
        arr[i]=arr[min];
        arr[min]=temp;
    }
}

Insert Sort구현-C]

#include <stdio.h>

void InsertSort(int arr[], int n){
    for(int i=1; i<n; i++){
        int key=arr[i];
        int j=i-1;

        //앞쪽 원소들과 비교
        while(j>=0 && arr[j]>key){
            //뒤로 밀기
            arr[j+1]=arr[j];
            j--;
        }
        arr[j+1]=key; //정렬로 삽입
    }
}