 Сортировка данных, C++ |
Внимание!
1. Пользуйтесь тегами кода. - [code] ... [/code]
2. Точно указывайте язык, название и версию компилятора (интерпретатора).
3. Название темы должно быть информативным.
В описании темы указываем язык!!!
  |
| Rocket |
 3.05.2008 18:14
Сообщение
#1
|
 Знаток  Группа: Пользователи Сообщений: 306 Пол: Мужской Реальное имя: Евгений Репутация:  0   |
Доброго времени суток, Уважаемые Форумчане! На форуме приведена реализация множества сортировок на Паскале. Где я могу найти их реализацию на языке С++? Если такая имеется у кого-либо, то буду очень признателен, если выложите...
 |
   |
 
|
| volvo |
3.05.2008 18:28
Сообщение
#2
|
|
Гость |
На АлгоЛисте есть...
|
|
|
|
| Rocket |
3.05.2008 18:46
Сообщение
#3
|
|
Знаток Группа: Пользователи Сообщений: 306 Пол: Мужской Реальное имя: Евгений Репутация: 0 |
Цитата(volvo @ 3.05.2008 19:28)  О! Спасибо большое...тут даже с поянениями)) А вот ещё что: нет какого-нибудь класса с уже реализованными методами сортировки? а то времени особо на реализацию нет... |
|
|
|
| volvo |
3.05.2008 19:05
Сообщение
#4
|
|
Гость |
К любому контейнеру STL можно применять алгоритм сортировки std::sort, чем не готовый класс?
|
|
|
|
| first_day |
3.05.2008 19:06
Сообщение
#5
|
 Пионер Группа: Пользователи Сообщений: 86 Пол: Мужской Реальное имя: Илья Репутация: 1 |
Цитата О! Спасибо большое...тут даже с поянениями)) А вот ещё что: нет какого-нибудь класса с уже реализованными методами сортировки? а то времени особо на реализацию нет... Есть STL, подключаешь <algorithm> и юзаешь сортировки.  Например, квик сорт:
#include <iostream>
#include <algorithm>
using namespace std;
int main ()
{
int a[10]={20,2,5,4,3,45,34,1,79,4};
sort(a,a+10);
for(int i=0; i<10; i++)
cout<<a[i]<<" ";
return 0;
}
-------------------- Я бы изменил мир, да Бог не дает исходников.
|
|
|
|
| Rocket |
5.05.2008 19:07
Сообщение
#6
|
|
Знаток Группа: Пользователи Сообщений: 306 Пол: Мужской Реальное имя: Евгений Репутация: 0 |
Цитата(first_day @ 3.05.2008 20:06) Есть STL, подключаешь <algorithm> и юзаешь сортировки. Например, квик сорт:
#include <iostream>
#include <algorithm>
using namespace std;
int main ()
{
int a[10]={20,2,5,4,3,45,34,1,79,4};
sort(a,a+10);
for(int i=0; i<10; i++)
cout<<a[i]<<" ";
return 0;
}
В задании непосредственно нужно свой класс с алгоритмами сортировок написать... Какие методы относятся к простым алгоритмам прямой сортировки? |
|
|
|
| volvo |
5.05.2008 19:42
Сообщение
#7
|
|
Гость |
К простым - наверное все-таки сортировка выбором, пузырьком и простыми вставками. Может быть - Шелл.
Ну, а прямой или обратной - это уж как направление задашь, любой алгоритм должен уметь сортировать в обоих направлениях. Что именно не получается с написанием класса? По ссылке же приведены даже шаблонные процедуры, просто собрать их под одной крышей... |
|
|
|
| Rocket |
10.05.2008 18:00
Сообщение
#8
|
|
Знаток Группа: Пользователи Сообщений: 306 Пол: Мужской Реальное имя: Евгений Репутация: 0 |
Цитата(volvo @ 5.05.2008 20:42) К простым - наверное все-таки сортировка выбором, пузырьком и простыми вставками. Может быть - Шелл. Ну, а прямой или обратной - это уж как направление задашь, любой алгоритм должен уметь сортировать в обоих направлениях. Что именно не получается с написанием класса? По ссылке же приведены даже шаблонные процедуры, просто собрать их под одной крышей... Как реализовать функцию setMin(T& x) для сортировки вставками со сторожевым елементом? Вот собственно сам метод:
template<class T>
inline void insertSortGuarded(T a[], long size) {
T x;
long i, j;
T backup = a[0];
setMin(a[0]);
for ( i=1; i < size; i++) {
x = a[i];
for ( j=i-1; a[j] > x; j--)
a[j+1] = a[j];
a[j+1] = x;
}
for ( j=1; j<size && a[j] < backup; j++)
a[j-1] = a[j];
a[j-1] = backup;
}
|
|
|
|
| volvo |
10.05.2008 18:34
Сообщение
#9
|
|
Гость |
Ну, в принципе, можно сделать так:
template <class T>
void setMin(T& val) {
val = static_cast<T>(std::numeric_limits<double>::min());
}
, для большинства POD-типов будет работать (с целочисленными, вещественными и char-ами точно работает) |
|
|
|
| Rocket |
11.05.2008 12:36
Сообщение
#10
|
|
Знаток Группа: Пользователи Сообщений: 306 Пол: Мужской Реальное имя: Евгений Репутация: 0 |
Цитата(volvo @ 10.05.2008 19:34)
val = static_cast<T>(std::numeric_limits<double>::min());
Не могли бы вы пояснить эту строчку? |
|
|
|
| volvo |
11.05.2008 12:43
Сообщение
#11
|
|
Гость |
Что именно непонятно в этой строчке? Берем из класса numeric_limits стандартной библиотеки минимально возможное значение типа double, и приводим его static_cast ом к типу, с которым работаем (т.е., к типу T)...
|
|
|
|
| Rocket |
11.05.2008 13:11
Сообщение
#12
|
|
Знаток Группа: Пользователи Сообщений: 306 Пол: Мужской Реальное имя: Евгений Репутация: 0 |
Цитата(volvo @ 11.05.2008 13:43) Что именно непонятно в этой строчке? Берем из класса numeric_limits стандартной библиотеки минимально возможное значение типа double, и приводим его static_cast ом к типу, с которым работаем (т.е., к типу T)... Ну в общем я и хотел узнать о static_cast и numeric_limits |
|
|
|
| Rocket |
11.05.2008 13:41
Сообщение
#13
|
|
Знаток Группа: Пользователи Сообщений: 306 Пол: Мужской Реальное имя: Евгений Репутация: 0 |
Допустим, я хочу проверить работу различных сортировок на массиве из 1000 элементов. Как инициализировать массив случайными числами? то есть с помощью random.
Возможно ли в программе организовать какой-нибудь таймер, чтобы засечь время работы метода сортировки, для дальнейшего сравнения быстродействия? |
|
|
|
| volvo |
11.05.2008 16:16
Сообщение
#14
|
|
Гость |
Работа со временем зависит от ОС. Под Win можно сделать так, например:
...
int main() {
const int size = 1000;
int a[size] = {0};
srand((unsigned int)time(0)); // randomize
for(int i = 0; i < size; i++) {
a[i] = rand() % 2000; // случайные числа 0 .. 1999
}
for(int i = 0; i < size; i++) {
cout << a[i] << " ";
}
cout << endl;
int time = GetTickCount(); // засекли время
insertSortGuarded<int>(a, size); // выполнили сортировку
time = GetTickCount() - time; // остановили время
for(int i = 0; i < size; i++) {
cout << a[i] << " ";
}
cout << endl;
cout << "time = " << time << endl; // вывели время
return 0;
}
|
|
|
|
| Rocket |
11.05.2008 16:33
Сообщение
#15
|
|
Знаток Группа: Пользователи Сообщений: 306 Пол: Мужской Реальное имя: Евгений Репутация: 0 |
Цитата(volvo @ 11.05.2008 17:16) Работа со временем зависит от ОС. Под Win можно сделать так, например: ...
int main() {
const int size = 1000;
int a[size] = {0};
srand((unsigned int)time(0)); // randomize
for(int i = 0; i < size; i++) {
a[i] = rand() % 2000; // случайные числа 0 .. 1999
}
for(int i = 0; i < size; i++) {
cout << a[i] << " ";
}
cout << endl;
int time = GetTickCount(); // засекли время
insertSortGuarded<int>(a, size); // выполнили сортировку
time = GetTickCount() - time; // остановили время
for(int i = 0; i < size; i++) {
cout << a[i] << " ";
}
cout << endl;
cout << "time = " << time << endl; // вывели время
return 0;
}
А библиотеку какую нужно подключать? а то компилятор мне выдает ошибку, что GetTickCount() не описана. |
|
|
|
| volvo |
11.05.2008 17:03
Сообщение
#16
|
|
Гость |
#include <iostream>
#include <windows.h>
|
|
|
|
| Rocket |
11.05.2008 17:30
Сообщение
#17
|
|
Знаток Группа: Пользователи Сообщений: 306 Пол: Мужской Реальное имя: Евгений Репутация: 0 |
Цитата(volvo @ 11.05.2008 17:16) Работа со временем зависит от ОС. Под Win можно сделать так, например: ...
int main() {
const int size = 1000;
int a[size] = {0};
srand((unsigned int)time(0)); // randomize
for(int i = 0; i < size; i++) {
a[i] = rand() % 2000; // случайные числа 0 .. 1999
}
for(int i = 0; i < size; i++) {
cout << a[i] << " ";
}
cout << endl;
int time = GetTickCount(); // засекли время
insertSortGuarded<int>(a, size); // выполнили сортировку
time = GetTickCount() - time; // остановили время
for(int i = 0; i < size; i++) {
cout << a[i] << " ";
}
cout << endl;
cout << "time = " << time << endl; // вывели время
return 0;
}
У меня возникло ещё несколько вопросов: 1. Вот что мы делаем этой функцией srand((unsigned int)time(0))
?2. Допустим, выводится time = 312. Как это адаптировать к реальному времени? 3. И вообще, такой метод проверки эффективности методов имеет право на существование?) и есть ли какие-нибудь другие способы? |
|
|
|
| volvo |
11.05.2008 17:40
Сообщение
#18
|
|
Гость |
Цитата что мы делаем этой функцией Инициализируем генератор случайных чисел тем значением, которое в данное время находится в системном таймере (фактически - случайное число). Это аналог Randomize, я же написал там...Цитата Допустим, выводится time = 312. Как это адаптировать к реальному времени? 312 миллисекунд... Но учти, что у этой функции довольно высокая погрешность - порядка 55 мс... Если хочешь точнее - смотри в сторону QueryPerformanceCounter или RDTSC. Вот тут я об этом написал: Как замерить время выполнения программы? |
|
|
|
| Rocket |
25.05.2008 14:06
Сообщение
#19
|
|
Знаток Группа: Пользователи Сообщений: 306 Пол: Мужской Реальное имя: Евгений Репутация: 0 |
Всё работаю над этой программой... У меня возникла идея реализовать что-то вроде менюшки. Какие библиотеки нужно подключать и вообще какие основные функции для вывода текста различных цветов, ну и вобщем для вывода?
|
|
|
|
| Rocket |
4.06.2008 16:52
Сообщение
#20
|
|
Знаток Группа: Пользователи Сообщений: 306 Пол: Мужской Реальное имя: Евгений Репутация: 0 |
Вот собрал все основные методы в одну прогу. Она сортирует данные целого типа. Как её видоизменить, чтобы была возможность работы с данными вещественного, строкового и т.п. типа?
Прикрепленные файлы 
SortX.cpp ( 11.65 килобайт )
Кол-во скачиваний: 190 |
|
|
|
|
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0
|
Текстовая версия | 18.07.2025 17:38 |