Мастер кустарных методов
 Аватар для LEQADA
232 / 227 / 17
Регистрация: 09.11.2010
Сообщений: 680
1

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

25.11.2010, 17:27. Показов 135744. Ответов 16
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Всем доброго времени суток. Реализовал Быструю Сортировку на 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);
 
}
2
Лучшие ответы (1)
25.11.2010, 17:27
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
25.11.2010, 17:27
Ответы с готовыми решениями:

Qvick-sort алгоритм быстрой сортировки. Гляньте плс(
пОДСКАЖИТЕ ПЛС ЧТО НЕ ТАК((( Знаю гдето напортачил когда массив в функцию передавалю Гляньте кто-то шарящий может кто поймет в чем дело,...

Метод сортировки quick sort ведомость абитуриентов
Ведомость абитуриентов, сдавших вступительные экзамены в университет, содержит: Ф.И.О. абитуриента, оценки. Определить средний балл по...

Алгоритм Быстрой Сортировки на C++
Можно ли этот алгоритм использовать для последовательности чисел? Просто в книге Сэджвика &quot;Фундаментальные алгоритмы на C++&quot;...

16
Freelance
Эксперт С++
 Аватар для asics
2891 / 1826 / 356
Регистрация: 09.09.2010
Сообщений: 3,841
25.11.2010, 18:16 2
http://www.algolist.manual.ru/sort/quick_sort.php
0
Мастер кустарных методов
 Аватар для LEQADA
232 / 227 / 17
Регистрация: 09.11.2010
Сообщений: 680
25.11.2010, 18:27  [ТС] 3
asics, по вашей ссылке я не нашёл доказательства.
0
Freelance
Эксперт С++
 Аватар для asics
2891 / 1826 / 356
Регистрация: 09.09.2010
Сообщений: 3,841
25.11.2010, 18:49 4
LEQADA, зато там правильный алгоритм быстрой сортировки.
0
Мастер кустарных методов
 Аватар для LEQADA
232 / 227 / 17
Регистрация: 09.11.2010
Сообщений: 680
26.11.2010, 06:22  [ТС] 5
asics, но там нету доказательства для их алгоритма. Мне нужно Доказательство.
0
Мастер кустарных методов
 Аватар для LEQADA
232 / 227 / 17
Регистрация: 09.11.2010
Сообщений: 680
26.11.2010, 06:39  [ТС] 6
Цитата Сообщение от silent_1991 Посмотреть сообщение
*LEQADA*,
Вас попросили доказать что ваш *неверно* работающий алгоритм работает верно. Как, по-вашему, это можно сделать?
Приведите контр пример к моему алгоритму, если считаете его НЕ работающим.
Алгоритм работает. Программа работает. Доказать, что Алгоритм верный.
0
Эксперт С++
5057 / 3117 / 271
Регистрация: 11.11.2009
Сообщений: 7,044
26.11.2010, 06:44 7
Да, вроде работает, мне условие сначала показалось неверным.
0
Эксперт С++
 Аватар для fasked
5044 / 2623 / 241
Регистрация: 07.10.2009
Сообщений: 4,310
Записей в блоге: 5
26.11.2010, 07:10 8
LEQADA, во-первых докажите, что алгоритм справляется со своей задачей, то есть либо подготовьте данные заранее, либо напишите функцию, которая проверяет последовательность на неубывание/невозрастание, в общем докажите, что функция сортировки на самом деле сортирует.
во-вторых, если требуется доказать, что этой алгоритм действительно быстрой сортировки, подготовьте специальный набор данных и подсчитайте количество итераций, конечно для этого набора данных должно быть известно верное количество итераций.
1
Эксперт С++
 Аватар для Хохол
476 / 444 / 34
Регистрация: 20.11.2009
Сообщений: 1,293
26.11.2010, 07:35 9
В Кормене, например, доказательство есть.
0
Мастер кустарных методов
 Аватар для LEQADA
232 / 227 / 17
Регистрация: 09.11.2010
Сообщений: 680
26.11.2010, 11:32  [ТС] 10
Цитата Сообщение от fasked Посмотреть сообщение
LEQADA, во-первых докажите, что алгоритм справляется со своей задачей...
Вот это я и спрашиваю. Надо это Доказать.

Хохол, Кормен это что?
0
Эксперт С++
5057 / 3117 / 271
Регистрация: 11.11.2009
Сообщений: 7,044
26.11.2010, 11:35 11
LEQADA, очевидно, фамилия.
0
Эксперт С++
 Аватар для Mr.X
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
26.11.2010, 12:27 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), то сортировка является быстрой.
0
Эксперт С++
 Аватар для fasked
5044 / 2623 / 241
Регистрация: 07.10.2009
Сообщений: 4,310
Записей в блоге: 5
26.11.2010, 15:38 13
Лучший ответ Сообщение было отмечено как решение

Решение

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

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

3) Найдите математическое доказательство.
Цитата Сообщение от LEQADA Посмотреть сообщение
Кормен это что?
Кормен - это не что, а автор, профессор компьютерных наук.
3
Эксперт С++
5057 / 3117 / 271
Регистрация: 11.11.2009
Сообщений: 7,044
26.11.2010, 16:00 14
Цитата Сообщение от fasked Посмотреть сообщение
Кормен - это не что
Супер
1
programina
14.11.2012, 11:37
  #15

Не по теме:

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

0
 Аватар для Fabeldyr
172 / 21 / 2
Регистрация: 11.09.2014
Сообщений: 235
09.11.2015, 18:22 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);
1
0 / 0 / 0
Регистрация: 14.05.2016
Сообщений: 4
24.11.2016, 16:00 17
Твоя быстрая сортировка не работает- почитай википедию
0
24.11.2016, 16:00
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
24.11.2016, 16:00
Помогаю со студенческими работами здесь

Не алгоритм быстрой сортировки
Просто как подключить эту функцию Не работаеееет #include&lt;iostream&gt; #include&lt;iomanip&gt; #include &lt;algorithm&gt; using namespace...

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

Реализовать алгоритм быстрой сортировки
Реализовать алгоритм быстрой сортировки. Суть алгоритма: из исходного массива выбирается нулевой элемент, после чего массив разделяется на...

Алгоритм быстрой сортировки по убыванию
Я нашёл алгоритм быстрой сортировки по возрастанию: int n, a; //n - количество элементов void qs(int* s_arr, int first, int last) ...

Алгоритм быстрой сортировки против пузырька
Решил проверить утверждение, что быстрая сортировка намного эффективнее пузырьковой. Результат пузырька увидел почти сразу, а быстрой...


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

Или воспользуйтесь поиском по форуму:
17
Ответ Создать тему

Редактор формул (кликните на картинку в правом углу, чтобы закрыть)
Опции темы

Новые блоги и статьи
Ошибка Docker "Got permission denied while trying to connect to the Docker daemon socket at"
hw_wired 14.02.2025
Разработка с использованием Docker может иногда преподносить неожиданные сюрпризы, и одним из самых распространенных камней преткновения становится ошибка с отказом в доступе к демону Docker. . . .
Ошибка "No 'Access-Control-Allow-Origin' header is present on the requested resource"
hw_wired 14.02.2025
При разработке современных веб-приложений нередко сталкиваешься с ошибкой "No 'Access-Control-Allow-Origin' header is present on the requested resource". Эта проблема возникает из-за политики. . .
Как закрыть порт в Linux
hw_wired 14.02.2025
Управление сетевыми портами в Linux - непростая, но важная задача для обеспечения безопасности системы. Каждый открытый порт - это потенциальная уязвимость, через которую злоумышленики могут. . .
Ошибка Angular "Can't bind to 'taskForm' since it isn't a known property of 'form'"
hw_wired 14.02.2025
При разработке веб-приложений на Angular можно столкнуться с ошибкой "Can't bind to '' since it isn't a known property of 'form'". Эта ошибка появляется в консоли браузера когда мы пытаемся. . .
Сообщение Git "Pulling without specifying how to reconcile divergent branches is discouraged"
hw_wired 14.02.2025
При работе с системой контроля версий Git многие разработчики сталкиваются с предупреждающим сообщением "Pulling without specifying how to reconcile divergent branches is discouraged". Это. . .
Как настроить количество пробелов в отступах табов в Visual Studio Code
hw_wired 14.02.2025
Visual Studio Code предоставляет несколько гибких способов настройки табуляции, каждый из которых имеет свои преимущества. Самый простой и наглядный метод - через графический интерфейс настроек, где. . .
Что означает знак восклицания в TypeScript
hw_wired 14.02.2025
TypeScript - удивительный язык программирования, который предоставляет множество возможностей для работы с типами данных. Особый интерес вызывает оператор утверждения ненулевого значения, который. . .
Как свернуть/скрыть секции кода в Visual Studio Code
hw_wired 14.02.2025
Ежедневно мы работам с файлами, содержащими сотни и тысячи строк кода. Навигация по такому объему становится настоящим испытанием, особенно когда нужно быстро найти нужный метод или переменную. . . .
Автоматическое создание файла requirements.tx­t в Python
hw_wired 14.02.2025
Дружелюбная среда для разработки на Python, один из самых широко используемых языков программирования, состоит не только из самого кода, но и целого ряда важных компонентов. И если вы когда-нибудь. . .
Передача переменных окружения в контейнер Docker
hw_wired 14.02.2025
При работе с Docker контейнерами возникает необходимость передать различные настройки и конфигурационные параметры - от строк подключения к базам данных до API ключей. И хотя можно жестко прописать. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru