उदाहरण
import java.io.*;
public class Demo {
static void stoogeSort(int my_arr[], int l_val, int h_val) {
if (l_val >= h_val)
return;
if (my_arr[l_val] > my_arr[h_val]) {
int temp = my_arr[l_val];
my_arr[l_val] = my_arr[h_val];
my_arr[h_val] = temp;
}
if (h_val - l_val + 1 > 2) {
int temp = (h_val - l_val + 1) / 3;
stoogeSort(my_arr, l_val, h_val - temp);
stoogeSort(my_arr, l_val + temp, h_val);
stoogeSort(my_arr, l_val, h_val - temp);
}
}
public static void main(String args[]) {
int my_arr[] = {12, 34, 67, 91, 11, 0, 89, 102, 39};
int n = my_arr.length;
stoogeSort(my_arr, 0, n - 1);
System.out.println("स्टूज सॉर्ट करने के बाद ऐरे है: ");
for (int i = 0; i < n; i++)
System.out.print(my_arr[i] + " ");
}
}
आउटपुट
स्टूज सॉर्ट करने के बाद ऐरे है 0 11 12 34 39 67 89 91 102
व्याख्या: Demo क्लास में 'stoogeSort' नामक एक फंक्शन होता है जो ऐरे, बाएं, ऊंचाई और दाएं मानों को पैरामीटर के रूप में लेता है। यदि बायां मान दाएं मान से बड़ा या बराबर है, तो कुछ भी नहीं लौटाया जाता। यदि ऐरे में बायां मान ऐरे में दाएं मान से बड़ा है, तो एक साधारण स्वैपिंग की जाती है।
ऊंचाई और बाएं मानों के आधार पर, 'stoogeSort' फंक्शन को बाएं मान और ऊंचाई मान पास करके कॉल किया जाता है। मुख्य फंक्शन में, ऐरे को परिभाषित किया जाता है, और इसकी लंबाई एक मान में संग्रहीत की जाती है। फंक्शन को इन मानों को पास करके कॉल किया जाता है और आउटपुट कंसोल पर प्रदर्शित होता है।
स्टूज सॉर्ट एल्गोरिदम:
- एक पुनरावर्ती सॉर्टिंग एल्गोरिदम
- समय जटिलता: O(n^(log 3 / log 1.5)) ≈ O(n^2.7095)
- बबल सॉर्ट से धीमा लेकिन क्विकसॉर्ट से सरल
- मुख्य रूप से शैक्षिक उद्देश्यों के लिए उपयोग किया जाता है
एल्गोरिदम चरण:
- यदि पहला तत्व अंतिम से बड़ा है, तो उन्हें स्वैप करें
- यदि 3 से अधिक तत्व हैं:
- पहले 2/3 को सॉर्ट करें
- अंतिम 2/3 को सॉर्ट करें
- फिर से पहले 2/3 को सॉर्ट करें
तुलना:
| एल्गोरिदम | समय जटिलता | स्थान जटिलता | स्थिर |
|---|---|---|---|
| स्टूज सॉर्ट | O(n^2.71) | O(n) | नहीं |
| बबल सॉर्ट | O(n²) | O(1) | हां |
| मर्ज सॉर्ट | O(n log n) | O(n) | हां |
| क्विक सॉर्ट | O(n log n) औसत | O(log n) | नहीं |