algorithm
शेल सॉर्ट

शैल क्रमबद्ध बुनियादी जानकारी

शेल सॉर्ट , जिसे घटती हुई वृद्धि के रूप में भी जाना जाता है, सबसे पुराने सॉर्टिंग एल्गोरिदम में से एक है, जिसका नाम इसके आविष्कारक डोनाल्ड के नाम पर रखा गया है । एल। शैल (1959)। यह तेज़, समझने में आसान और लागू करने में आसान है। हालांकि, इसकी जटिलता का विश्लेषण थोड़ा अधिक परिष्कृत है।

शैल प्रकार का विचार निम्नलिखित है:

1. डेटा अनुक्रम को द्वि-आयामी सरणी में व्यवस्थित करें
2. सरणी के स्तंभों को क्रमबद्ध करें

शैल प्रकार सम्मिलन प्रकार को बेहतर बनाता है। यह दूर के तत्वों की तुलना करके शुरू होता है, फिर तत्वों को दूर तक कम करता है, और अंत में आसन्न तत्वों (प्रभावी रूप से एक सम्मिलन प्रकार) की तुलना करता है।

प्रभाव यह है कि डेटा अनुक्रम आंशिक रूप से सॉर्ट किया गया है। ऊपर की प्रक्रिया को दोहराया जाता है, लेकिन हर बार एक संकीर्ण सरणी के साथ, यानी कम संख्या में कॉलम के साथ। अंतिम चरण में, सरणी में केवल एक कॉलम होता है।

शैल प्रकार का उदाहरण:

शेल के लिए छद्म कोड

input
foreach element in input
{
    for(i = gap; i < n; i++)
    {
        temp = a[i]
        for (j = i; j >= gap and a[j - gap] > temp; j -= gap)
        {
            a[j] = a[j - gap]
        }
        a[j] = temp
    }
}

सहायक स्थान: O(n) total, O(1) auxiliary
समय जटिलता: O(nlogn)

C # कार्यान्वयन

public class ShellSort
{
    static void SortShell(int[] input, int n)
    {
        var inc = 3;
        while (inc > 0)
        {
            int i;
            for (i = 0; i < n; i++)
            {
                var j = i;
                var temp = input[i];
                while ((j >= inc) && (input[j - inc] > temp))
                {
                    input[j] = input[j - inc];
                    j = j - inc;
                }
                input[j] = temp;
            }
            if (inc / 2 != 0)
                inc = inc / 2;
            else if (inc == 1)
                inc = 0;
            else
                inc = 1;
        }
    }

    public static int[] Main(int[] input)
    {
        SortShell(input, input.Length);
        return input;
    }
}