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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 21, средняя оценка - 4.67
slowCheetah
11 / 11 / 1
Регистрация: 18.07.2009
Сообщений: 123
#1

реализация Shell Sort в stl - C++

24.04.2011, 17:15. Просмотров 2705. Ответов 13
Метки нет (Все метки)

Всем привет!

Кто-нибудь знает, есть ли в Stl реализация сортировки Шелла?
std::sort() реализован на основе быстрой сортировки, есть partial_sort(), stable_sort(), а вот про сортировку Шелла что-то не помню
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.04.2011, 17:15
Здравствуйте! Я подобрал для вас темы с ответами на вопрос реализация Shell Sort в stl (C++):

STL sort() - C++
кто знает и где можно посмотреть за какое время работает сортировка sort() в STL <algorithm>??

stl sort vector не сортирует ?! - C++
class Playlist { private: std::vector<Song> s_container; public: Playlist() { s_container=std::vector<Song>(); } ...

Не работает сортировка Stl sort - C++
вот код сортировки массива обычным stl sort () #include<conio.h> #include<iostream.h> #include<vector.h> #include<algorithm> ...

С++ Builder STL copy/sort multiset - C++
есть две проблемы: 1) ф-ция copy не компилируеться multiset<double> MS,MS2; multiset<double>::iterator msIter; ///здесь...

STL sort строк string по убыванию - C++
Как по возрастанию - знаю:std::vector<std::string> obj; std::string str("asdfghjkl"); vector.push_back(str); for (auto &index : obj)...

(STL LIST SORT) Сортировка по некольким критериям - C++
Здравствуйте! Столкнулся с такой проблемой при сортировке списка. %-) Есть структура: struct PackObject { bool ...

13
asics
Freelance
Эксперт С++
2848 / 1783 / 144
Регистрация: 09.09.2010
Сообщений: 3,841
24.04.2011, 17:20 #2
__beginner__, Самому реализовать не судьба ? Да и вообще, все давно уже реализовано, осатется только копи/паст
0
ForEveR
В астрале
Эксперт С++
7979 / 4738 / 321
Регистрация: 24.06.2010
Сообщений: 10,543
Завершенные тесты: 3
24.04.2011, 19:43 #3
__beginner__, sort реализован не на базе быстрой сортировки. Метод сортировки выбирается по разным параметрам самой функцией sort.
Например, как вы думаете что вызовется при сортировке небольшого вектора?

C++
1
2
3
4
5
6
7
8
9
10
#include <iostream>
#include <vector>
#include <algorithm>
 
int main()
{
    int arr[]={5,4,3,2,1};
    std::vector<int> vec(arr, arr+(sizeof(arr)/sizeof(*arr)));
    std::sort(vec.begin(), vec.end());
}
1
slowCheetah
11 / 11 / 1
Регистрация: 18.07.2009
Сообщений: 123
24.04.2011, 21:25  [ТС] #4
Цитата Сообщение от asics Посмотреть сообщение
__beginner__, Самому реализовать не судьба ? Да и вообще, все давно уже реализовано, осатется только копи/паст
спасибо, кэп
вот до этого действительно сам не дошел бы никогда, слишком это сложно вообще зайдя на какой-нибудь algolist.xxx сделать ее копипаст и использовать дальше

я спросил есть ли в stl ее реализация, я не просил за меня писать ее алгоритм или что-то в этом духе

Добавлено через 4 минуты
Цитата Сообщение от ForEveR Посмотреть сообщение
__beginner__, sort реализован не на базе быстрой сортировки. Метод сортировки выбирается по разным параметрам самой функцией sort.
Например, как вы думаете что вызовется при сортировке небольшого вектора?

C++
1
2
3
4
5
6
7
8
9
10
#include <iostream>
#include <vector>
#include <algorithm>
 
int main()
{
    int arr[]={5,4,3,2,1};
    std::vector<int> vec(arr, arr+(sizeof(arr)/sizeof(*arr)));
    std::sort(vec.begin(), vec.end());
}
т.е. вы хотите сказать, что реализация std::sort зависит от объема входных данных? и при небольшом массиве будет использоваться сортировка, например, вставками, а при большом объеме данных быстрая?
0
ForEveR
В астрале
Эксперт С++
7979 / 4738 / 321
Регистрация: 24.06.2010
Сообщений: 10,543
Завершенные тесты: 3
25.04.2011, 00:37 #5
__beginner__, Верно) В MSVS Так по крайней мере. Кстати, на тот код что я скинул вызывается из std::sort - вспомогательная функция Sort - а из нее сортировка вставками.

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
template<class _RanIt,
    class _Diff> inline
    void _Sort(_RanIt _First, _RanIt _Last, _Diff _Ideal)
    {   // order [_First, _Last), using operator<
    _Diff _Count;
    for (; _ISORT_MAX < (_Count = _Last - _First) && 0 < _Ideal; )
        {   // divide and conquer by quicksort
        pair<_RanIt, _RanIt> _Mid =
            std::_Unguarded_partition(_First, _Last);
        _Ideal /= 2, _Ideal += _Ideal / 2;  // allow 1.5 log2(N) divisions
 
        if (_Mid.first - _First < _Last - _Mid.second)
            {   // loop on second half
            std::_Sort(_First, _Mid.first, _Ideal);
            _First = _Mid.second;
            }
        else
            {   // loop on first half
            std::_Sort(_Mid.second, _Last, _Ideal);
            _Last = _Mid.first;
            }
        }
 
    if (_ISORT_MAX < _Count)
        {   // heap sort if too many divisions
        std::make_heap(_First, _Last);
        std::sort_heap(_First, _Last);
        }
    else if (1 < _Count)
        std::_Insertion_sort(_First, _Last);    // small
    }
2
Deviaphan
Делаю внезапно и красиво
Эксперт С++
1305 / 1220 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
25.04.2011, 12:11 #6
А я так переживал, когда вызывал std::sort для массива из 3-5 элементов.))) Даже сортировку реализовывал иногда.)))
0
slowCheetah
11 / 11 / 1
Регистрация: 18.07.2009
Сообщений: 123
25.04.2011, 12:51  [ТС] #7
а вообще конечно странно, что в нескольких источниках пишут о том, что std::sort реализована на основе быстрой сортировки
0
Deviaphan
Делаю внезапно и красиво
Эксперт С++
1305 / 1220 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
25.04.2011, 12:54 #8
Цитата Сообщение от __beginner__ Посмотреть сообщение
на основе быстрой сортировки
Если размер меньше 32, используется сортировка вставками. Если больше - двоичная.
В MSVC2010 _ISORT_MAX = 32
1
slowCheetah
11 / 11 / 1
Регистрация: 18.07.2009
Сообщений: 123
25.04.2011, 13:06  [ТС] #9
Цитата Сообщение от Deviaphan Посмотреть сообщение
Если размер меньше 32, используется сортировка вставками. Если больше - двоичная.
В MSVC2010 _ISORT_MAX = 32
имеется в виду поразрядная?
если так, то это вообще круто, особенно если учесть то, что у сортировок без сравненний рост O(nlgn)
0
Deviaphan
Делаю внезапно и красиво
Эксперт С++
1305 / 1220 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
25.04.2011, 13:11 #10
Цитата Сообщение от __beginner__ Посмотреть сообщение
имеется в виду поразрядная?
Имеется в виду разделение диапазона пополам.
Сортировок без сравнения не бывает.

"Двоичная", она же "быстрая" имеет сложность от n*log(n), до n*n.
Т.е. всё ништяк, пользуйтесь спокойно. В 99.9% случаев std::sort - правильный выбор.
0
slowCheetah
11 / 11 / 1
Регистрация: 18.07.2009
Сообщений: 123
25.04.2011, 14:22  [ТС] #11
Цитата Сообщение от Deviaphan Посмотреть сообщение
Сортировок без сравнения не бывает.
Кормен пишет, что бывают ) например, подсчетом, та же поразрядная сортировка - там нет сравнений
0
Deviaphan
Делаю внезапно и красиво
Эксперт С++
1305 / 1220 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
25.04.2011, 14:29 #12
Цитата Сообщение от __beginner__ Посмотреть сообщение
Кормен пишет, что бывают
Первый раз слышу! о_0 Ссыль в студию! Буду образованность повышать.
0
slowCheetah
11 / 11 / 1
Регистрация: 18.07.2009
Сообщений: 123
25.04.2011, 14:37  [ТС] #13
Цитата Сообщение от Deviaphan Посмотреть сообщение
Первый раз слышу! о_0 Ссыль в студию! Буду образованность повышать.
http://algolist.manual.ru/sort/radix_sort.php

у кормена глава 8 - сортировка за линейное время, описаны несколько методов и скорость их роста
объяснено, почему у сортировок сравнениями нижняя граница O(nlogn)

опять же, взять сортирвку подсчетом - там нет никаких сравнений, но нужны предположения о входных данных
2
Deviaphan
Делаю внезапно и красиво
Эксперт С++
1305 / 1220 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
25.04.2011, 15:18 #14
Я себе radix немного по другому представлял.) Буду знать теперь.)
0
25.04.2011, 15:18
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.04.2011, 15:18
Привет! Вот еще темы с ответами:

Реализация merge sort на C++14 - C++
Помогите найти (или покажите сами) профессиональную реализацию merge sort с использованием 14-го стандарта. Интернет завален только сишными...

Реализация Merge Sort, ошибка в объявлении массивов - C++
Я пишу реализацию Merge Sort по псевдокоду, и у меня возникла ошибка при объявлении временных массивов &quot;выражение должно иметь константное...

Реализация list из STL - C++
Можете скинуть реализацию класса list из STL.

Нужна реализация STL - C++
Привет всем! Где мне можно найти реализацию map, set, string и list из стандартной библиотеки шаблонов STL на С или С++ (используя...


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

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

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