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

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

Войти
Регистрация
Восстановить пароль
 
hardline
Сообщений: n/a
#1

Time Limit Randomized Quicksort - C++

07.11.2013, 00:17. Просмотров 213. Ответов 0
Метки нет (Все метки)

Помогите, пожалуйста, сдаю программу с этой сортировкой в систему контеста, выдает таймлимит на 91ом из 100 тесте. Что делать? Вроде как всё учёл при сортировке. Буду безмерно благодарен.

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include <iostream>
#include <vector>
#include <cstdlib>
#include <iterator>
#include <utility>
 
using namespace std;
 
template <typename T>
void swaping (T &a, T &b)
{
    T c;
    c = a;
    a = b;
    b = c;
}
 
template<class RandomAccessIterator>
RandomAccessIterator partitioning (RandomAccessIterator first,
                             RandomAccessIterator last)
{
    RandomAccessIterator beg = first - 1;
    int pivot = *(last - 1);
 
    for (RandomAccessIterator end = first; end != last - 1; ++end)
 
        if (*end < pivot + 1)
        {
            ++beg;
            swaping (*beg, *end);
        }
 
    swaping (*(beg + 1), *(last - 1));
    return (beg + 1);
 
}
 
template<class RandomAccessIterator>
RandomAccessIterator random_partitioning (RandomAccessIterator first,
                                    RandomAccessIterator last)
{
    RandomAccessIterator random_iterator = rand()% (last - first - 1) + first;
    swaping (*(random_iterator), *(last - 1));
    return partitioning<RandomAccessIterator> (first, last);
}
 
template<class RandomAccessIterator>
void quick_sort (RandomAccessIterator first,
                 RandomAccessIterator last)
{
    if (first < last - 1)
    {
        RandomAccessIterator median = random_partitioning<RandomAccessIterator> (first, last);
        quick_sort<RandomAccessIterator> (first, median);
        quick_sort<RandomAccessIterator> (median + 1, last);
    }
}
 
template <class RandomAccessIterator>
void quick_sortn (RandomAccessIterator first, RandomAccessIterator last)
{
    while (first < last - 1)
    {
        RandomAccessIterator median = random_partitioning<RandomAccessIterator> (first, last);
        if (median - first < last - median)
        {
            quick_sortn(first, median);
            first = median + 1;
        }
        else
        {
            quick_sortn(median, last);
            last = median;
        }
    }
}
 
int main ()
{
    int size;
    cin >> size;
    vector <int> v;
 
    for (int i = 0; i < size; ++i)
    {
        int inp;
        cin >> inp;
        v.push_back(inp);
    }
 
    //vector <int>::iterator first = v.begin();
    //vector <int>::iterator last = v.end() - 1;
 
    cout << endl;
 
    cout << endl << endl;
 
    quick_sortn<vector <int>::iterator> (v.begin(), v.end());
 
    cout << endl;
 
 
    for (vector <int>::iterator it = v.begin(); it < v.end(); ++it) cout << *it << ' ';
 
    return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.11.2013, 00:17
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Time Limit Randomized Quicksort (C++):

Next_permutation() и Time Limit - C++
Задача https://www.e-olymp.com/ru/problems/364 Мой код: #include &lt;bits/stdc++.h&gt; using namespace std; int main() { int...

Не могу разобраться с заданием "Создайте класс Time с конструкторами Time(), Time( int hour)......" - C++
/* Создайте класс Time с конструкторами Time(), Time( int hour), Time(int hour, int min), Time( int h, int m, int s) и ...

Compile-time и run-time методы и функции - C++
Добрый день. Есть две функции, которые делают идентичную работу: template&lt;bool leftShift, typename T&gt; T byteShift(T data) { ...

Напишите конструктор для инициализации объекта класса Time, который может использовать текущее время, возвращаемое функцией time (). - C++
Помогите пожалуйста написать программу на С++. Просто скоро курсовую сдавать, а классы мы еще не разобрали и не успеваем. Поэтому не знаю...

Класс Time через time(0) - C++
Всем привет. На форуме искал ничего похожего не нашол. Не могу до конца разобраться. В класе 1 член, который держит секунды, которые...

Класс "Время". Двусмысленность между time и std:time(long*) - C++
Здравствуйте. Дали код, сказали есть проблема(скриншот): http://joxi.ru/12MxOENhw14QmJ Код: # include &lt;iostream.h&gt; # include...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.11.2013, 00:17
Привет! Вот еще темы с ответами:

QuickSort на C++11 - C++
Написал быструю сортировку, добился работоспособности и сразу захотелось улучшить сам код. #include &lt;iostream&gt; #include...

Quicksort - C++
Дан массив, необходимо отсортировать его в порядке возрастания. Использую квиксорт, но в одном из тестов не проходит по времени (2с). ...

QuickSort - C++
Помогите с алгоритмом и кодом на C++ быстрой сортировки! Наработок вообще нет!

Что за ошибка: "E2015 Ambiguity between 'time' and 'std::time"? - C++
Коды ошибок: v8.cpp(132): E2015 Ambiguity between 'time' and 'std::time(long *)' v8.cpp(133): E2015 Ambiguity between 'time' and...


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

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

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