मैं तुलना करने के लिए एक प्रयोग कर रहा हूं कि कैसे थॉमस हिबार्ड के खोल प्रकार (अंतराल आकार = 2^के -1) और डोनाल्ड शेल के खोल प्रकार (एन/2^के) एक ही सरणी पर प्रदर्शन करते हैं। जब सरणी का आकार 10 से 1000 तक होता है, तो हिबार्ड खोल से बेहतर प्रदर्शन कर रहा है। लेकिन जब आकार 10000 या उससे अधिक तक पहुंच जाता है, तो शेल सॉर्ट हिबार्ड से तेज होता है।शेल बनाम। हिबार्ड समय जटिलता तुलना
बड़े ओ नोटेशन के अनुसार, हिबार्ड ओ (एन^1.5) है, शैल ओ (एन^2) है, जो मुझे लगता है कि हिल्बार्ड को डेटा सेट के आकार के रूप में शैल पर अधिक सुधार होना चाहिए। क्या कोई मुझे बता सकता है कि मेरे नतीजों की अपेक्षा क्यों नहीं की जा सकती है?
मैं समझता हूं कि ओ नोटेशन सबसे खराब मामला जटिलता है, लेकिन ऐसा लगता है कि प्रदर्शन को नोटेशन के लिए बेहतर संरेखित करना चाहिए।
यहाँ मेरी कोड जावा में लिखा है: (ध्यान दें: unsortedArray घोषित कर दिया और पहले आरंभ नहीं हो जाता)
{
int temp;
int[] sortedArray = unsortedArray.clone();
printArray();
int k = (int)(Math.log(sortedArray.length)/Math.log(2));
int gap = (int)(Math.pow(2,k)-1);
int count = 0;
long endTime;
long startTime = System.nanoTime();
while (gap > 0)
{
for (int g = 0; g < gap; g++)
{
for (int d = g + gap; d < sortedArray.length; d = d + gap)
{
for (int i = d; i - gap >= 0; i = i - gap)
{
if (sortedArray[i - gap] <= (sortedArray[i]))
{
break;
}
count++;
temp = sortedArray[i];
sortedArray[i] = sortedArray [i-gap];
sortedArray[i-gap] = temp;
}
}
}
k = k -1;
gap = (int)(Math.pow(2,k)-1);
}
endTime = System.nanoTime();
System.out.println("The total time for hibbard sort is" + (endTime-startTime));
System.out.println("the number of swaps for hibbard sort is" + count);
}
कृपया ध्यान दें कि कोड हिबार्ड के खोल प्रकार के लिए है। –
'स्वैप' या 'तुलना' की बजाय 'कैश मिस' के संदर्भ में जटिलता मापना जानकारीपूर्ण हो सकता है। – Novelocrat