algorithm
सम्मिलन सॉर्ट

टिप्पणियों

एल्गोरिथम मूल बातें

सम्मिलन सॉर्ट एक बहुत ही सरल, स्थिर, इन-प्लेस सॉर्टिंग एल्गोरिथ्म है। यह छोटे अनुक्रमों पर अच्छा प्रदर्शन करता है, लेकिन बड़ी सूचियों पर यह बहुत कम कुशल है। प्रत्येक चरण में, एल्गोरिदम दिए गए अनुक्रम के i-th तत्व पर विचार करता है, इसे बाईं ओर ले जाता है जब तक कि यह सही स्थिति में न हो।

चित्रमय चित्रण

स्यूडोकोड

for j = 1 to length(A)
    n = A[j]
    i = j - 1
    while j > 0 and A[i] > n
        A[i + 1] = A[i]
        i = i - 1
    A[i + 1] = n

उदाहरण

पूर्णांकों की निम्नलिखित सूची पर विचार करें:

[5, 2, 4, 6, 1, 3]

एल्गोरिथ्म निम्न चरणों का पालन करेगा:

1. [5, 2, 4, 6, 1, 3]
2. [2, 5, 4, 6, 1, 3]
3. [2, 4, 5, 6, 1, 3]
4. [2, 4, 5, 6, 1, 3]
5. [1, 2, 4, 5, 6, 3]
6. [1, 2, 3, 4, 5, 6]

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

public class InsertionSort
{
    public static void SortInsertion(int[] input, int n)
    {
        for (int i = 0; i < n; i++)
        {
            int x = input[i];
            int j = i - 1;
            while (j >= 0 && input[j] > x)
            {
                input[j + 1] = input[j];
                j = j - 1;
            }
            input[j + 1] = x;
        }
    }

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

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

हास्केल कार्यान्वयन

insertSort :: Ord a => [a] -> [a]
insertSort [] = []
insertSort (x:xs) = insert x (insertSort xs)

insert :: Ord a => a-> [a] -> [a]
insert n [] = [n]
insert n (x:xs) | n <= x    = (n:x:xs)
                | otherwise = x:insert n xs