[Algorithm] Cell Sort | SUMFIのBlog

Cell Sort

셀 정렬은 삽입정렬이 이미 정렬된 상태에서 정렬을 수행할 경우 속도가 우수하다는 근거를 기반으로 개발이 되었다
삽입정렬을 수행하기 전 일정 간격을 기준으로 배열의 엔티티를 묶고 삽입정렬을 수행한다
해당 간격에 대해 정렬이 완료되면 간격의 크기를 줄여가며 반복하고 어느정도 정렬이 완료되었다 판단되면 간격 기준 삽입정렬이 아닌 전체 삽입정렬로 정렬을 완료한다
일정 간격의 크기는 Gap이라고 부르며 연구 결과를 토대로 말하면 대체로 홀수의 간격을 가지는게 좋다

Gap Size Example : 1, 4, 10, 23, 57, 132, 301, 701, 1750

동작 원리

오름차순 정렬 기준

Gap의 크기를 결정한다
Gap의 크기를 기준으로 삽입 정렬을 수행한다
예를들어 Gap의 크기가 3이라고 가정하고 배열의 전체 크기가 10일 때
묶음으로 가져지는 배열은 다음과 같다
List 1 : Array[0], Array[3], Array[6], Array[9]
List 2 : Array[1], Array[4], Array[7]
List 3 : Array[2], Array[5], Array[8]
Gap의 크기를 줄여가며 정렬을 반복한다
일정 기준이 되면 전체 삽입 정렬을 수행한다

구현

#include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>
#include <cstdlib>
#include <random>
#include <numeric>

using namespace std;

inline void CellSort(vector<int> &cellSortVec, int &_start, int &Gap){
    for(int start = _start + Gap; start < cellSortVec.size() ; start += Gap){
        int temp = cellSortVec[start];
        int compare = start - Gap;
        //삽입정렬의 최적화 방법 중 하나
        //매 단계마다 SWAP을 하는 대신 기준 엔티티를 메모리에 올려둔 후 적절한 위치에 도달하면 삽입을 수행한다
        for(;compare>=_start && cellSortVec[compare] > temp; compare -= Gap) {
            cellSortVec[compare + Gap] = cellSortVec[compare];
        }
        cellSortVec[compare+Gap] = temp;
    }
}

void CellSort(vector<int> &cellSortVec){
    int Gap = cellSortVec.size() >> 1;
    while(Gap){
        if(!(Gap&1)) // Gap%2 == 0
            Gap^=1;  // Gap++
        for(int start = 0; start < Gap; start++)
            CellSort(cellSortVec,start,Gap);

        Gap>>=1;    // Gap /= 2
    }
}


int main() {
    std::srand ( unsigned ( std::time(0) ) );
    vector<int> vec(1000);
    iota(begin(vec),end(vec),1);
    std::shuffle(std::begin(vec), std::end(vec), default_random_engine {});
    cout<<"Before Cell Sorting"<<endl;
    for(auto it : vec)
        cout<<it<<" ";
    cout<<endl;

    CellSort(vec);

    cout<<"After Cell Sorting"<<endl;
    for(auto it : vec)
        cout<<it<<" ";
    return 0;
}

Cell Sort

동작 원리

구현

같이보기