Время выполнения алгоритмов Bubble sort в C - PullRequest
Новая
       6

Время выполнения алгоритмов Bubble sort в C

0 голосов
/ 24 ноября 2018

Привет, я читаю лекцию о структуре данных и алгоритме в моем колледже.Я делаю задание по анализу алгоритма сортировки.Назначения требуют отчета, который включает измерение времени выполнения алгоритма.TA дал нам три набора данных по 30000 целых чисел (в порядке возрастания, в порядке убывания, в произвольном порядке)

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

Для сортировки чисел в порядке убывания требуется 2,445 с в реальном времени и 2,409 с по пользовательскому времени, а 3,217 с в реальном времени и 3,159 с по пользовательской.числа в случайном порядке.Этот результат также о моем алгоритме сортировки выбора.Разве это не наихудший случай по убыванию: 

//file is opened at main function
int* bubble_prj4(FILE *fp_in)
{
    int i, j, temp;

    //arr is declared in header file
    arr = (int*)malloc(sizeof(int) * 30000);
    fread(arr, sizeof(int), 30000, fp_in);
    for(i = 0; i < 29999; i++)
        for(j = 29999; j > i; j--)
            if(arr[j] < arr[j - 1])
            {
                temp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = temp;
            }
    return arr;
}

Я впервые задаю вопрос здесь.Я не знаю, что делаю это правильно.

1 Ответ

0 голосов
/ 24 ноября 2018

Я провел ваши тесты.Вот мои результаты по трем различным наборам данных размером 30 000: 

  dataset  |  time (s)  |   swaps
-----------+------------+----------
random     |  3.588447  | 221476595
descending |  2.588694  | 449985000
ascending  |  1.582666  |         0

Что здесь происходит?Почему рандомизированный набор данных медленнее, чем нисходящий набор данных в наихудшем случае?

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

Сказав, что процедура включает в себя то же количество сравнений, а сложность времени равна O (n 2 ) во всех случаях.

...