Форум программистов, компьютерный форум CyberForum.ru

Алгоритм Быстрой сортировки (Quick Sort) - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 343, средняя оценка - 4.70
LEQADA
Мастер кустарных методов
 Аватар для LEQADA
227 / 222 / 9
Регистрация: 09.11.2010
Сообщений: 680
25.11.2010, 17:27     Алгоритм Быстрой сортировки (Quick Sort) #1
Всем доброго времени суток. Реализовал Быструю Сортировку на C++. Всё работает. Только препод требует доказать, что мой алгоритм правильный. Не знаю как это сделать... Помогите пожалуйста. Вот код:
Файл qs.cpp:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include "qs.h"
using namespace std;
 
 
void print(int arr[], int n) {
    for (int i = 0; i <n; i++) {
    cout << arr[i] << "-";
    }
    cout << endl;
}
 
int main ()
{int n;
    
    int i;
    cout<<"Array Size: ";
    cin>> n;
    cout<<endl;
    int* arr=new int [n];
    for (i=0;i<n;i++) {
    cout << "Array[" << i+1 << "]: ";
    cin >>  arr[i];
    cout<<endl;
    }
    print(arr,n);
    quickSort(arr, 0, n-1);
    print(arr,n);
 
}
Файл qs.h:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
using namespace std;
 
void quickSort(int arr[], int left, int right) {
    int i = left, j = right;
    int tmp;
    int pivot = arr[(left + right) / 2];
 
    /* partition */
    while (i <= j) {
        while (arr[i] < pivot)
        i++;
        while (arr[j] > pivot)
        j--;
        if (i <= j) {
            tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
            i++;
            j--;
        }
    };
 
    /* recursion */
    if (left < j)
    quickSort(arr, left, j);
    if (i < right)
    quickSort(arr, i, right);
 
}
Лучшие ответы (1)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
asics
Freelance
Эксперт C++
 Аватар для asics
2838 / 1775 / 144
Регистрация: 09.09.2010
Сообщений: 3,842
25.11.2010, 18:16     Алгоритм Быстрой сортировки (Quick Sort) #2
http://www.algolist.manual.ru/sort/quick_sort.php
LEQADA
Мастер кустарных методов
 Аватар для LEQADA
227 / 222 / 9
Регистрация: 09.11.2010
Сообщений: 680
25.11.2010, 18:27  [ТС]     Алгоритм Быстрой сортировки (Quick Sort) #3
asics, по вашей ссылке я не нашёл доказательства.
asics
Freelance
Эксперт C++
 Аватар для asics
2838 / 1775 / 144
Регистрация: 09.09.2010
Сообщений: 3,842
25.11.2010, 18:49     Алгоритм Быстрой сортировки (Quick Sort) #4
LEQADA, зато там правильный алгоритм быстрой сортировки.
LEQADA
Мастер кустарных методов
 Аватар для LEQADA
227 / 222 / 9
Регистрация: 09.11.2010
Сообщений: 680
26.11.2010, 06:22  [ТС]     Алгоритм Быстрой сортировки (Quick Sort) #5
asics, но там нету доказательства для их алгоритма. Мне нужно Доказательство.
LEQADA
Мастер кустарных методов
 Аватар для LEQADA
227 / 222 / 9
Регистрация: 09.11.2010
Сообщений: 680
26.11.2010, 06:39  [ТС]     Алгоритм Быстрой сортировки (Quick Sort) #6
Цитата Сообщение от silent_1991 Посмотреть сообщение
*LEQADA*,
Вас попросили доказать что ваш *неверно* работающий алгоритм работает верно. Как, по-вашему, это можно сделать?
Приведите контр пример к моему алгоритму, если считаете его НЕ работающим.
Алгоритм работает. Программа работает. Доказать, что Алгоритм верный.
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
26.11.2010, 06:44     Алгоритм Быстрой сортировки (Quick Sort) #7
Да, вроде работает, мне условие сначала показалось неверным.
fasked
Эксперт C++
 Аватар для fasked
4924 / 2504 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
26.11.2010, 07:10     Алгоритм Быстрой сортировки (Quick Sort) #8
LEQADA, во-первых докажите, что алгоритм справляется со своей задачей, то есть либо подготовьте данные заранее, либо напишите функцию, которая проверяет последовательность на неубывание/невозрастание, в общем докажите, что функция сортировки на самом деле сортирует.
во-вторых, если требуется доказать, что этой алгоритм действительно быстрой сортировки, подготовьте специальный набор данных и подсчитайте количество итераций, конечно для этого набора данных должно быть известно верное количество итераций.
Хохол
Эксперт C++
 Аватар для Хохол
475 / 443 / 13
Регистрация: 20.11.2009
Сообщений: 1,292
26.11.2010, 07:35     Алгоритм Быстрой сортировки (Quick Sort) #9
В Кормене, например, доказательство есть.
LEQADA
Мастер кустарных методов
 Аватар для LEQADA
227 / 222 / 9
Регистрация: 09.11.2010
Сообщений: 680
26.11.2010, 11:32  [ТС]     Алгоритм Быстрой сортировки (Quick Sort) #10
Цитата Сообщение от fasked Посмотреть сообщение
LEQADA, во-первых докажите, что алгоритм справляется со своей задачей...
Вот это я и спрашиваю. Надо это Доказать.

Хохол, Кормен это что?
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
26.11.2010, 11:35     Алгоритм Быстрой сортировки (Quick Sort) #11
LEQADA, очевидно, фамилия.
Mr.X
Эксперт С++
 Аватар для Mr.X
2801 / 1577 / 247
Регистрация: 03.05.2010
Сообщений: 3,663
26.11.2010, 12:27     Алгоритм Быстрой сортировки (Quick Sort) #12
В худшем случае (при сортировке уже отсортированного массива) время работы быстрой сортировки пропорционально n^2. А ее среднее время работы пропорционально n*log2(n) (log2 здесь логарифм по основанию 2).
Т.е. для доказательства достаточно для некоторого фиксированного n сначала замерить время сортировки отсортированного массива, а затем вычислить среднее время сортировки одного массива из некоторого множества из m случайных массивов, и найти их отношение A. Если A при увеличении m стремится к n^2/n*log2(n), т.е. к величине B = n/log2(n) (например, при n = 256 B = 32), то сортировка является быстрой.
fasked
Эксперт C++
 Аватар для fasked
4924 / 2504 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
26.11.2010, 15:38     Алгоритм Быстрой сортировки (Quick Sort) #13
Сообщение было отмечено автором темы, экспертом или модератором как ответ
LEQADA, А вы читаете только не больше 10 слов из сообщений?
Цитата Сообщение от fasked Посмотреть сообщение
во-первых докажите, что алгоритм справляется со своей задачей
и далее,
Цитата Сообщение от fasked Посмотреть сообщение
то есть либо подготовьте данные заранее, либо напишите функцию, которая проверяет последовательность на неубывание/невозрастание, в общем докажите, что функция сортировки на самом деле сортирует.
1) Подготовьте данные заранее:
Создайте заготовки данных, например, в файле. Где будут храниться начальная последовательность - несортированная, и эталонная - сортированная. Эти данные заведомо правильные. Подготовьте средние и крайние случаи. Применяете алгоритм к начальной последовательности и сравниваете ее с эталоном.

2) Напишите функцию, которая проверяет последовательность на неубывание или невозрастание:
здесь даже никаких объяснений не надо.

3) Найдите математическое доказательство.
Цитата Сообщение от LEQADA Посмотреть сообщение
Кормен это что?
Кормен - это не что, а автор, профессор компьютерных наук.
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
26.11.2010, 16:00     Алгоритм Быстрой сортировки (Quick Sort) #14
Цитата Сообщение от fasked Посмотреть сообщение
Кормен - это не что
Супер
programina
14.11.2012, 11:37
  #15

Не по теме:

Цитата Сообщение от fasked Посмотреть сообщение
1) Подготовьте данные заранее:
Создайте заготовки данных, например, в файле. Где будут храниться начальная последовательность - несортированная, и эталонная - сортированная. Эти данные заведомо правильные. Подготовьте средние и крайние случаи. Применяете алгоритм к начальной последовательности и сравниваете ее с эталоном.
2) Напишите функцию, которая проверяет последовательность на неубывание или невозрастание:
здесь даже никаких объяснений не надо.
3) Найдите математическое доказательство.
Кэп объяснил

Fabeldyr
 Аватар для Fabeldyr
4 / 4 / 1
Регистрация: 11.09.2014
Сообщений: 63
Завершенные тесты: 1
09.11.2015, 18:22     Алгоритм Быстрой сортировки (Quick Sort) #16
оживлю, пожалуй, мамонта, потому что есть как раз вопрос по данной выше ссылке

мне, собственно, непонятен только один момент:
C++ (Qt)
1
if ( N > i ) quickSortR(a+i, N-i);
в первом аргументе функции складывается массив и константа - как такое возможно?

Добавлено через 32 минуты
сам нашёл ответ =))
Цитата Сообщение от Акелла Посмотреть сообщение
эх вы=))) это же основа еще великого Си=)))
имя массива - указатель на его первый елемент=) a+i - сдвиг по маиву на i элементов
з.ы. однако, данный алгоритм почему-то не работает

Добавлено через 32 минуты
нашёл почему не работает - пришлось расписывать все шаги компа на бумажке
вот в этой строке ошибка:
C++ (Qt)
1
if ( j > 0 ) quickSortR(a, j);
должно быть
C++ (Qt)
1
if ( j > 0 ) quickSortR(a, j + 1);
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.11.2016, 16:00     Алгоритм Быстрой сортировки (Quick Sort)
Еще ссылки по теме:

Алгоритм быстрой сортировки - посчитать количество перестановок и сравнений элементов массивов C++
Qvick-sort алгоритм быстрой сортировки. Гляньте плс( C++
Алгоритм быстрой сортировки C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
vladkuz
0 / 0 / 0
Регистрация: 14.05.2016
Сообщений: 4
24.11.2016, 16:00     Алгоритм Быстрой сортировки (Quick Sort) #17
Твоя быстрая сортировка не работает- почитай википедию
Yandex
Объявления
24.11.2016, 16:00     Алгоритм Быстрой сортировки (Quick Sort)
Ответ Создать тему
Опции темы

Текущее время: 12:11. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru