シェルソート

シェルソート手法は、挿入ソートに基づいています。挿入ソートでは、アイテムを正しい場所に挿入するために大きなブロックをシフトする必要がある場合があります。シェルソートを使用すると、多数のシフトを回避できます。並べ替えは特定の間隔で行われます。各パスの後、間隔が短くなり、間隔が短くなります。

シェルソート手法の複雑さ

• 時間計算量：最良の場合はO（n log n）、その他の場合はギャップシーケンスに依存します。
• スペースの複雑さ：O（1）

入力と出力

Input:
The unsorted list: 23 56 97 21 35 689 854 12 47 66
Output:
Array before Sorting: 23 56 97 21 35 689 854 12 47 66
Array after Sorting: 12 21 23 35 47 56 66 97 689 854

アルゴリズム

shellSort(array, size)

入力- データの配列、および配列内の総数

出力- ソートされた配列

Begin
   for gap := size / 2, when gap > 0 and gap is updated with gap / 2 do
      for j:= gap to size– 1 do
         for k := j-gap to 0, decrease by gap value do
            if array[k+gap] >= array[k]
               break
            else
               swap array[k + gap] with array[k]
         done
      done
   done
End

例

#include<iostream>
using namespace std;

void swapping(int &a, int &b) { //swap the content of a and b
   int temp;
   temp = a;
   a = b;
   b = temp;
}

void display(int *array, int size) {
   for(int i = 0; i<size; i++)
      cout << array[i] << " ";
   cout << endl;
}

void shellSort(int *arr, int n) {
   int gap, j, k;
   for(gap = n/2; gap > 0; gap = gap / 2) {      //initially gap = n/2, decreasing by gap /2
      for(j = gap; j<n; j++) {
         for(k = j-gap; k>=0; k -= gap) {
            if(arr[k+gap] >= arr[k])
               break;
            else
               swapping(arr[k+gap], arr[k]);
         }
      }
   }
}

int main() {
   int n;
   cout << "Enter the number of elements: ";
   cin >> n;
   int arr[n]; //create an array with given number of elements
   cout << "Enter elements:" << endl;

   for(int i = 0; i<n; i++) {
      cin >> arr[i];
   }

   cout << "Array before Sorting: ";
   display(arr, n);
   shellSort(arr, n);
   cout << "Array after Sorting: ";
   display(arr, n);
}

出力

Enter the number of elements: 10
Enter elements:
23 56 97 21 35 689 854 12 47 66
Array before Sorting: 23 56 97 21 35 689 854 12 47 66
Array after Sorting: 12 21 23 35 47 56 66 97 689 854