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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Структуры... http://www.cyberforum.ru/cpp-beginners/thread197428.html
Сформировать двоичный файл из элементов, заданной в варианте структуры, распечатать его содержимое, выполнить удаление и добавление элементов в соответствии со своим вариантом, используя для поиска...
C++ производные классы. Попалось такое Задание: Написать программу используя базовый и производный классы, защищенные члены класса, которая создавала массив объекта типа производного класса, инициализировала бы их... http://www.cyberforum.ru/cpp-beginners/thread197413.html
C++ Сортировка методом прямого включения
Привет всем, нужна помощь по сортировки методом включения, помогите разобраться с темой и желательно с задачей: В ремонтной мастерской находяться несколько (N) машин. О них имеются следующие...
Ошибка в программе с потоками C++
Вообщем условие: Задан текстовый файл Input.txt, состоящий из слов. Разделителями между словами является некоторое множество знаков препинания. Найти в каждой строке слова, записанные прописными...
C++ число пробелов http://www.cyberforum.ru/cpp-beginners/thread197404.html
нужно решить задачу:ведите с клавиатуры строку символов, после чего подсчитайте и выведите на экран число пробелов, содержащихся в ней. вот мой код что у меня может быть не правильно? #include...
C++ Бинарные деревья(основные процедуры) Привет всем, объясните кто может пожалуйста на примере(желательно чтоб коды мог проверить на VS 2008) что такое бинарные деревья, а то сам не могу разобраться...(( подробнее

Показать сообщение отдельно
LEQADA
Мастер кустарных методов
227 / 222 / 9
Регистрация: 09.11.2010
Сообщений: 680

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

25.11.2010, 17:27. Просмотров 49753. Ответов 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
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru