C++ प्रोग्राम शेल सॉर्ट को लागू करने के लिए

शेल सॉर्टिंग तकनीक सम्मिलन प्रकार पर आधारित है। सम्मिलन क्रम में कभी-कभी हमें आइटम को सही स्थान पर सम्मिलित करने के लिए बड़े ब्लॉक को स्थानांतरित करने की आवश्यकता होती है। शेल सॉर्ट का उपयोग करके, हम बड़ी संख्या में स्थानांतरण से बच सकते हैं। छँटाई विशिष्ट अंतराल के साथ की जाती है। प्रत्येक पास के बाद अंतराल को छोटा अंतराल बनाने के लिए कम किया जाता है।

शैल सॉर्ट तकनीक की जटिलता

• समय जटिलता:ओ (एन लॉग एन) सर्वोत्तम मामले के लिए, और अन्य मामलों के लिए, यह अंतराल अनुक्रम पर निर्भर करता है।

• अंतरिक्ष जटिलता:ओ(1)

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

एल्गोरिदम

shellSort(सरणी, आकार)

इनपुट :डेटा की एक सरणी, और सरणी में कुल संख्या

आउटपुट :क्रमबद्ध सरणी

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