Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

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

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

25.11.2010, 17:27. Просмотров 54408. Ответов 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
Лучшие ответы (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++
Реализовать алгоритм быстрой сортировки. Суть алгоритма: из исходного массива выбирается нулевой элемент, после чего массив разделяется на...

16
Fabeldyr
99 / 13 / 2
Регистрация: 11.09.2014
Сообщений: 142
Завершенные тесты: 1
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
vladkuz
0 / 0 / 0
Регистрация: 14.05.2016
Сообщений: 4
24.11.2016, 16:00 #17
Твоя быстрая сортировка не работает- почитай википедию
0
24.11.2016, 16:00
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.11.2016, 16:00
Привет! Вот еще темы с ответами:

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

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

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

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


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

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

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