Сравнение алгоритмов сортировки Хоара и std::sort

@serega006 · Регистрация: 16.10.2011

Студворк — интернет-сервис помощи студентам

Собственно в универе было дано задание, написать программу которая принимает на вход из файла в структуру имя - производитель-цена и сортирует сначала по производителю, а внутри него по цене. Использовать при этом надо алгоритм Хоара и стд сорт. Далее надо было сравнить скорость работы сортировок при различных объемах данных, при разных наборах входных данных(уже отсортированный, отсортированный в обратную сторону и рандомный). Вообщем результаты исследования меня немного смутили, поэтому создал данную тему с основным вопросом, у меня ошибка в коде или у данных алгоритмов действительно такой большой разброс по времени? Вот код:

C++ (Qt)

#include <iostream>
#include <fstream>
#include <ctime>
#include<windows.h>
#include <algorithm>
#include <string>
 
const int N = 4000;
 
using namespace std;
 
struct t
{
    int name;
    string inc;
    int price;
};
 
 
void QuickSort(t *array, int left, int right)
{
    long base, opposite, p;
    base = left;
    opposite = right;
    while (base != opposite) {
        if (array[base].inc == array[opposite].inc && array[base].price > array[opposite].price)
        {
            t tmp = array[base];
            array[base] = array[opposite];
            array[opposite] = tmp;
        }
        if ((array[base].inc > array[opposite].inc > 0) ^ (base > opposite)) 
        {
            t tmp = array[base];
            array[base] = array[opposite];
            array[opposite] = tmp;
 
            p = base;
            base = opposite;
            if (p < opposite)
                opposite = p + 1; else opposite = p - 1;
        }
        else
        {
            if (base < opposite)
                opposite--; else opposite++;
        };
    };
 
    if (left<base - 1) QuickSort(array, left, base - 1);
    if (base + 1 < right) QuickSort(array, base + 1, right);
}
 
boolean sortik(t &t1, t &t2)
{
    if (t1.inc == t2.inc && t1.price < t2.price) return false;
    else return (t1.inc < t2.inc);
}
 
 
 
void random(t *arr)
{
    srand(time(0));
    for (int i = 0; i < N; i++)
    {
        arr[i].name = i;
        arr[i].inc = (char)(224 + rand() % 31);
        arr[i].price = rand() % 10000;
    }
}
 
void best(t *arr)
{
    random(arr);
    QuickSort(arr, 0, N - 1);
}
 
void bad(t *arr)
{
    best(arr);
    reverse(arr, arr + N);
}
 
void test()
{
    ofstream outest("testresult.txt");
    unsigned int start;
    unsigned int time;
    t arr[N];
 
    best(arr);
 
    start = clock();
    QuickSort(arr, 0, N - 1);
    time = clock() - start;
    outest << "N is " << N << endl << "Quick-Best:" << time << endl;
 
    bad(arr);
 
    start = clock();
    QuickSort(arr, 0, N - 1);
    time = clock() - start;
    outest << "Quick-Bad:" << time << endl;
 
    random(arr);
 
    start = clock();
    QuickSort(arr, 0, N - 1);
    time = clock() - start;
    outest << "Quick-Random:" << time << endl;
 
 
    best(arr);
 
    start = clock();
    sort(arr, arr + N, sortik);
    time = clock() - start;
    outest << "std::Best:" << time << endl;
 
    bad(arr);
 
    start = clock();
    sort(arr, arr + N, sortik);
    time = clock() - start;
    outest << "std::Bad:" << time << endl;
 
    random(arr);
 
    start = clock();
    sort(arr, arr + N, sortik);
    time = clock() - start;
    outest << "std::Random:" << time << endl;
}
 
 
int main()
{
    test();
    return 0;
}

Таблицу с результатом приложил в виде картинки.

@nmcf · 30.09.2015, 23:42

У тебя какая-то неправильная реализация сортировки. Так попробуй:

C++

struct t
{
    int name;
    string inc;
    int price;
    bool operator > (const t &tt)
    {
        return inc > tt.inc || (inc == tt.inc && price > tt.price);
    }
    bool operator < (const t &tt)
    {
        return inc < tt.inc || (inc == tt.inc && price < tt.price);
    }
};
 
 
void QuickSort(t *s_arr, int first, int last)
{
    int i = first, j = last;
    t x = s_arr[(first + last) / 2];
 
    do {
        while (s_arr[i] < x) i++;
        while (s_arr[j] > x) j--;
 
        if(i <= j) {
            if (s_arr[i] > s_arr[j]) swap(s_arr[i], s_arr[j]);
            i++;
            j--;
        }
    } while (i <= j);
 
    if (i < last)
        QuickSort(s_arr, i, last);
    if (first < j)
        QuickSort(s_arr, first, j);
}

@serega006 · 01.10.2015, 17:30 **[ТС]**

Что то у меня с этой сортировкой визуалка один раз сработала и показала результаты намного меньше моих(при 2000 где то 27 вместо 1171), а все следующие разы вылетала с критической ошибкой про неизвестный модуль.

Добавлено через 16 часов 46 минут
Разобрался с проблемой, результаты значительно изменились, спасибо.

@nmcf · 01.10.2015, 21:03

В чём проблема была? Рабочий вариант покажи.

@serega006 · 01.10.2015, 21:22 **[ТС]**

Не в коде проблема, где то с проектом намудрил видимо, просто создал новый и все норм.

@serega006 9 / 9 / 6 Регистрация: 16.10.2011 Сообщений: 423
	01.10.2015, 17:30 [ТС]	3
	Что то у меня с этой сортировкой визуалка один раз сработала и показала результаты намного меньше моих(при 2000 где то 27 вместо 1171), а все следующие разы вылетала с критической ошибкой про неизвестный модуль. Добавлено через 16 часов 46 минут Разобрался с проблемой, результаты значительно изменились, спасибо. 0

@nmcf 7651 / 6456 / 2944 Регистрация: 14.04.2014 Сообщений: 28,148
	01.10.2015, 21:03	4
	В чём проблема была? Рабочий вариант покажи. 1

@serega006 9 / 9 / 6 Регистрация: 16.10.2011 Сообщений: 423
	01.10.2015, 21:22 [ТС]	5
	Не в коде проблема, где то с проектом намудрил видимо, просто создал новый и все норм. 0

Опции темы

Сравнение алгоритмов сортировки Хоара и std::sort

Решение