sort( Bubble sort , Insertion sort , Selection sort , and Qsort)

1.  bubble sort

필요한 그림 : (array에 맨앞 index start ,맨 뒤 index end , 움직이는 index : index )

시간 복잡도 

:

 O(N^2)

(오름 차순 정렬일 때,)

가장 큰 값 부터 가장 작은 값 까지 차례로 오른쪽에 한 개씩 정렬해나가는 방법이다.
stable sort이다.

 

※ stable sort 란
같은 값들이 array에 있을 때, sort 전의 같은 값들끼리의 순서가 sort후에도 보장된다는 것이다.
예를 들어 sort 전 1 3 1 2 5 의 어레이가 있다고 했을 때 sort 후 1 1 2 3 5 가 될 텐데
stable sort를 했다면 sort 전 맨 앞의 1 이 sort 후 맨앞의 1 이되고,
unstable sort를 했다면 sort 전 맨앞의 1 이 sort 후에도 맨앞의 1이 된다는 보장을 할 수 없다는 것이다.

알고리즘
:
① index를 start 에서 end-1 까지 옮겨 가면서 index번째 값과 index+1 번째 값을 비교한다.

- 두 값을 비교하면서 더 큰 값이 index+1 번째에 있도록 한다. 이 과정을 start에서 end-1까지 하게 되면 end에 가장 큰 값이 위치하게 된다.

 

② 이 과정을 array size 만큼 반복하면 정렬이 된다.

연산 속도를 높이는 장치 설정
:
① <알고리즘 ① 과정>이 끝나고 end를 -1 만큼 줄인다.

- 왜 그러는지 예를 들어 보면 <알고리즘 ① 과정> 을 한 번 마치고 두 번째 반복할 때는 두 번째 가장 큰 수가 end-1에 위치할 것이다.(이미 첫 번째 반복에서 가장 큰수가 end 위치에 있기 때문에)
(두번째 반복 index에 end-1이 들어 갔을 경우) 불필요하게 가장 큰 수와 비교를 하게 된다.
과정이 거듭될 수록 불필요한 비교는 늘어갈 수 있다.
이런 불필요한 연산을 없애기 위해 end를 -1 씩 줄여 나간다.

 

② <알고리즘 ② 과정 중>, 정렬이 다 되서 반복이 더 이상 필요없다면 for문을 탈출한다.

- <알고리즘 ② 과정>을 array size만큼 반복 한다고 했는데, 그 만큼의 반복보다 적게 반복해도 sort가 완료되는 array들의 경우
sort가 완료되었음을 확인하고 반복 중간에 for문을 탈출하는 장치를 만든다.
sort가 완료 되었음을 확인 하는 방법은 간단하다.
정렬이 되어있는 array에서 알고리즘 ① 과정을 진행한다고 생각해보자.
index에 start 부터 end-1까지 옮겨가며 비교를 하겠지만, 값을 바꾸는 실행은 일어나지 않을 것이다.
왜냐하면 항상 index+1의 값이 index의 값보다 크기 때문이다.(오름차순 기준.)
이렇게 한번도 값을 바꾸는 실행이 일어나지 않으면 정렬이 완료되었다고 이해하고 반복을 종료한다.

Coding

 

template <typename T>
// 1. bubble sort
void bubblesort(T* a , int a_size , bool(*comp)(T a, T b)){
    if(a_size == 0 || a_size == 1) return ;

    bool sorted_check = true;
    int decreasing_size = a_size-1;

    for(int i = 0 ; i < a_size-1 ; i++){
        for(int j = 0 ; j < decreasing_size ; j++){
            if(!comp(a[j],a[j+1])) {
                sorted_check = false; // false means not yet sort completed.
                swap(a[j],a[j+1]);
            }
        }
        if(sorted_check) break; // if sort is completed , break. 연산 속도를 높이는 장치 ②
        sorted_check = true;
        decreasing_size--; // 연산 속도를 높이는 장치 ①
    }

}

2. insertion sort

필요한 그림 : (array에 옮겨가는 index : index , start index : start , end index : end , start~index : comparision array)

(오름차순기준) index를 start부터 end까지 이동하면서 start~ index 까지의 값들을 정렬해나가는 방법이다.
stable sort이다.

 

시간 복잡도 

:

 O(N^2)

알고리즘
:
① index를 자신의 앞 순서에 있는 값들(comparision array) 사이에 알맞은 위치에 집어 넣는다.

 

- 즉, 정렬된 start 부터 index-1 까지 값들 사이에 index의 값을 알맞은 위치에 집어넣는다.

 

② index를 start 부터 end까지 반복한다.

연산 속도를 높이는 장치 설정
:
①index를 start부터 시작 하지 않고 start+1 부터 시작한다.

 

 - index가 start일 때는 어차피 값이 1개 이기때문이다.

 

②vector를 사용한다.

 

- 값을 erase하거나 insert 하는 부분이 있기 때문에 정적 어레이 에서는 시간이 오래걸린다.

Coding

 

// 2. insertion sort
template <typename T>
vector<char> insertionsort(T* a, int a_size ,bool(*comp)(T a , T b)){    
    
    vector<T> v;
    for(int i = 0 ; i < a_size ; ++i){
        v.push_back(a[i]); // copy array to vector
    }
    
    if(v.size() == 0 || v.size() == 1){
        return v;
    }

    for(int end = 1; end < v.size() ; ++end){
        for(int start = 0 ; start < end ; ++start){
            if(comp(v[end],v[start])){ 
                v.insert(v.begin() + start , v[end]); 
                v.erase(v.begin() + end + 1);
            }
        }
    }

    return v;
}

3. selection sort

(오름 차순 기준) 가장 작은 값부터 가장 큰값 까지 순서대로 하나 씩 sort하는 방법이다.
unstable sort이다.

시간 복잡도

:

O(N^2)

알고리즘
:
① 가장 작은 값을 찾아내서 1번째 값과 바꾼다.

② 그 다음 2번 째 작은 값을 찾아내어 2번째 값과 바꾼다.
③ ①,② 같은 방법을 array size 만큼 시행 한다. (n번째 작은 값을 n번째 값과 바꾼다.)

연산 속도를 높이는 장치 설정
:
① n 번째 작은 값을 찾을 때는 array의 n-1 index부터 찾는다.

 

- n-1번째 작은 값까지 0~ n-2 index에 정렬되어 저장되어 있기 때문이다.
- 그리고 이 방법을 사용하기 때문에 항상 가장 작은 값을 찾는 장치를 만들어 두면 된다.
이게 무슨 말인지는 예를 들어 설명하겠다.
n번째 작은 값을 찾는다고 예를 들겠다.
이미 1~n-1 번째 작은 값들은 array index 0~ n-2 까지 찾아져서 정렬되어 있을 것이다.
우리는 n 번째 작은 값을 array의 n-1 index 부터 찾기 때문에 n번째 작은 값은 찾는 범위에서 가장 작다.
그래서 우리는 찾는 범위에서 가장 작은 값을 찾는 장치를 만들면 된다.

Coding

 

// 3. selection Sort

template <typename T>
void selectionsort(T *a , int a_size , bool(*comp)(T a, T b)){
    if(a_size == 0 || a_size == 1) return ;
    
    for(int start = 0 ; start < a_size-1 ; ++start){
        T min_or_max = a[start]; // a[start] is value of index N.
        
        int index = start;  // index of N.
    
        for(int search = start+1 ; search < a_size ; search++ ){
            if(!comp(min_or_max , a[search])){ // finding min or max value and index.
                min_or_max = a[search];
                index = search;
            }
        }
        swap(a[start],a[index]);
    }


}

4. Qsort (Quick sort)

피벗(pivot)을 사용하여서 효과적으로 정렬할 수 있는 정렬기법.

 

시간 복잡도 

: 

O(NlogN) 최악에는 O(N^2)

알고리즘
:
①먼저 피벗 엘레멘트를 정하고 그걸 기준으로 한쪽은 피벗엘레멘트 보다 작은 값들은 왼쪽 ,  큰 값들은 오른쪽에 모아둔다.
그리고 피벗 엘레멘트의 알맞은 위치로 피벗엘레멘트를 옮긴다.

②피벗 값을 기준으로 index 0~피벗 바로왼쪽 , index 피벗 바로오른쪽~ 마지막 를 범위 지정하여 두 번의 qsort를 또 진행한다.(단 , 지정 범위에서 정렬이 되어 있다면 그 지정 범위에서는 qsort를 진행하지 않는다.)

③이 것을 반복한다.(recursion을 사용한다.)

Coding

// 4. Quick sort
template <typename T>
bool less(T a , T b) { return a<b; } 

template <typename T>
void swap(T* a , int i , int j) { T t = a[i]; a[i] = a[j]; a[j] = t; }

template <typename T>
int partition(T *a ,int lo , int hi){
    int i = lo;
    int j = hi+1;

    while(1){
        while(::less( a[++i] ,a[lo]))
            if(i==hi) break;
        while(::less(a[lo],a[--j]))
            if(j==lo) break;

        if(i >= j) break;
        swap(a,i,j);

    }
    swap(a,lo,j);
    return j;

}

template <typename T>
void Quicksort(T *a ,int lo, int hi){
    if(hi <= lo) return;


    int j =partition(a,lo,hi);

    Quicksort(a,lo,j-1); // recursion lo ~ before pivot.
    Quicksort(a,j+1,hi); // recursion after pivot ~ hi.

}