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

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

Войти
Регистрация
Восстановить пароль
 
ShuricFC
0 / 0 / 0
Регистрация: 08.09.2016
Сообщений: 73
#1

Как оптимизировать быструю сортировку? - C++

22.09.2016, 11:21. Просмотров 196. Ответов 2
Метки нет (Все метки)

Помогите пожалуйста оптимизировать быструю сортировку. Какой лучше выбрать опорный элемент?
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
#include "fstream"
#include <math.h>
using namespace std;
#define MAXSTACK 100000
void sort(int *ar, int L, int R) {
    int i, j, x, buf;
    x = ar[(R+L)/2];
    i = L;
    j = R;
    do
    {
        while (ar[i]<x)
            i++;
        while (ar[j]>x)
            j--;
        if (i <= j) {
            buf = ar[i];
            ar[i] = ar[j];
            ar[j] = buf;
            i++;
            j--;
        }
    } while (i <= j);
 
    if (j>L)
        sort(ar, L, j);
    if (i<R)
        sort(ar, i, R);
}
 
void sortQuick(int *ar, int cnt) {
    int L, R;
    L = 0;
    R = cnt - 1;
    sort(ar, L, R);
}
int main()
{
    ifstream f("input.txt");
    ofstream f1("output.txt");
    int n;
    f >> n;
    int* mas;
    mas = new int[n];
    for (int i = 0; i < n; i++)
    {
        f >> mas[i];
    }
    sortQuick(mas, n );
    for (int i = 0; i < n; i++)
    {
        f1 << mas[i] << " ";
    }
 
    return 0;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.09.2016, 11:21
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Как оптимизировать быструю сортировку? (C++):

Как вставить счетчик в быструю сортировку? - C++
нужно написать счетчик, какой определяет кол-во перестановок и сравнений в быстрой сортировке #include &lt;iostream&gt; #include &lt;ctime&gt; ...

Как вызвать функцию, которая производит быструю сортировку - C++
Подскажите пожалуйста, как в С++ вызвать функцию, которая проводит быструю сортировку

Пример на быструю сортировку - C++
форумчане пожалуйста, приведите пример на быструю сортировку, на одномерный массив, заполненными случайными числами, состоящих из 10...

Нужно написать полную быструю сортировку!!! - C++
Нужно написать полную быструю сортировку, т.е. из массива{3, 10, 2, 5, 1, 8} взять любое число и раскидать вокруг него числа и...

Подскажите как эту сортировку переделать в сортировку по алфавиту? - C++
Подскажите как эту сортировку переделать в сортировку по алфавиту?? vector&lt;std::pair&lt;string, int&gt;&gt; popularAuthor; ...

Сортировку вставками меняем на Пирамидальную сортировку и на Сортировку подсчётом - C++
Здравствуйте. Я не как не могу разобраться.Помогите. У меня есть листинг сортировки вставками: #include &quot;stdafx.h&quot; #include...

2
igorrr37
1859 / 1477 / 231
Регистрация: 21.12.2010
Сообщений: 2,462
Записей в блоге: 11
22.09.2016, 19:30 #2
если число элементов небольшое то она должна досортировывать вставками
0
__General__
24 / 24 / 3
Регистрация: 04.01.2014
Сообщений: 91
Завершенные тесты: 2
23.09.2016, 07:12 #3
Цитата Сообщение от ShuricFC Посмотреть сообщение
Какой лучше выбрать опорный элемент?
я знаю 2 эвристики:
1)брать элемент с рандомным индексом.
2)медиану из 3х элементов (берешь, скажем, первый, последний и из середины - и делаешь опорным тот, значение которого лежит между двумя остальными).

А товарищ выше дал неплохой совет; только это будет уже не быстрая сортировка, а гибрид.
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.09.2016, 07:12
Привет! Вот еще темы с ответами:

Как оптимизировать код? - C++
Вот такой код, написанный для микроконтроллера импульсного блока питания. Просто интересно мнение, что можно поменять и изменить для...

Как оптимизировать код? - C++
Как оптимизировать код, чтобы работала программа быстрее #include &lt;iostream&gt; #include &lt;fstream&gt; #include &lt;iomanip&gt; using namespace...

Сортировку вставками меняем на сортировку слиянием - C++
Код программы выполняет сортировку массива вставками. Как сюда вставить код сортировки массива методом слияния, вместо метода вставками,что...

Оцените и скажите как оптимизировать? - C++
Это моя первая более мение обьемная и продуктивная программа. Написал для знакомых школьников, чтобы подтянули математику (люблю её:)...


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

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

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