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

LEQADA · Регистрация: 09.11.2010

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

Всем доброго времени суток. Реализовал Быструю Сортировку на 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);
 
}

@asics · 25.11.2010, 18:16

http://www.algolist.manual.ru/sort/quick_sort.php

LEQADA · 25.11.2010, 18:27 **[ТС]**

asics, по вашей ссылке я не нашёл доказательства.

@asics · 25.11.2010, 18:49

LEQADA, зато там правильный алгоритм быстрой сортировки.

LEQADA · 26.11.2010, 06:22 **[ТС]**

asics, но там нету доказательства для их алгоритма. Мне нужно Доказательство.

LEQADA · 26.11.2010, 06:39 **[ТС]**

Сообщение от silent_1991

*LEQADA*,
Вас попросили доказать что ваш *неверно* работающий алгоритм работает верно. Как, по-вашему, это можно сделать?

Приведите контр пример к моему алгоритму, если считаете его НЕ работающим.
Алгоритм работает. Программа работает. Доказать, что Алгоритм верный.

silent_1991 · 26.11.2010, 06:44

Да, вроде работает, мне условие сначала показалось неверным.

@fasked · 26.11.2010, 07:10

LEQADA, во-первых докажите, что алгоритм справляется со своей задачей, то есть либо подготовьте данные заранее, либо напишите функцию, которая проверяет последовательность на неубывание/невозрастание, в общем докажите, что функция сортировки на самом деле сортирует.
во-вторых, если требуется доказать, что этой алгоритм действительно быстрой сортировки, подготовьте специальный набор данных и подсчитайте количество итераций, конечно для этого набора данных должно быть известно верное количество итераций.

@Хохол · 26.11.2010, 07:35

В Кормене, например, доказательство есть.

LEQADA · 26.11.2010, 11:32 **[ТС]**

Сообщение от fasked

LEQADA, во-первых докажите, что алгоритм справляется со своей задачей...

Вот это я и спрашиваю. Надо это Доказать.

Хохол, Кормен это что?

silent_1991 · 26.11.2010, 11:35

LEQADA, очевидно, фамилия.

@Mr.X · 26.11.2010, 12:27

В худшем случае (при сортировке уже отсортированного массива) время работы быстрой сортировки пропорционально 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 · 26.11.2010, 15:38

LEQADA, А вы читаете только не больше 10 слов из сообщений?

Сообщение от fasked

во-первых докажите, что алгоритм справляется со своей задачей

и далее,

Сообщение от fasked

то есть либо подготовьте данные заранее, либо напишите функцию, которая проверяет последовательность на неубывание/невозрастание, в общем докажите, что функция сортировки на самом деле сортирует.

1) Подготовьте данные заранее:
Создайте заготовки данных, например, в файле. Где будут храниться начальная последовательность - несортированная, и эталонная - сортированная. Эти данные заведомо правильные. Подготовьте средние и крайние случаи. Применяете алгоритм к начальной последовательности и сравниваете ее с эталоном.

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

3) Найдите математическое доказательство.

Сообщение от LEQADA

Кормен это что?

Кормен - это не что, а автор, профессор компьютерных наук.

silent_1991 · 26.11.2010, 16:00

Сообщение от fasked

Кормен - это не что

Супер

@programina · 14.11.2012, 11:37

Не по теме:

Сообщение от fasked

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

Кэп объяснил:D

@Fabeldyr · 09.11.2015, 18:22

оживлю, пожалуй, мамонта, потому что есть как раз вопрос по данной выше ссылке

мне, собственно, непонятен только один момент:

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);

@vladkuz · 24.11.2016, 16:00

Твоя быстрая сортировка не работает- почитай википедию

Новые блоги и статьи Все статьи Все блоги /
Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .	SDL3 для Web (WebAssembly): Работа со звуком через SDL3_mixer 8Observer8 08.02.2026 Содержание блога Пошагово создадим проект для загрузки звукового файла и воспроизведения звука с помощью библиотеки SDL3_mixer. Звук будет воспроизводиться по клику мышки по холсту на Desktop и по. . .

@asics Freelance 2891 / 1826 / 356 Регистрация: 09.09.2010 Сообщений: 3,841
	25.11.2010, 18:16
	http://www.algolist.manual.ru/sort/quick_sort.php 0

LEQADA Мастер кустарных методов 232 / 227 / 17 Регистрация: 09.11.2010 Сообщений: 680
	25.11.2010, 18:27 [ТС]
	asics, по вашей ссылке я не нашёл доказательства. 0

@asics Freelance 2891 / 1826 / 356 Регистрация: 09.09.2010 Сообщений: 3,841
	25.11.2010, 18:49
	LEQADA, зато там правильный алгоритм быстрой сортировки. 0

LEQADA Мастер кустарных методов 232 / 227 / 17 Регистрация: 09.11.2010 Сообщений: 680
	26.11.2010, 06:22 [ТС]
	asics, но там нету доказательства для их алгоритма. Мне нужно Доказательство. 0

silent_1991 5058 / 3118 / 271 Регистрация: 11.11.2009 Сообщений: 7,044
	26.11.2010, 06:44
	Да, вроде работает, мне условие сначала показалось неверным. 0

@fasked 5045 / 2624 / 241 Регистрация: 07.10.2009 Сообщений: 4,310 Записей в блоге: 5
	26.11.2010, 07:10
	LEQADA, во-первых докажите, что алгоритм справляется со своей задачей, то есть либо подготовьте данные заранее, либо напишите функцию, которая проверяет последовательность на неубывание/невозрастание, в общем докажите, что функция сортировки на самом деле сортирует. во-вторых, если требуется доказать, что этой алгоритм действительно быстрой сортировки, подготовьте специальный набор данных и подсчитайте количество итераций, конечно для этого набора данных должно быть известно верное количество итераций. 1

@Хохол 476 / 444 / 34 Регистрация: 20.11.2009 Сообщений: 1,293
	26.11.2010, 07:35
	В Кормене, например, доказательство есть. 0

silent_1991 5058 / 3118 / 271 Регистрация: 11.11.2009 Сообщений: 7,044
	26.11.2010, 11:35
	LEQADA, очевидно, фамилия. 0

@Mr.X 3225 / 1752 / 436 Регистрация: 03.05.2010 Сообщений: 3,867
	26.11.2010, 12:27
	В худшем случае (при сортировке уже отсортированного массива) время работы быстрой сортировки пропорционально n^2. А ее среднее время работы пропорционально nlog2(n) (log2 здесь логарифм по основанию 2). Т.е. для доказательства достаточно для некоторого фиксированного n сначала замерить время сортировки отсортированного массива, а затем вычислить среднее время сортировки одного массива из некоторого множества из m случайных массивов, и найти их отношение A. Если A при увеличении m стремится к n^2/nlog2(n), т.е. к величине B = n/log2(n) (например, при n = 256 B = 32), то сортировка является быстрой. 0

@vladkuz 0 / 0 / 0 Регистрация: 14.05.2016 Сообщений: 4
	24.11.2016, 16:00
	Твоя быстрая сортировка не работает- почитай википедию 0

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

Решение