শেল সর্টিং টেকনিক (Shell Sort) ইনসার্শন সর্টের উপর ভিত্তি করে। ইনসার্শন সর্টে কখনও কখনও বড় ব্লক শিফট করতে হয় সঠিক লোকেশনে আইটেম ইনসার্ট করার জন্য। শেল সর্ট ব্যবহার করে আমরা বড় সংখ্যক শিফটিং এড়াতে পারি। সর্টিং নির্দিষ্ট ইন্টারভാലে করা হয়। প্রতিটি পাসের পর ইন্টারভাল কমিয়ে ছোট করা হয়।
শেল সর্ট টেকনিকের জটিলতা
সময় জটিলতা: বেস্ট কেসে O(n log n), অন্যান্য কেসে গ্যাপ সিকোয়েন্সের উপর নির্ভর করে।
স্পেস জটিলতা: O(1)
ইনপুট − আনসর্টেড লিস্ট: 23 56 97 21 35 689 854 12 47 66 আউটপুট − সর্টিংয়ের পর অ্যারে: 12 21 23 35 47 56 66 97 689 854
অ্যালগরিদম
shellSort(array, size)
ইনপুট: একটি ডেটা অ্যারে, এবং অ্যারেতে মোট সংখ্যা
আউটপুট: সর্টেড অ্যারে
শুরু
gap := size / 2 থেকে শুরু, gap > 0 रहने দিয়ে এবং gap = gap / 2 করে আপডেট
j := gap থেকে size-1 পর্যন্ত
k := j-gap থেকে 0 পর্যন্ত, gap ভ্যালু দিয়ে কমিয়ে
যদি array[k+gap] >= array[k] হয় তবে
ব্রেক
অন্যথায়
array[k+gap] এবং array[k] সোয়্যাপ করুন
শেষ
শেষ
শেষ
শেষ
উদাহরণ কোড
#include <iostream>
using namespace std;
void swapping(int &a, int &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) {
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 << "এলিমেন্টের সংখ্যা দিন: ";
cin >> n;
int arr[n];
cout << "এলিমেন্টগুলো দিন:" << endl;
for(int i = 0; i < n; i++) {
cin >> arr[i];
}
cout << "সর্টিংয়ের আগে অ্যারে: ";
display(arr, n);
shellSort(arr, n);
cout << "সর্টিংয়ের পর অ্যারে: ";
display(arr, n);
}
আউটপুট
এলিমেন্টের সংখ্যা দিন: 10 এলিমেন্টগুলো দিন: 23 56 97 21 35 689 854 12 47 66 সর্টিংয়ের আগে অ্যারে: 23 56 97 21 35 689 854 12 47 66 সর্টিংয়ের পর অ্যারে: 12 21 23 35 47 56 66 97 689 854
