Пузырьковая сортировка против сортировки вставками во время выполнения

Я пытаюсь написать программу, которая вычисляет время выполнения пузырьковой сортировки по сравнению с сортировкой вставками. Он принимает два входа, количество элементов и элементов и вычисляет время их выполнения. Это то, что у меня есть до сих пор, но оно печатает одинаковое время для обоих сортировщиков.

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.h>

int bubblesort(int a[], int n);
int insertionsort(int a[], int n);

int main()
{
    int s,temp,i,j,comparisons,a[20];
    float function_time;
    clock_t start;
    clock_t end;
    printf("Enter total numbers of elements: ");
    scanf("%d",&s);
    printf("Enter %d elements: ",s);

    for(i=0;i<s;i++)
    scanf("%d",&a[i]);

  //Bubble sorting algorithm

    for(i=s-2;i>=0;i--)
    {
        for(j=0;j<=i;j++)
        {
            if(a[j]>a[j+1])
            {
                temp=a[j];

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

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

    for(i=0;i<s;i++)
    a[i]= rand()%10000;

    start = clock();    
    comparisons= bubblesort(a, s);
    end = clock();
    function_time = (float)(end)/(CLOCKS_PER_SEC);  // Time in seconds
    printf("\nTime for Bubble Sort is %f microseconds\n ", function_time);

    // Insertion sorting algorithm

    for(i=1;i<s;i++)
    {
        temp=a[i];
        j=i-1;
        while((temp<a[j])&&(j>=0))
        {
            a[j+1]=a[j];
            j=j-1;
        }
        a[j+1]=temp;
    }

    for(i=0;i<s;i++)
    a[i]= rand()%10000;

    start = clock();    
    comparisons= insertionsort(a, s);
    end = clock();
    function_time = (float)(end)/(CLOCKS_PER_SEC);  // Time in seconds
    printf("\nTime for Insertion Sort is %f microseconds\n ", function_time);

    return 0;
}

int bubblesort(int a[], int n)
{
    bool swapped = false;
    int temp=0, counter=0;

    for (int j = n-1; j>0; j--)
    {
        swapped = false;
        for (int k = 0; k<j; k++) 
            {
                counter++;
                if (a[k+1] < a[k]) 
                {
                    temp= a[k];
                    a[k] = a[k+1];
                    a[k+1]= temp;
                    swapped = true;
                }
            }
        if (!swapped)
            break;
    }

return counter;
}

int insertionsort(int a[], int n)
{
    bool swapped = false;
    int temp=0, counter=0;
    for (int i=1; i<=n; i++)
    {    
        for (int s=i; s>0; s--)
        {
            counter++;
            if (a[s]<a[s-1])
            {
                temp=a[s-1];
                a[s-1]=a[s];
                a[s]=temp;
                swapped = true;
            } 
        }
        if (!swapped)
            break;
    }
return counter;
}

person Thisgurl    schedule 03.12.2013    source источник
comment
Я думаю, что ваш код избыточен. Код для обоих видов повторяется дважды. Почему?   -  person Aswin Murugesh    schedule 03.12.2013
comment
Не знаю, как это изменить и с чего начать.   -  person Thisgurl    schedule 03.12.2013
comment
clock не подходит для измерения времени выполнения. Это ваша главная проблема. Разрешение слишком низкое, и на многих системах оно даже не работает так, как описано в документации.   -  person R.. GitHub STOP HELPING ICE    schedule 03.12.2013
comment
Вам нужны большие наборы данных для сравнения с использованием clock() — попробуйте, например, от 10 000 до 50 000 с шагом 10 000. Вам также необходимо убедиться, что вы сортируете одни и те же данные с каждым алгоритмом. Создайте данные любым выбранным вами механизмом, затем сделайте их копию; затем отсортируйте одну копию с помощью пузырьковой сортировки, а другую — с сортировкой вставками, синхронизируя их.   -  person Jonathan Leffler    schedule 03.12.2013
comment
Помимо того факта, что clock — плохой выбор методов синхронизации, чтобы измерить производительность чего-то вроде алгоритмов сортировки, вам нужно отсортировать огромное количество элементов. Подумайте о сотнях тысяч или даже миллионах элементов, а не о нескольких вещах, которые пользователь может ввести.   -  person Carey Gregory    schedule 03.12.2013


Ответы (1)


Во-первых, то, как вы рассчитываете время сортировки, неверно:

function_time = (float)(end)/(CLOCKS_PER_SEC);

Должен быть:

function_time = (float)(end-start)/(CLOCKS_PER_SEC);

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

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

person Krypton    schedule 03.12.2013