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

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

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

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

C++ (STL LIST SORT) Сортировка по некольким критериям
Нужна реализация STL C++
C++ реализация алгоритмов библиотеки STL
C++ STL sort()
C++ С++ Builder STL copy/sort multiset
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
asics
Freelance
Эксперт C++
 Аватар для asics
2838 / 1775 / 144
Регистрация: 09.09.2010
Сообщений: 3,842
24.04.2011, 17:20     реализация Shell Sort в stl #2
__beginner__, Самому реализовать не судьба ? Да и вообще, все давно уже реализовано, осатется только копи/паст
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
24.04.2011, 19:43     реализация Shell Sort в stl #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());
}
slowCheetah
11 / 11 / 1
Регистрация: 18.07.2009
Сообщений: 123
24.04.2011, 21:25  [ТС]     реализация Shell Sort в stl #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 зависит от объема входных данных? и при небольшом массиве будет использоваться сортировка, например, вставками, а при большом объеме данных быстрая?
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
25.04.2011, 00:37     реализация Shell Sort в stl #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
    }
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
25.04.2011, 12:11     реализация Shell Sort в stl #6
А я так переживал, когда вызывал std::sort для массива из 3-5 элементов.))) Даже сортировку реализовывал иногда.)))
slowCheetah
11 / 11 / 1
Регистрация: 18.07.2009
Сообщений: 123
25.04.2011, 12:51  [ТС]     реализация Shell Sort в stl #7
а вообще конечно странно, что в нескольких источниках пишут о том, что std::sort реализована на основе быстрой сортировки
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
25.04.2011, 12:54     реализация Shell Sort в stl #8
Цитата Сообщение от __beginner__ Посмотреть сообщение
на основе быстрой сортировки
Если размер меньше 32, используется сортировка вставками. Если больше - двоичная.
В MSVC2010 _ISORT_MAX = 32
slowCheetah
11 / 11 / 1
Регистрация: 18.07.2009
Сообщений: 123
25.04.2011, 13:06  [ТС]     реализация Shell Sort в stl #9
Цитата Сообщение от Deviaphan Посмотреть сообщение
Если размер меньше 32, используется сортировка вставками. Если больше - двоичная.
В MSVC2010 _ISORT_MAX = 32
имеется в виду поразрядная?
если так, то это вообще круто, особенно если учесть то, что у сортировок без сравненний рост O(nlgn)
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
25.04.2011, 13:11     реализация Shell Sort в stl #10
Цитата Сообщение от __beginner__ Посмотреть сообщение
имеется в виду поразрядная?
Имеется в виду разделение диапазона пополам.
Сортировок без сравнения не бывает.

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

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

опять же, взять сортирвку подсчетом - там нет никаких сравнений, но нужны предположения о входных данных
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.04.2011, 15:18     реализация Shell Sort в stl
Еще ссылки по теме:

C++ stl sort vector не сортирует ?!
Не работает сортировка Stl sort C++
C++ Реализация Merge Sort, ошибка в объявлении массивов

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

Или воспользуйтесь поиском по форуму:
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
25.04.2011, 15:18     реализация Shell Sort в stl #14
Я себе radix немного по другому представлял.) Буду знать теперь.)
Yandex
Объявления
25.04.2011, 15:18     реализация Shell Sort в stl
Ответ Создать тему
Опции темы

Текущее время: 12:46. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru