Рубрики

ShellSort

ShellSort — это, в основном, разновидность сортировки вставками . В сортировке вставки мы перемещаем элементы только на одну позицию вперед. Когда элемент должен быть перемещен далеко вперед, задействовано много движений. Идея shellSort заключается в том, чтобы разрешить обмен удаленными элементами. В shellSort мы делаем массив h-отсортированным для большого значения h. Мы продолжаем уменьшать значение h до тех пор, пока оно не станет равным 1. Считается, что массив отсортирован по h, если отсортированы все подсписки каждого h-го элемента.

Ниже приводится реализация ShellSort.

C ++

// C ++ реализация Shell Sort
#include  <iostream>

using namespace std;

  
/ * функция для сортировки arr используя shellSort * /

int shellSort(int arr[], int n)

{

    // Начинаем с большого разрыва, затем уменьшаем разрыв

    for (int gap = n/2; gap > 0; gap /= 2)

    {

        // Делаем вставку с пробелом для этого размера зазора.

        // Первые элементы промежутка a [0..gap-1] уже находятся в зазоре

        // продолжаем добавлять еще один элемент, пока весь массив не будет

        // пробел отсортирован

        for (int i = gap; i < n; i += 1)

        {

            // добавляем [i] к элементам, которые были отсортированы по пробелу

            // сохранить [i] в temp и сделать дыру в позиции i

            int temp = arr[i];

  

            // сдвигаем ранее отсортированные по гэпу элементы до правильного

            // местоположение для [i] найдено

            int j;            

            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)

                arr[j] = arr[j - gap];

              

            // поместим temp (оригинал a [i]) в правильное местоположение

            arr[j] = temp;

        }

    }

    return 0;

}

  

void printArray(int arr[], int n)

{

    for (int i=0; i<n; i++)

        cout << arr[i] << " ";

}

  

int main()

{

    int arr[] = {12, 34, 54, 2, 3}, i;

    int n = sizeof(arr)/sizeof(arr[0]);

  

    cout << "Array before sorting: \n";

    printArray(arr, n);

  

    shellSort(arr, n);

  

    cout << "\nArray after sorting: \n";

    printArray(arr, n);

  

    return 0;

}

Джава

// Java-реализация ShellSort

class ShellSort

{

    / * Утилита для печати массива размером n * /

    static void printArray(int arr[])

    {

        int n = arr.length;

        for (int i=0; i<n; ++i)

            System.out.print(arr[i] + " ");

        System.out.println();

    }

  

    / * функция для сортировки arr используя shellSort * /

    int sort(int arr[])

    {

        int n = arr.length;

  

        // Начинаем с большого разрыва, затем уменьшаем разрыв

        for (int gap = n/2; gap > 0; gap /= 2)

        {

            // Делаем вставку с пробелом для этого размера зазора.

            // Первые элементы пробела a [0..gap-1] уже

            // в заданном порядке продолжаем добавлять еще один элемент

            // пока весь массив не отсортирован по пробелу

            for (int i = gap; i < n; i += 1)

            {

                // добавляем [i] к элементам, которые были пропущены

                // отсортировано, сохраните [i] в temp и сделайте дыру в

                // позиция i

                int temp = arr[i];

  

                // сдвигаем ранее отсортированные по гэпу элементы до

                // правильное местоположение для [i] найдено

                int j;

                for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)

                    arr[j] = arr[j - gap];

  

                // положить temp (оригинал a [i]) в правильное

                // место расположения

                arr[j] = temp;

            }

        }

        return 0;

    }

  

    // Метод драйвера

    public static void main(String args[])

    {

        int arr[] = {12, 34, 54, 2, 3};

        System.out.println("Array before sorting");

        printArray(arr);

  

        ShellSort ob = new ShellSort();

        ob.sort(arr);

  

        System.out.println("Array after sorting");

        printArray(arr);

    }


/ * Этот код предоставлен Раджатом Мишрой * /

python3

# Python3 программа для реализации Shell Sort

  

def shellSort(arr):

  

    # Начните с большого разрыва, затем уменьшите разрыв

    n = len(arr)

    gap = n//2

  

    # Сделайте вставку с пробелом для этого размера зазора.

    # Первые элементы гэпа a [0..gap-1] уже находятся в зазоре

    # порядок продолжения добавления еще одного элемента, пока весь массив

    # пробел отсортирован

    while gap > 0:

  

        for i in range(gap,n):

  

            # добавить [i] к элементам, которые были отсортированы по пробелу

            # сохранить [i] в temp и сделать дыру в позиции i

            temp = arr[i]

  

            # сдвигать ранние отсортированные элементы до правильного

            # место для [i] найдено

            j = i

            while  j >= gap and arr[j-gap] >temp:

                arr[j] = arr[j-gap]

                j -= gap

  

            # поместите temp (оригинал a [i]) в правильное местоположение

            arr[j] = temp

        gap //= 2

  

  
# Код драйвера для проверки выше

arr = [ 12, 34, 54, 2, 3]

  

n = len(arr)

print ("Array before sorting:")

for i in range(n):

    print(arr[i]),

  
shellSort(arr)

  

print ("\nArray after sorting:")

for i in range(n):

    print(arr[i]),

  
# Этот код предоставлен Мохитом Кумрой

C #

// C # реализация ShellSort

using System;

  

class ShellSort

{

    / * Функция полезности для

       распечатать массив размером n * /

    static void printArray(int []arr)

    {

        int n = arr.Length;

        for (int i=0; i<n; ++i)

        Console.Write(arr[i] + " ");

        Console.WriteLine();

    }

  

    / * функция для сортировки arr используя shellSort * /

    int sort(int []arr)

    {

        int n = arr.Length;

  

        // Начнем с большого разрыва,

        // затем уменьшаем разрыв

        for (int gap = n/2; gap > 0; gap /= 2)

        {

            // Делаем вставку с пробелом для этого размера зазора.

            // Первые элементы пробела a [0..gap-1] уже

            // в заданном порядке продолжаем добавлять еще один элемент

            // пока весь массив не отсортирован по пробелу

            for (int i = gap; i < n; i += 1)

            {

                // добавляем [i] к элементам, которые имеют

                // отсортированный пробел, сохраните [i] в temp и

                // сделать отверстие в позиции i

                int temp = arr[i];

  

                // сдвигаем ранее отсортированные по гэпу элементы до

                // правильное местоположение для [i] найдено

                int j;

                for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)

                    arr[j] = arr[j - gap];

  

                // положить temp (оригинал a [i])

                // в правильном месте

                arr[j] = temp;

            }

        }

        return 0;

    }

  

    // Метод драйвера

    public static void Main()

    {

        int []arr = {12, 34, 54, 2, 3};

        Console.Write("Array before sorting :\n");

        printArray(arr);

  

        ShellSort ob = new ShellSort();

        ob.sort(arr);

  

        Console.Write("Array after sorting :\n");

        printArray(arr);

    }

  
// Этот код предоставлен нитин митталь.


Выход:

Array before sorting:
12 34 54 2 3
Array after sorting:
2 3 12 34 54

Сложность времени: временная сложность вышеописанной реализации сортировки оболочки равна O (n 2 ). В приведенной выше реализации разрыв уменьшается вдвое на каждой итерации. Есть много других способов уменьшить разрыв, которые приводят к лучшей временной сложности. Смотрите это для более подробной информации.

Ссылки:
https://www.youtube.com/watch?v=pGhazjsFW28
http://en.wikipedia.org/wiki/Shellsort


Фотосъёмка:





Викторина по Shell Sort

Другие алгоритмы сортировки на GeeksforGeeks / GeeksQuiz: