Алгоритм поиска и сортировки C # Sharp: Shell sort

Алгоритм поиска и сортировки C # Sharp: упражнение-1 с решением

Напишите программу на C # Sharp для сортировки списка элементов, используя сортировку Shell.

Примечание. Согласно Википедии «Сортировка оболочки или метод Shell является сортировкой сравнения на месте. Это можно рассматривать как обобщение сортировки по обмену (пузырьковая сортировка) или сортировку по вставке (вставка сортировки). Метод начинается с сортировки». пары элементов далеко друг от друга, а затем постепенно сокращается разрыв между сравниваемыми элементами. Начиная с далеко расположенных элементов, можно перемещать некоторые неуместные элементы в положение быстрее, чем простой обмен ближайшими соседями ».

Пример запуска Shellsort с пробелами 5, 3 и 1 показан ниже.

Первый проход, 5-сортировка, выполняет сортировку вставки на отдельных подмассивах (a1, a6, a11), (a2, a7, a12), (a3, a8), (a4, a9), (a5, a10). Например, он изменяет подмассив (a1, a6, a11) с (62, 17, 25) на (17, 25, 62). Следующий проход, сортировка 3, выполняет сортировку вставки для подмассивов (a1, a4, a7, a10), (a2, a5, a8, a11), (a3, a6, a9, a12). Последний проход, 1-сортировка, является обычной сортировкой вставки всего массива (a1, ..., a12).
Как показано в примере, подмассивы, на которых работает Shellsort, изначально короткие; позже они длиннее но почти заказаны. В обоих случаях сортировка вставок работает эффективно.
Сортировка оболочки нестабильна: она может изменить относительный порядок элементов с равными значениями. Это адаптивный алгоритм сортировки, который выполняется быстрее при частичной сортировке входных данных.

Shell Sort

Shellsort с пробелами 23, 10, 4, 1 в действии .

Пример решения : -

C # острый код:

using System;
using System.Collections;
namespace Shell_Sort
{
    public class SortShell
    {
       static void Main(string[] args)
        {
            int[] arr = new int[] { 5, -4, 11, 0, 18, 22, 67, 51, 6 };
            int n;
            n = arr.Length;
            Console.WriteLine("Original Array Elements :");
            show_array_elements(arr);
            shellSort(arr, n);
            Console.WriteLine("\nSorted Array Elements :");
            show_array_elements(arr);
        }
        static void shellSort(int[] arr, int array_size)
        {
            int i, j, inc, temp;
            inc = 3;
            while (inc > 0)
            {
                for (i = 0; i < array_size; i++)
                {
                    j = i;
                    temp = arr[i];
                    while ((j >= inc) && (arr[j - inc] > temp))
                    {
                        arr[j] = arr[j - inc];
                        j = j - inc;
                    }
                    arr[j] = temp;
                }
                if (inc / 2 != 0)
                    inc = inc / 2;
                else if (inc == 1)
                    inc = 0;
                else
                    inc = 1;
            }
        }
        static void show_array_elements(int[] arr)
        {
            foreach (var element in arr)
            {
                Console.Write(element + " ");
            }
            Console.Write("\n");
        }
    }
}

Пример вывода:

 Оригинальные элементы массива:                                                                                     
5 -4 11 0 18 22 67 51 6                                                                                       
                                                                                                              
Сортированные элементы массива:                                                                                       
-4 0 5 6 11 18 22 51 67

Блок - схема:

Редактор кода C # Sharp:

Внесите свой код и комментарии через Disqus.

Предыдущая: Упражнения по алгоритму поиска и сортировки C # Sharp
Далее: Напишите программу на C # Sharp для сортировки списка элементов с помощью сортировки Bogosort.