Сортировка вставками реализация адаптированных из интернета


Я нашел эту реализацию на веб-сайте:

void insertSort(int a[], int length) 
{  
    int i, j, value;  
    int k=0;
    for(i = 1; i < length; i++) 
    {  
      value = a[i];  
        for (j = i - 1; j >= 0 && a[j] > value; j--) 
      {  
            a[j + 1] = a[j]; 
            k++;
        }  
        a[j+1] = value;  
    }  

    printf("k=%d", k);
}

Я написал это:

#include <stdio.h>

#define SIZE 8

int array1[SIZE] = {77, 33, 44, 11, 88, 22, 66, 55};

void PrintArray()
{
    int i = 0;
    printf("\n");
    for(i=0 ; i<SIZE ; i++)
    {
        printf("%d, ", array1[i]);
    }
}

void Insert(int insertPosition, int insertElementIndex)
{
    int temp = array1[insertElementIndex];
    int i = 0;

    for(i=insertElementIndex ; i>=insertPosition ; i--)
    {
        array1[i] = array1[i-1];
    }

    array1[insertPosition] = temp;
}

void InsertionSort()
{
    int i = 0;
    int j = 0;
    int k = 0;

    for(i=0 ; i<SIZE ; i++)
    {
        for(j=0 ; j<=i ; j++)
        {
            if(array1[i] < array1[j])
            {
                Insert(j, i);               
                PrintArray();               
            }

            k++;
        }
    }
    printf("k=%d", k);
}



main()
{
    PrintArray();

    InsertionSort();
    //insertSort(array1, SIZE);

    PrintArray();

    getch();
}

Есть ли проблема с этой реализации?



725
9
задан 22 апреля 2011 в 10:04 Источник Поделиться
Комментарии
2 ответа

Прежде всего, что вы реализовали-это не сортировка вставками:

Сортировка вставками используется один цикл, чтобы выполнить итерации по массиву и для каждого элемента используется другой контур, чтобы переместить элемент в нужное место. Это делает его время \$o(п^2)\$.

Ваш алгоритм выполняется для каждой пары элементов (с использованием двух вложенных циклов в InsertionSort()) и затем для каждой пары используется третья петля (одна вставка) для перемещения одного элемента на другой при необходимости. Это делает его время \$o(П^3)\ долл., что значительно хуже, чем \$o(п^2)\$.

Так что это проблема.


В дополнение к этому есть также серьезная проблема юзабилити с вашей функции:

Путем создания массива и его размер глобальной переменной и постоянной, а не параметры, можно сделать повторно использовать функции, как хорошо, как невозможно. Если вы хотите использовать функцию для сортировки нескольких массивов, вам нужно скопировать их в глобальную переменную, вызвать функцию сортировки, а затем скопировать его обратно из глобальной переменной. И это работает только если все массивы имеют одинаковый размер. Если массивы имеют различные размеры его просто невозможно использовать ваш InsertionSort функции на них.

Поэтому, проходя массива и его размер в качестве параметров явно предпочтительнее.


Наконец, я понимаю, что ты скорее всего в курсе этого и это всего лишь учебное упражнение, но на всякий случай:

В большинстве реальных приложений, быстрая сортировка или сортировка слиянием, как правило, предпочтительнее сортировка вставкой, с гораздо лучшими характеристиками, чем сортировка вставками в большинстве случаев. Так что если вы хотите использовать это в реальном коде, вы должны пересмотреть, действительно ли вы хотите использовать сортировка вставками.

Также стандартная библиотека C имеет вид функция встроенный, так что вам даже не придется выполнять что-либо самостоятельно.

14
ответ дан 22 апреля 2011 в 10:04 Источник Поделиться

Не использовать глобальные переменные:

int array1[SIZE] = {77, 33, 44, 11, 88, 22, 66, 55};

Это позволит сделать ваш код труднее поддерживать и больше вероятность ошибок, багов, потому что он может быть изменен из любой точки программы.

Вместо этого, инициализировать его в функции main() и передайте ему все необходимые функции. Эта практика использования локальных объектов более глобальные должны быть соблюдены во всех программах. Однако, если вы работаете с константами, это хорошо, чтобы держать их глобальными, потому что они уже неизменны.

Это может также быть полезно в случае, если вы решили добавить дополнительные массивы, как было бы легче поддерживать их все в функции main(). Хотя вы могли бы вместо того, чтобы сделать их константы и использовать локальные копии, вы все равно должны избегать возвращения в локальный массив (неопределенное поведение). В частности, вы не может возвращать массив себя, потому что только возвращает указатели на массивы, и этот указатель будет указывать на локальные данные.

Боковые Примечание: удалить закомментированные строки в функции main(). Это загромождает код немного, и это бессмысленно, даже если она осталась (размер уже мирового масштаба).

2
ответ дан 14 апреля 2014 в 10:04 Источник Поделиться