shell sort

 
########################## 
####    shell sort    #### 
########################## 
 
remember both bubble sort and insertion sort have the best case computation complexity O(N) when the input array is already sorted. 
 
by leveraging this nature, shell sort applies a method of sorting things with a gap between them, eventually reducing the gap to 1 which is the normal bubble/insertion sort. 
 
assuming we are sorting in the ascending order, this method allows the really big elements to hover to the end, and the smaller elements to be moved to the front in a leap, instead of one-by-one swap like bubble/insertion sorts do. 
 
often it's discussed in the context of improved insertion sort rather than bubble sort. 
 
- unstable sort 
- called shell sort cos it is invented by donald shell. 
 
 
 
e.g. 
 
arr int[10] = {1,2,3,4,5,6,7,8,9,10}; 
 
h = 3 :  will sort elems { arr[0],arr[3],arr[6],arr[9] }, then { arr[1],arr[4],arr[7] }, then { arr[2],arr[5],arr[8]} 
h = 1 :  will sort every elem 
 
 
 
######################################### 
####   how to determine the gap H    #### 
######################################### 
 
there are many theories proposed, each with a rigorous maths analysis and a paper. 
 
(ref) 
http://en.wikipedia.org/wiki/Shellsort#Gap_sequences 
 
 
some important property to note: 
 
(1) if you sort an array with gap H=k, and sort again with H=c, the array remains H=k sorted. 
(proof later) 
 
 
 
 
#################################### 
####   computation complexity   #### 
#################################### 
 
depends on your gap-determination scheme. 
 
### 
###  worst 
### 
 
gat H=1 is the normal insertion sort, so it's O(N^2) 
the best ones are known to give the worst case complexity O(N^(4/3)) = O(N^1.33) 
 
sedgewick version:   4^k + 3*(2^(k-1)) + 1   # prefixed with 1    #  1,8,23,77,281 
 
### 
### average 
### 
 
knuth and hibbard came up with the gap sequence that gives average O(N^(5/4)) = O(N^1.25) 
 
knuth:    (3^k - 1) / 2  # not greater than N/3      # 1,4,13,40,121,,, 
hibbard:  2^k - 1                                    # 1,3,7,15,31,63,,, 
 
### 
### best 
### 
 
again depends on the gap sequence scheeme. but the best possible case should be linear O(N). H=1 and already completely sorted input. 
 
 
############################## 
####   space complexity   #### 
############################## 
 
since it's essentially an enhancement of bubble/insertion sort, it's the same old 
 
total :    O(N) 
auxiliary: O(1) 
 
 
 
 
########################################## 
####   implementation example (C++)   #### 
########################################## 
 
for simplicity's (and performance of course) sake, lets use hibbard  2^k - 1 gap scheme 
 
code is a bit messy, but it's all just implementing an insertion sort with multi-layered gap h. 
 
-----------------------------------------  // main.cpp 
 
 
#include <iostream> 
using namespace std; 
 
void shellSort(int*arr, int arrSize) 

 
  int h = 1; 
  int prev = h; 
  int i = 1; 
  while(1)                   // need to determine the h 
    { 
      if(h > arrSize) 
        { 
          h = prev; 
          break; 
        } 
      prev = h; 
      h = (1 << i) - 1;      // 2^i  can be done with bit shift (1 << i) 
      i++; 
    } 
 
  while(1) 
    { 
      for( int i = 0 ; i < h ; i++ )                // this is for looping the group  e.g. if h=3 in array of 10 elem, 
        {                                           // then i iterates a0,a1,a2 from {a0,a3,a6,a9}{a1,a4,a7}{a2,a5,a8} 
          for(int m = h + i; m < arrSize ; m += h)  // moves the pivot by h.  like a0,a3,a6,a9 
            { 
              int pivot = arr[m]; 
              for(int j = m-h; j > -1 ;j -= h)   // based on the pivot, it iterates each of the already-sorted-subarray 
                { 
                  if(arr[j] > pivot)         // swap as long as pivot is smaller 
                    { 
                      arr[j] = arr[j] + arr[j+h]; 
                      arr[j+h] = arr[j] - arr[j+h]; 
                      arr[j] = arr[j] - arr[j+h]; 
                    } 
                  else                       // stop and break out cos pivot now sits where it fits 
                    break; 
                } 
            } 
        } 
 
      if(h == 1) 
        break; 
      h = ((h+1) >> 1) - 1;             // making h one level down  15(2^4 - 1), 7(2^3 - 1), 3(2^2 - 1), 1(2^1 - 1) 
    } 

 
void printArr(int*arr, int arrSize) 

  for(int i = 0; i < arrSize ;i++) 
    cout << arr[i] << " "; 
  cout << endl; 

 
int main() 

  int arr[] = {92,35,84,11,4,17,66,20};         // 8 elements. h will be 7,3,1 
  int arrSize = sizeof(arr)/sizeof(arr[0]); 
 
  printArr(arr,arrSize);       // 92 35 84 11 4 17 66 20 
  shellSort(arr,arrSize); 
  printArr(arr,arrSize);       // 4 11 17 20 35 66 84 92 
 
 
  return 0; 

 
---------------------------------------------- 
 

  1. 2014-06-07 22:12:46 |
  2. Category : algo
  3. Page View:

Google Ads