Рубрики

Асимптотический анализ и сравнение алгоритмов сортировки

Хорошо известно, что сортировка слиянием выполняется быстрее, чем сортировка с вставкой. Используя асимптотический анализ, мы можем доказать, что сортировка слиянием выполняется за время O (nlogn), а сортировка вставкой занимает O (n ^ 2). Это очевидно, потому что сортировка слиянием использует подход «разделяй и властвуй» путем рекурсивного решения проблем, когда сортировка вставкой следует инкрементному подходу.
Если мы еще больше рассмотрим анализ сложности времени, мы узнаем, что сортировка вставок не так уж и плоха. Удивительно, но вставка сортировки превосходит сортировку слиянием при меньшем входном размере. Это потому, что есть несколько констант, которые мы игнорируем при определении временной сложности. При больших входных размерах порядка 10 ^ 4 это не влияет на поведение нашей функции. Но когда входные размеры падают ниже, скажем, меньше 40, константы в уравнении преобладают над входным размером «n».
Все идет нормально. Но я не был удовлетворен таким математическим анализом. Как студент информатики, мы должны верить в написание кода. Я написал программу на C, чтобы понять, как алгоритмы конкурируют друг с другом для разных входных размеров. А также, почему такой строгий математический анализ делается для установления сложности времени выполнения этих алгоритмов сортировки.

Реализация:

// C ++ код для сравнения производительности алгоритмов сортировки
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.h>
#define MAX_ELEMENT_IN_ARRAY 1000000001

  

int cmpfunc (const void * a, const void * b)

{

    // Сравнить функцию, используемую qsort

    return ( *(int*)a - *(int*)b );

}

  

int* generate_random_array(int n)

{

    srand(time(NULL));

    int *a = malloc(sizeof(int) * n), i;

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

        a[i] = rand() % MAX_ELEMENT_IN_ARRAY;

    return a;

}

  

int* copy_array(int a[], int n)

{

    int *arr = malloc(sizeof(int) * n);

    int i;

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

        arr[i] = a[i];

    return arr;

}

  
// Код для вставки сортировки

void insertion_sort_asc(int a[], int start, int end)

{

    int i;

    for(i = start + 1; i <= end ; ++i)

    {

        int key = a[i];

        int j = i - 1;

        while(j >= start && a[j] > key)

        {

            a[j + 1] = a[j];

            --j;

        }

        a[j + 1] = key;

    }

}

  
// Код для сортировки слиянием

void merge(int a[], int start, int end, int mid)

{

    int i = start, j = mid + 1, k = 0;

    int *aux = malloc(sizeof(int) * (end - start + 1));

    while(i <= mid && j <= end)

    {

        if(a[i] <= a[j])

            aux[k++] = a[i++];

        else

            aux[k++] = a[j++];

    }

    while(i <= mid)

        aux[k++] = a[i++];

    while(j <= end)

        aux[k++] = a[j++];

    j = 0;

    for(i = start;i <= end;++i)

        a[i] = aux[j++];

    free(aux);

}

  

void _merge_sort(int a[],int start,int end)

{

    if(start < end)

    {

        int mid = start + (end - start) / 2;

        _merge_sort(a,start,mid);

        _merge_sort(a,mid + 1,end);

        merge(a,start,end,mid);

    }

}

void merge_sort(int a[],int n)

{

    return _merge_sort(a,0,n - 1);

}

  

  

void insertion_and_merge_sort_combine(int a[], int start, int end, int k)

{

    // Выполняет сортировку вставкой, если размер массива меньше или равен k

    // В противном случае использует сортировку слиянием

    if(start < end)

    {

        int size = end - start + 1;

          

        if(size <= k)

        {

            // printf («Выполнено вставка sort-start =% d и end =% d / n», start, end);

            return insertion_sort_asc(a,start,end);

        }

        int mid = start + (end - start) / 2;

        insertion_and_merge_sort_combine(a,start,mid,k);

        insertion_and_merge_sort_combine(a,mid + 1,end,k);

        merge(a,start,end,mid);

    }

}

  

void test_sorting_runtimes(int size,int num_of_times)

{

    // Измерение времени выполнения алгоритмов сортировки

    int number_of_times = num_of_times;

    int t = number_of_times;

    int n = size;

    double insertion_sort_time = 0, merge_sort_time = 0;

    double merge_sort_and_insertion_sort_mix_time = 0, qsort_time = 0;

    while(t--)

    {

        clock_t start, end;

          

        int *a = generate_random_array(n);

        int *b = copy_array(a,n);

        start = clock();

        insertion_sort_asc(b,0,n-1);

        end = clock();

        insertion_sort_time += ((double) (end - start)) / CLOCKS_PER_SEC;

        free(b);

        int *c = copy_array(a,n);

        start = clock();

        merge_sort(c,n);

        end = clock();

        merge_sort_time += ((double) (end - start)) / CLOCKS_PER_SEC;

        free(c);

        int *d = copy_array(a,n);

        start = clock();

        insertion_and_merge_sort_combine(d,0,n-1,40);

        end = clock();

        merge_sort_and_insertion_sort_mix_time+=((double) (end - start))/CLOCKS_PER_SEC;

        free(d);

        start = clock();

        qsort(a,n,sizeof(int),cmpfunc);

        end = clock();

        qsort_time += ((double) (end - start)) / CLOCKS_PER_SEC;

        free(a);

    }

      

    insertion_sort_time /= number_of_times;

    merge_sort_time /= number_of_times;

    merge_sort_and_insertion_sort_mix_time /= number_of_times;

    qsort_time /= number_of_times;

    printf("\nTime taken to sort:\n"

            "%-35s %f\n"

            "%-35s %f\n"

            "%-35s %f\n"

            "%-35s %f\n\n",

            "(i)Insertion sort: ",

            insertion_sort_time,

            "(ii)Merge sort: ",

            merge_sort_time,

            "(iii)Insertion-mergesort-hybrid: ",

            merge_sort_and_insertion_sort_mix_time,

            "(iv)Qsort library function: ",

            qsort_time);

}

  

int main(int argc, char const *argv[])

{

    int t;

    scanf("%d", &t);

    while(t--)

    {

        int size, num_of_times;

        scanf("%d %d", &size, &num_of_times);

        test_sorting_runtimes(size,num_of_times);

    }

    return 0;

}

Я сравнил время выполнения следующих алгоритмов:

  • Вид вставки : традиционный алгоритм без изменений / оптимизации. Это работает очень хорошо для меньших входных размеров. И да, это лучше, чем сортировка слиянием
  • Сортировка слиянием : следует принципу «разделяй и властвуй». Для входных размеров порядка 10 ^ 5 этот алгоритм является правильным выбором. Это делает вставку сортировки непрактичной для таких больших входных размеров.
  • Комбинированная версия сортировки вставкой и сортировки слиянием: я немного изменил логику сортировки слиянием, чтобы добиться значительно лучшего времени выполнения при меньших размерах ввода. Как мы знаем, сортировка слиянием разбивает свой ввод на две половины, пока не станет достаточно тривиальным для сортировки элементов. Но здесь, когда входной размер падает ниже порогового значения, такого как 'n' <40, тогда этот гибридный алгоритм вызывает традиционный метод сортировки вставкой. Из-за того, что сортировка вставок выполняется быстрее на меньших входах и сортировка слиянием выполняется быстрее на больших входах, этот алгоритм наилучшим образом использует оба мира.
  • Быстрая сортировка: я не реализовал эту процедуру. Это библиотечная функция qsort (), которая доступна в. Я рассмотрел этот алгоритм, чтобы узнать значение реализации. Требуется большой опыт программирования, чтобы минимизировать количество шагов и максимально использовать базовые языковые примитивы для наилучшей реализации алгоритма. Это основная причина, по которой рекомендуется использовать библиотечные функции. Они написаны для обработки всего и вся. Они оптимизируют в максимально возможной степени. И прежде чем я забуду, из моего анализа qsort () работает невероятно быстро практически при любом входном размере!

Анализ:

  • Входные данные: пользователь должен указать, сколько раз он / она хочет протестировать алгоритм, соответствующий количеству тестовых случаев. Для каждого тестового случая пользователь должен ввести два целых числа, разделенных пробелом, обозначающие размер ввода 'n' и 'num_of_times', обозначающие количество раз, которое он / она хочет выполнить анализ и взять среднее значение. (Пояснение: если 'num_of_times' равно 10, то каждый из указанных выше алгоритмов запускается 10 раз, и берется среднее значение. Это делается потому, что входной массив генерируется случайным образом в соответствии с указанным вами размером ввода. Входной массив может быть всем отсортировано. Наше это может соответствовать наихудшему случаю .ie в порядке убывания. Чтобы избежать времени выполнения таких входных массивов. Алгоритм запускается 'num_of_times' и берется среднее значение.)
    Функция clock () и макрос CLOCKS_PER_SEC from используются для измерения затраченного времени.
    Компиляция: я написал вышеупомянутый код в среде Linux (Ubuntu 16.04 LTS). Скопируйте фрагмент кода выше. Скомпилируйте его, используя gcc, введите указанные значения и наслаждайтесь мощью алгоритмов сортировки!
  • Результаты: Как вы можете видеть для небольших входных размеров, сортировка вставки превосходит сортировку слиянием на 2 * 10 ^ -6 сек. Но эта разница во времени не так существенна. С другой стороны, гибридный алгоритм и библиотечная функция qsort () работают так же хорошо, как сортировка вставкой.

    Размер ввода теперь увеличен примерно в 100 раз до n = 1000 с n = 30. Теперь разница ощутима. Сортировка слиянием выполняется в 10 раз быстрее, чем сортировка вставкой. Снова существует связь между производительностью гибридного алгоритма и процедурой qsort (). Это говорит о том, что qsort () реализован таким образом, который более или менее похож на наш гибридный алгоритм, т. Е. Переключается между различными алгоритмами, чтобы извлечь максимальную выгоду из них.

    Наконец, входной размер увеличен до 10 ^ 5 (1 лакх!), Что, скорее всего, является идеальным размером, используемым в практических сценариях. По сравнению с предыдущим входом n = 1000, где сортировка с разбивкой с сортировкой слиянием выполняется в 10 раз быстрее, здесь разница еще более значительна. Сортировка слиянием превосходит сортировку вставкой в 100 раз!
    Гибридный алгоритм, который мы фактически написали, не выполняет традиционную сортировку слиянием, выполняя на 0,01 сек быстрее И наконец, qsort () библиотечная функция, наконец, доказывает нам, что реализация также играет важную роль при тщательном измерении времени выполнения, выполняя на 3 миллисекунды быстрее! 😀

Примечание. Не запускайте вышеуказанную программу с n> = 10 ^ 6, так как это потребует больших вычислительных ресурсов. Спасибо и счастливого кодирования! 🙂

Эта статья предоставлена Aditya Ch . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

Рекомендуемые посты:

Асимптотический анализ и сравнение алгоритмов сортировки

0.00 (0%) 0 votes