مرتب سازی شل (Shell Sort) — به زبان ساده

1// C++ implementation of Shell Sort 
2#include  <iostream> 
3using namespace std; 
4  
5/* function to sort arr using shellSort */
6int shellSort(int arr[], int n) 
7{ 
8    // Start with a big gap, then reduce the gap 
9    for (int gap = n/2; gap > 0; gap /= 2) 
10    { 
11        // Do a gapped insertion sort for this gap size. 
12        // The first gap elements a[0..gap-1] are already in gapped order 
13        // keep adding one more element until the entire array is 
14        // gap sorted  
15        for (int i = gap; i < n; i += 1) 
16        { 
17            // add a[i] to the elements that have been gap sorted 
18            // save a[i] in temp and make a hole at position i 
19            int temp = arr[i]; 
20  
21            // shift earlier gap-sorted elements up until the correct  
22            // location for a[i] is found 
23            int j;             
24            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) 
25                arr[j] = arr[j - gap]; 
26              
27            //  put temp (the original a[i]) in its correct location 
28            arr[j] = temp; 
29        } 
30    } 
31    return 0; 
32} 
33  
34void printArray(int arr[], int n) 
35{ 
36    for (int i=0; i<n; i++) 
37        cout << arr[i] << " "; 
38} 
39  
40int main() 
41{ 
42    int arr[] = {12, 34, 54, 2, 3}, i; 
43    int n = sizeof(arr)/sizeof(arr[0]); 
44  
45    cout << "Array before sorting: \n"; 
46    printArray(arr, n); 
47  
48    shellSort(arr, n); 
49  
50    cout << "\nArray after sorting: \n"; 
51    printArray(arr, n); 
52  
53    return 0;

1// Java implementation of ShellSort 
2class ShellSort 
3{ 
4    /* An utility function to print array of size n*/
5    static void printArray(int arr[]) 
6    { 
7        int n = arr.length; 
8        for (int i=0; i<n; ++i) 
9            System.out.print(arr[i] + " "); 
10        System.out.println(); 
11    } 
12  
13    /* function to sort arr using shellSort */
14    int sort(int arr[]) 
15    { 
16        int n = arr.length; 
17  
18        // Start with a big gap, then reduce the gap 
19        for (int gap = n/2; gap > 0; gap /= 2) 
20        { 
21            // Do a gapped insertion sort for this gap size. 
22            // The first gap elements a[0..gap-1] are already 
23            // in gapped order keep adding one more element 
24            // until the entire array is gap sorted 
25            for (int i = gap; i < n; i += 1) 
26            { 
27                // add a[i] to the elements that have been gap 
28                // sorted save a[i] in temp and make a hole at 
29                // position i 
30                int temp = arr[i]; 
31  
32                // shift earlier gap-sorted elements up until 
33                // the correct location for a[i] is found 
34                int j; 
35                for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) 
36                    arr[j] = arr[j - gap]; 
37  
38                // put temp (the original a[i]) in its correct 
39                // location 
40                arr[j] = temp; 
41            } 
42        } 
43        return 0; 
44    } 
45  
46    // Driver method 
47    public static void main(String args[]) 
48    { 
49        int arr[] = {12, 34, 54, 2, 3}; 
50        System.out.println("Array before sorting"); 
51        printArray(arr); 
52  
53        ShellSort ob = new ShellSort(); 
54        ob.sort(arr); 
55  
56        System.out.println("Array after sorting"); 
57        printArray(arr); 
58    } 
59}  
60/*This code is contributed by Rajat Mishra */

1# Python3 program for implementation of Shell Sort 
2  
3def shellSort(arr): 
4  
5    # Start with a big gap, then reduce the gap 
6    n = len(arr) 
7    gap = n//2
8  
9    # Do a gapped insertion sort for this gap size. 
10    # The first gap elements a[0..gap-1] are already in gapped  
11    # order keep adding one more element until the entire array 
12    # is gap sorted 
13    while gap > 0: 
14  
15        for i in range(gap,n): 
16  
17            # add a[i] to the elements that have been gap sorted 
18            # save a[i] in temp and make a hole at position i 
19            temp = arr[i] 
20  
21            # shift earlier gap-sorted elements up until the correct 
22            # location for a[i] is found 
23            j = i 
24            while  j >= gap and arr[j-gap] >temp: 
25                arr[j] = arr[j-gap] 
26                j -= gap 
27  
28            # put temp (the original a[i]) in its correct location 
29            arr[j] = temp 
30        gap //= 2
31  
32  
33# Driver code to test above 
34arr = [ 12, 34, 54, 2, 3] 
35  
36n = len(arr) 
37print ("Array before sorting:") 
38for i in range(n): 
39    print(arr[i]), 
40  
41shellSort(arr) 
42  
43print ("\nArray after sorting:") 
44for i in range(n): 
45    print(arr[i]), 
46  
47# This code is contributed by Mohit Kumra 

1// C# implementation of ShellSort 
2using System; 
3  
4class ShellSort 
5{ 
6    /* An utility function to  
7       print array of size n*/
8    static void printArray(int []arr) 
9    { 
10        int n = arr.Length; 
11        for (int i=0; i<n; ++i) 
12        Console.Write(arr[i] + " "); 
13        Console.WriteLine(); 
14    } 
15  
16    /* function to sort arr using shellSort */
17    int sort(int []arr) 
18    { 
19        int n = arr.Length; 
20  
21        // Start with a big gap,  
22        // then reduce the gap 
23        for (int gap = n/2; gap > 0; gap /= 2) 
24        { 
25            // Do a gapped insertion sort for this gap size. 
26            // The first gap elements a[0..gap-1] are already 
27            // in gapped order keep adding one more element 
28            // until the entire array is gap sorted 
29            for (int i = gap; i < n; i += 1) 
30            { 
31                // add a[i] to the elements that have 
32                // been gap sorted save a[i] in temp and 
33                // make a hole at position i 
34                int temp = arr[i]; 
35  
36                // shift earlier gap-sorted elements up until 
37                // the correct location for a[i] is found 
38                int j; 
39                for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) 
40                    arr[j] = arr[j - gap]; 
41  
42                // put temp (the original a[i])  
43                // in its correct location 
44                arr[j] = temp; 
45            } 
46        } 
47        return 0; 
48    } 
49  
50    // Driver method 
51    public static void Main() 
52    { 
53        int []arr = {12, 34, 54, 2, 3}; 
54        Console.Write("Array before sorting :\n"); 
55        printArray(arr); 
56  
57        ShellSort ob = new ShellSort(); 
58        ob.sort(arr); 
59  
60        Console.Write("Array after sorting :\n"); 
61        printArray(arr); 
62    } 
63}  
64  
65// This code is contributed by nitin mittal.