기본기)정렬)c#) 셸 정렬(Shell Sort)

셸 정렬(Shell Sort)

가장 오래된 정렬 알고리즘 중 하나로 삽입 정렬의 단점을 보완한 알고리즘이다.

삽입 정렬이 어느 정도 정렬된 배열에 대해서는 빠른 것에 단점을 보안해서 만든 것으로 

정렬해야 할 노드의 리스트를 k번째 요소를 추출해서 부분 리스트를 만든다. 이때 간격(Gap)을 기준으로 부분 리스트를 순차적으로 만든다.

반응형

간격의 초기값은 정렬할 크기 / 2, 생성된 부분 리스트 개수는 grap과 같다.

각 회전마다 간격 k를 절반으로 줄이면서 회전이 반복될 때마다 부분 리스트에 포함된 값은 증가한다.

gap은 홀수로 하는 것이 좋다.

gap이 1이 될때까지 반복한다.

 

배열 10, 8, 6, 20, 4, 3, 22, 1, 0 , 15, 16을 정렬할 때를 예시로 보면 다음과 같다.

코드는 다음과 같다.

public void SetShellSort(List<int> _list){
        int sortCount = 0;

        List<int> saveList = _list;
        int gap = (_list.Count/2);

        while(true){
            saveList = this.SheelSortList(saveList, gap);
            if(gap == 1){
                break;
            }
            gap = (gap/2);
        }
    }
    
    private List<int> SheelSortList(List<int> _list, int _divisionCount){
        
        List<int> returnValue = new List<int>();

        if(_divisionCount % 2 == 0){
            _divisionCount++;
        }

        //Logger.LogFormat("[Sheel Sort] Gap : {0}",_divisionCount);
      
        if(_divisionCount >1){
            int count = (_list.Count / _divisionCount);
            if(count * _divisionCount < _list.Count){
                count++;
            }

            List<List<int>> tempList = new List<List<int>>();
            for(int i = 0; i<count;i++){
                tempList.Add(new List<int>());
            }

            int index = 0;  //Set Value
            for(int i = 0; i< _list.Count;i++){
                if(tempList[index].Count == _divisionCount){
                    index++;
                }
                tempList[index].Add(_list[i]);
            }


            for(int i = 0; i<_divisionCount;i++){
                for(int j =0; j < count -1;j++){

                    if(tempList[j+1].Count-1 < i){
                        continue;
                    }

                    if(tempList[j][i] > tempList[j+1][i]){
                        int tempValue = tempList[j][i];
                        tempList[j][i] = tempList[j+1][i];
                        tempList[j+1][i] = tempValue;
                    }
                }
            }

        
            for(int i =0 ;i< tempList.Count;i++){
                for(int j =0; j< tempList[i].Count;j++){
                    returnValue.Add(tempList[i][j]);
                }
            }
        }
        else{
           //삽입정렬
             int j, key;
            for(int i = 1; i < _list.Count;i++){
                  key = _list[i];
                  for(j = i-1; (j >=0 && _list[j]> key); j--){
                      _list[j + 1] = _list[j];
                  }

                  _list[j + 1 ] =key;
              }
              returnValue = _list;
          }
        }

        this.DebugText(returnValue);

        return returnValue;
    }

셸 정렬의 특징은 여러 부분 리스트(Sub List)로 분리해서 정렬을 수행한다는 것이 특징이다.

 

시간 복잡도 : O(n)

공간 복잡도: 최선 O(N log N) , 평균 O (N^1.5), 최악 O(N^2)

 

 ★★☆☆☆