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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 343, средняя оценка - 4.70
LEQADA
Мастер кустарных методов
227 / 222 / 9
Регистрация: 09.11.2010
Сообщений: 680
#1

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

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

Всем доброго времени суток. Реализовал Быструю Сортировку на 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)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.11.2010, 17:27
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Алгоритм Быстрой сортировки (Quick Sort) (C++):

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

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

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

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

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

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

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
asics
Freelance
Эксперт С++
2846 / 1783 / 144
Регистрация: 09.09.2010
Сообщений: 3,841
25.11.2010, 18:16 #2
http://www.algolist.manual.ru/sort/quick_sort.php
LEQADA
Мастер кустарных методов
227 / 222 / 9
Регистрация: 09.11.2010
Сообщений: 680
25.11.2010, 18:27  [ТС] #3
asics, по вашей ссылке я не нашёл доказательства.
asics
Freelance
Эксперт С++
2846 / 1783 / 144
Регистрация: 09.09.2010
Сообщений: 3,841
25.11.2010, 18:49 #4
LEQADA, зато там правильный алгоритм быстрой сортировки.
LEQADA
Мастер кустарных методов
227 / 222 / 9
Регистрация: 09.11.2010
Сообщений: 680
26.11.2010, 06:22  [ТС] #5
asics, но там нету доказательства для их алгоритма. Мне нужно Доказательство.
LEQADA
Мастер кустарных методов
227 / 222 / 9
Регистрация: 09.11.2010
Сообщений: 680
26.11.2010, 06:39  [ТС] #6
Цитата Сообщение от silent_1991 Посмотреть сообщение
*LEQADA*,
Вас попросили доказать что ваш *неверно* работающий алгоритм работает верно. Как, по-вашему, это можно сделать?
Приведите контр пример к моему алгоритму, если считаете его НЕ работающим.
Алгоритм работает. Программа работает. Доказать, что Алгоритм верный.
silent_1991
Эксперт С++
4963 / 3039 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
26.11.2010, 06:44 #7
Да, вроде работает, мне условие сначала показалось неверным.
fasked
Эксперт С++
4934 / 2514 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
26.11.2010, 07:10 #8
LEQADA, во-первых докажите, что алгоритм справляется со своей задачей, то есть либо подготовьте данные заранее, либо напишите функцию, которая проверяет последовательность на неубывание/невозрастание, в общем докажите, что функция сортировки на самом деле сортирует.
во-вторых, если требуется доказать, что этой алгоритм действительно быстрой сортировки, подготовьте специальный набор данных и подсчитайте количество итераций, конечно для этого набора данных должно быть известно верное количество итераций.
Хохол
Эксперт C++
475 / 443 / 13
Регистрация: 20.11.2009
Сообщений: 1,292
26.11.2010, 07:35 #9
В Кормене, например, доказательство есть.
LEQADA
Мастер кустарных методов
227 / 222 / 9
Регистрация: 09.11.2010
Сообщений: 680
26.11.2010, 11:32  [ТС] #10
Цитата Сообщение от fasked Посмотреть сообщение
LEQADA, во-первых докажите, что алгоритм справляется со своей задачей...
Вот это я и спрашиваю. Надо это Доказать.

Хохол, Кормен это что?
silent_1991
Эксперт С++
4963 / 3039 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
26.11.2010, 11:35 #11
LEQADA, очевидно, фамилия.
Mr.X
Эксперт С++
3049 / 1694 / 265
Регистрация: 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), то сортировка является быстрой.
fasked
Эксперт С++
4934 / 2514 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
26.11.2010, 15:38 #13
Сообщение было отмечено автором темы, экспертом или модератором как ответ
LEQADA, А вы читаете только не больше 10 слов из сообщений?
Цитата Сообщение от fasked Посмотреть сообщение
во-первых докажите, что алгоритм справляется со своей задачей
и далее,
Цитата Сообщение от fasked Посмотреть сообщение
то есть либо подготовьте данные заранее, либо напишите функцию, которая проверяет последовательность на неубывание/невозрастание, в общем докажите, что функция сортировки на самом деле сортирует.
1) Подготовьте данные заранее:
Создайте заготовки данных, например, в файле. Где будут храниться начальная последовательность - несортированная, и эталонная - сортированная. Эти данные заведомо правильные. Подготовьте средние и крайние случаи. Применяете алгоритм к начальной последовательности и сравниваете ее с эталоном.

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

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

Не по теме:

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

MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.11.2012, 11:37
Привет! Вот еще темы с ответами:

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

Параллельный алгоритм быстрой сортировки (quicksort) - C++
Как реализовать параллельный алгоритм быстрой сортировки на C++? Необходимо в последовательном алгоритме быстрой сортировки...

Разработать эффективный алгоритм быстрой сортировки - C++
Быстрая сортировка. Разработайте эффективный алгоритм для упорядочивания n элементов таким образом, чтобы все отрицательные элементы...

Алгоритм сортировки In-place merge sort - C++
Для здачи лабораторной нужно написать алгоритм сортировки vector и массивов любых типов данных(как пользовательских так и стандартных),...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
14.11.2012, 11:37
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru