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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 46, средняя оценка - 4.85
Даня98
28 / 28 / 8
Регистрация: 13.02.2010
Сообщений: 145
#1

Встроенная сортировка - C++

09.08.2011, 17:09. Просмотров 6812. Ответов 23
Метки нет (Все метки)

Где-то слышал, что в Си++(или в Си) есть втроенная сортивка. Правда ли это? И если да, то как ее использовать?
0
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.08.2011, 17:09
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Встроенная сортировка (C++):

Встроенная функция вектора из векторного класса - C++
template <typename TypeContainer, typename Type, typename Policy> class Container { public: ... TypeContainer GetPointer(); ...

Почему встроенная функция вызывает конструктор копирования? - C++
Почему встроенная функция вызывает конструктор копирования или всегда ли встроенная функция действительно встроеннаая? Но всё по порядку....

Сортировка Шелла. Написал программу, не могу понять, почему сортировка не выполняется - C++
Программа создает динамический массив с рандомным заполнением. Дальше выбор сортировок, пузырьком или сортировка Шелла. Вот она то и не...

Сортировка слиянием. В каком куске кода происходит сортировка и каким именно образом? - C++
Помогите, пожалуйста, разобраться. Подскажите в каком куске кода происходит сортировка и каким именно образом? #include <iostream> ...

Быстрая сортировка (сортировка Хоара) для связных списков - C++
есть у кого готовый алгоритм? или подскажите как реализовать

Быстрая сортировка(сортировка Хоара). Отсортировать фрагмент массива - C++
Мне нужно отсортировать фрагмент массива, расположенный между первым и последним отрицательным элементом. Немогу понять как устоновить...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Сыроежка
Заблокирован
09.08.2011, 17:14 #2
Цитата Сообщение от Даня98 Посмотреть сообщение
Где-то слышал, что в Си++(или в Си) есть втроенная сортивка. Правда ли это? И если да, то как ее использовать?
Есть два основных стандартных алгоритма сортировки: алгоритм С, если память не изменяет,
C++
1
qsort
, и алгоритмы С++
C++
1
std::sort
и некоторые другие варианты этого алгоритма, как, например,
C++
1
std::partial_sort
.
0
Даня98
28 / 28 / 8
Регистрация: 13.02.2010
Сообщений: 145
09.08.2011, 17:19  [ТС] #3
qsort - быстрая сортировка, а в с++ пузырьковая? и как ее применять так чтоли
C++
1
int a[10]; std::cort(a);
0
Сыроежка
Заблокирован
09.08.2011, 17:21 #4
Цитата Сообщение от Даня98 Посмотреть сообщение
qsort - быстрая сортировка, а в с++ пузырьковая? и как ее применять так чтоли
C++
1
int a[10]; std::cort(a);
В С++, как я уже сказал, существует несколько разновидностей сортировки. Если говорить о std::sort, то она тоже быстрая сортировка.

В вашем случае она применяется следующим образом

C++
1
std::sort( a, a + 10 );
Нужно только не забыть включить заголовок <algorithm>
1
Даня98
28 / 28 / 8
Регистрация: 13.02.2010
Сообщений: 145
09.08.2011, 17:23  [ТС] #5
Цитата Сообщение от Сыроежка Посмотреть сообщение
1 std::sort( a, a + 10 );
Что указывает а+10?
0
Сыроежка
Заблокирован
09.08.2011, 18:22 #6
Цитата Сообщение от Даня98 Посмотреть сообщение
Что указывает а+10?
Это задается диапазон элементов массива для сортировки, то есть от первого элемента, указатель на которой передается в 'a' и до элемента, следующего за последним элементом массива., то есть элементы вашего массива имеют адреса: a, a+1, a+2, a+3, a+4, a+5, a+6, a+7, a+8, a+9
А a+ 10 задает границу сортировки. Это как пишется в цикле

C++
1
for ( int i = 0; i < 10; i++ )
То в sort, фактически такой же цикл, только граница цикла задается выражением a + 10.
1
diagon
Higher
1929 / 1195 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
09.08.2011, 18:27 #7
Цитата Сообщение от Даня98 Посмотреть сообщение
в с++ пузырьковая
Сильно оптимизированный вариант быстрой сортировки.
Допустим у вас есть вектор
Тогда сортится он будет таким образом
C++
1
std::sort(vec.begin(), vec.end() );
1
Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
09.08.2011, 20:55 #8
Цитата Сообщение от diagon Посмотреть сообщение
Сильно оптимизированный вариант быстрой сортировки.
Бывают сортировки намного быстрее чем qsort, все от массива зависит, есть сортировки сложностью O(n)
0
Даня98
28 / 28 / 8
Регистрация: 13.02.2010
Сообщений: 145
09.08.2011, 23:34  [ТС] #9
Цитата Сообщение от Olga_ Посмотреть сообщение
Бывают сортировки намного быстрее чем qsort, все от массива зависит, есть сортировки сложностью O(n)
К примеру цифровая сортировка.
0
accept
4822 / 3243 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
10.08.2011, 05:41 #10
Цитата Сообщение от Даня98
qsort - быстрая сортировка, а в с++ пузырьковая? и как ее применять так чтоли
пузырьковая сортировка очень медленная
0
Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
10.08.2011, 08:33 #11
Цитата Сообщение от accept Посмотреть сообщение
пузырьковая сортировка очень медленная
Пузырьковая сортировка самая непригодная, нужно избегать ее как только можно.
А сортировка сложностью O(n) для специальных массив, например, целочисленных с узким диапазоном. Называется сортировка подсчетом, сортирует массив, максимум, за 3 прохождения по нему.
0
diagon
Higher
1929 / 1195 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
10.08.2011, 09:07 #12
Цитата Сообщение от Olga_ Посмотреть сообщение
Называется сортировка подсчетом, сортирует массив, максимум, за 3 прохождения по нему.
Это как?
Там же всего один проход по сортируемому массиву и потом еще один по массиву, где количество вхождений хранится.
Но квиксорт ненамного медленнее работает, зато сортирует все, что угодно, включая строки =)
0
Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
10.08.2011, 09:26 #13
Цитата Сообщение от diagon Посмотреть сообщение
Это как?
Там же всего один проход по сортируемому массиву и потом еще один по массиву, где количество вхождений хранится.
Но квиксорт ненамного медленнее работает, зато сортирует все, что угодно, включая строки =)
Первый проход - ищем минимум и максимум, 2 - считаем количество повторений каждого элемента, 3 - заполняем массив.

Согласна, qsort можно для всех использовать массивов, поэтому и оговорка, что сортировка подсчетом - специальная сортировка
0
Даня98
28 / 28 / 8
Регистрация: 13.02.2010
Сообщений: 145
10.08.2011, 10:31  [ТС] #14
Цитата Сообщение от Olga_ Посмотреть сообщение
Пузырьковая сортировка самая непригодная, нужно избегать ее как только можно.
Пузырьковая сортировка тем хороша, что можно сэкономить время на ее запись. Для массивов например в 5 символов qsort писать никто не захочет
0
CyBOSSeR
Эксперт C++
2302 / 1672 / 86
Регистрация: 06.03.2009
Сообщений: 3,675
10.08.2011, 10:35 #15
Даня98, на самом деле, обычно быстрая сортировка используется совместно с какой либо другой, т.е. сначала с помошью быстрой сортировки последовательность разбивается на небольшие части упорядоченные относительно друг друга, а затем каждая часть сортируется более простой сортировкой (хоть тем же пузырьком).
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.08.2011, 10:35
Привет! Вот еще темы с ответами:

Сортировка Шелла и пирамидальная сортировка для символов - C++
Здраствуйте, можете пожалуйста привести пример сортировок шелла и пиромидальной сортировки для символов, а то ничего не могу ...

Сортировка вектора по полю(Сортировка вставками) - C++
Здравствуйте! Нужно написать сортировку вектора по полю weight класса tomato. Вот класс: #pragma once #include &lt;iostream&gt; ...

C/C++ FAQ :: Быстрая сортировка (сортировка Хоара) - C++
Вопрос, скорее академический, по мотивам реализации. Вот в faq приведена реализация этого метода сортировки на C++. В коде есть следующий...

Быстрая сортировка (сортировка методом Хоара) - C++
Ввести массив x1,x2,...,x20 в диапазоне . Требуется расположить отрицательные элементы в порядке убывания. Вывести массивы до и после...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
10.08.2011, 10:35
Ответ Создать тему
Опции темы

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