শেল সোর্ট (Shell Sort)

শেল সোর্ট ইনসারশন সোর্টের উন্নত সংস্করণ। ইনসারশন সোর্টে বড় ব্লক শিফট করতে হয়, শেল সোর্টে নির্দিষ্ট ইন্টারভাল (gap) দিয়ে সোর্ট করা হয়, প্রতিটি পাসের পর গ্যাপ কমে যায়।

শেল সোর্টের জটিলতা

• টাইম কমপ্লেক্সিটি: বেস্ট কেস O(n log n), অন্যান্য কেসে গ্যাপ সিকোয়েন্সের ওপর নির্ভর
• স্পেস কমপ্লেক্সিটি: O(1)

ইনপুট এবং আউটপুট

Input: 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; gap > 0; gap := gap/2 do
        for j := gap to size-1 do
            for k := j-gap down to 0 step -gap do
                if array[k+gap] >= array[k] break
                else swap array[k+gap], array[k]
            done
        done
    done
End

C++ উদাহরণ

#include <iostream>
using namespace std;

void swapping(int &a, int &b) { int t=a; a=b; b=t; }
void display(int *a, int n) { for(int i=0;i0; gap/=2)
        for(int j=gap; j=0; k-=gap)
                if(arr[k+gap] < arr[k]) swapping(arr[k+gap], arr[k]);
                else break;
}

int main() {
    int n; cout << "Enter the number of elements: "; cin >> n;
    int arr[n];
    cout << "Enter elements:" << endl;
    for(int i=0; i> 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