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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 46, средняя оценка - 4.85
Даня98
 Аватар для Даня98
27 / 27 / 8
Регистрация: 13.02.2010
Сообщений: 145
09.08.2011, 17:09     Встроенная сортировка #1
Где-то слышал, что в Си++(или в Си) есть втроенная сортивка. Правда ли это? И если да, то как ее использовать?
Лучшие ответы (1)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Сыроежка
Заблокирован
09.08.2011, 17:14     Встроенная сортировка #2
Цитата Сообщение от Даня98 Посмотреть сообщение
Где-то слышал, что в Си++(или в Си) есть втроенная сортивка. Правда ли это? И если да, то как ее использовать?
Есть два основных стандартных алгоритма сортировки: алгоритм С, если память не изменяет,
C++
1
qsort
, и алгоритмы С++
C++
1
std::sort
и некоторые другие варианты этого алгоритма, как, например,
C++
1
std::partial_sort
.
Даня98
 Аватар для Даня98
27 / 27 / 8
Регистрация: 13.02.2010
Сообщений: 145
09.08.2011, 17:19  [ТС]     Встроенная сортировка #3
qsort - быстрая сортировка, а в с++ пузырьковая? и как ее применять так чтоли
C++
1
int a[10]; std::cort(a);
Сыроежка
Заблокирован
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>
Даня98
 Аватар для Даня98
27 / 27 / 8
Регистрация: 13.02.2010
Сообщений: 145
09.08.2011, 17:23  [ТС]     Встроенная сортировка #5
Цитата Сообщение от Сыроежка Посмотреть сообщение
1 std::sort( a, a + 10 );
Что указывает а+10?
Сыроежка
Заблокирован
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.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
09.08.2011, 18:27     Встроенная сортировка #7
Цитата Сообщение от Даня98 Посмотреть сообщение
в с++ пузырьковая
Сильно оптимизированный вариант быстрой сортировки.
Допустим у вас есть вектор
Тогда сортится он будет таким образом
C++
1
std::sort(vec.begin(), vec.end() );
Olga_
 Аватар для Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
09.08.2011, 20:55     Встроенная сортировка #8
Цитата Сообщение от diagon Посмотреть сообщение
Сильно оптимизированный вариант быстрой сортировки.
Бывают сортировки намного быстрее чем qsort, все от массива зависит, есть сортировки сложностью O(n)
Даня98
 Аватар для Даня98
27 / 27 / 8
Регистрация: 13.02.2010
Сообщений: 145
09.08.2011, 23:34  [ТС]     Встроенная сортировка #9
Цитата Сообщение от Olga_ Посмотреть сообщение
Бывают сортировки намного быстрее чем qsort, все от массива зависит, есть сортировки сложностью O(n)
К примеру цифровая сортировка.
accept
4838 / 3237 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
10.08.2011, 05:41     Встроенная сортировка #10
Цитата Сообщение от Даня98
qsort - быстрая сортировка, а в с++ пузырьковая? и как ее применять так чтоли
пузырьковая сортировка очень медленная
Olga_
 Аватар для Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
10.08.2011, 08:33     Встроенная сортировка #11
Цитата Сообщение от accept Посмотреть сообщение
пузырьковая сортировка очень медленная
Пузырьковая сортировка самая непригодная, нужно избегать ее как только можно.
А сортировка сложностью O(n) для специальных массив, например, целочисленных с узким диапазоном. Называется сортировка подсчетом, сортирует массив, максимум, за 3 прохождения по нему.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
10.08.2011, 09:07     Встроенная сортировка #12
Цитата Сообщение от Olga_ Посмотреть сообщение
Называется сортировка подсчетом, сортирует массив, максимум, за 3 прохождения по нему.
Это как?
Там же всего один проход по сортируемому массиву и потом еще один по массиву, где количество вхождений хранится.
Но квиксорт ненамного медленнее работает, зато сортирует все, что угодно, включая строки =)
Olga_
 Аватар для Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
10.08.2011, 09:26     Встроенная сортировка #13
Цитата Сообщение от diagon Посмотреть сообщение
Это как?
Там же всего один проход по сортируемому массиву и потом еще один по массиву, где количество вхождений хранится.
Но квиксорт ненамного медленнее работает, зато сортирует все, что угодно, включая строки =)
Первый проход - ищем минимум и максимум, 2 - считаем количество повторений каждого элемента, 3 - заполняем массив.

Согласна, qsort можно для всех использовать массивов, поэтому и оговорка, что сортировка подсчетом - специальная сортировка
Даня98
 Аватар для Даня98
27 / 27 / 8
Регистрация: 13.02.2010
Сообщений: 145
10.08.2011, 10:31  [ТС]     Встроенная сортировка #14
Цитата Сообщение от Olga_ Посмотреть сообщение
Пузырьковая сортировка самая непригодная, нужно избегать ее как только можно.
Пузырьковая сортировка тем хороша, что можно сэкономить время на ее запись. Для массивов например в 5 символов qsort писать никто не захочет
CyBOSSeR
Эксперт C++
 Аватар для CyBOSSeR
2294 / 1664 / 86
Регистрация: 06.03.2009
Сообщений: 3,675
10.08.2011, 10:35     Встроенная сортировка #15
Даня98, на самом деле, обычно быстрая сортировка используется совместно с какой либо другой, т.е. сначала с помошью быстрой сортировки последовательность разбивается на небольшие части упорядоченные относительно друг друга, а затем каждая часть сортируется более простой сортировкой (хоть тем же пузырьком).
Olga_
 Аватар для Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
10.08.2011, 10:57     Встроенная сортировка #16
Цитата Сообщение от Даня98 Посмотреть сообщение
Пузырьковая сортировка тем хороша, что можно сэкономить время на ее запись. Для массивов например в 5 символов qsort писать никто не захочет
Вообще-то речь шла о произвольном массиве. Для маленьких массивчиков вы можете хоть пальчиками элементы передвигать. Хотя, если таких массивчиков будет ОЧЕНЬ много, то пузырьковый метод тоже непригоден.
Даня98
 Аватар для Даня98
27 / 27 / 8
Регистрация: 13.02.2010
Сообщений: 145
10.08.2011, 11:03  [ТС]     Встроенная сортировка #17
Цитата Сообщение от Olga_ Посмотреть сообщение
Для маленьких массивчиков вы можете хоть пальчиками элементы передвигать.
Интересно, а что будет работать быстрее: передвигать элементы циклом или быстрее ифами?
Мне кажется, что ифами.
Olga_
 Аватар для Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
10.08.2011, 11:13     Встроенная сортировка #18
Цитата Сообщение от Даня98 Посмотреть сообщение
Интересно, а что будет работать быстрее: передвигать элементы циклом или быстрее ифами?
Мне кажется, что ифами.
Даня98, кто вам мешает провести эксперимент? Все зависит как вы эти ифы и циклы использовать хотите. Если массив маленький, то хорошее распределение ифов (либо другой метод) будет быстрее
Даня98
 Аватар для Даня98
27 / 27 / 8
Регистрация: 13.02.2010
Сообщений: 145
10.08.2011, 11:17  [ТС]     Встроенная сортировка #19
Цитата Сообщение от Olga_ Посмотреть сообщение
кто вам мешает провести эксперимент?
Проведу, только подскажите как таймер использовать?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.08.2011, 11:20     Встроенная сортировка
Еще ссылки по теме:

2 сортировки: пирамидальная сортировка и сортировка слиянием C++
Сортировка методом "быстрая сортировка" C++
C++ Сортировка Хоара / Быстрая сортировка

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

Или воспользуйтесь поиском по форуму:
Olga_
 Аватар для Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
10.08.2011, 11:20     Встроенная сортировка #20
Цитата Сообщение от Даня98 Посмотреть сообщение
Проведу, только подскажите как таймер использовать?
Можно, например, так. В итоге подсчитаете количество секунд на эксперимент.

#include<time.h>

long t;
t = time(NULL);
// эксперимент
cout << time(NULL) - t;
Yandex
Объявления
10.08.2011, 11:20     Встроенная сортировка
Ответ Создать тему
Опции темы

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