Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
ShuricFC
0 / 0 / 0
Регистрация: 08.09.2016
Сообщений: 73
#1

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

22.09.2016, 11:21. Просмотров 204. Ответов 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
Ответы с готовыми решениями:

Как вставить счетчик в быструю сортировку?
нужно написать счетчик, какой определяет кол-во перестановок и сравнений в быстрой сортировке ...

Как реализовать быструю сортировку для структуры?
Что нужно поправить? #include&lt;iostream&gt; #include&lt;fstream&gt; #include&lt;vector&gt; #include&lt;string&gt;...

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

Пример на быструю сортировку
форумчане пожалуйста, приведите пример на быструю сортировку, на одномерный массив, заполненными...

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

2
igorrr37
1867 / 1483 / 751
Регистрация: 21.12.2010
Сообщений: 2,473
Записей в блоге: 11
22.09.2016, 19:30 #2
если число элементов небольшое то она должна досортировывать вставками
0
__General__
24 / 24 / 12
Регистрация: 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

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

Сортировку вставками меняем на Пирамидальную сортировку и на Сортировку подсчётом
Здравствуйте. Я не как не могу разобраться.Помогите. У меня есть листинг сортировки вставками: ...

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


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

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

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