IPB
ЛогинПароль:

> Внимание!

1. Пользуйтесь тегами кода. - [code] ... [/code]
2. Точно указывайте язык, название и версию компилятора (интерпретатора).
3. Название темы должно быть информативным.
В описании темы указываем язык!!!

Наладить общение поможет, если вы подпишитесь по почте на новые темы в этом форуме.

2 страниц V  1 2 >  
 Ответить  Открыть новую тему 
> Сортировка данных, C++
сообщение
Сообщение #1


Знаток
****

Группа: Пользователи
Сообщений: 306
Пол: Мужской
Реальное имя: Евгений

Репутация: -  0  +


Доброго времени суток, Уважаемые Форумчане! На форуме приведена реализация множества сортировок на Паскале. Где я могу найти их реализацию на языке С++? Если такая имеется у кого-либо, то буду очень признателен, если выложите... good.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Гость






На АлгоЛисте есть...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Знаток
****

Группа: Пользователи
Сообщений: 306
Пол: Мужской
Реальное имя: Евгений

Репутация: -  0  +


Цитата(volvo @ 3.05.2008 19:28) *

На АлгоЛисте есть...

О! Спасибо большое...тут даже с поянениями)) А вот ещё что: нет какого-нибудь класса с уже реализованными методами сортировки? а то времени особо на реализацию нет...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Гость






К любому контейнеру STL можно применять алгоритм сортировки std::sort, чем не готовый класс?
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Пионер
**

Группа: Пользователи
Сообщений: 86
Пол: Мужской
Реальное имя: Илья

Репутация: -  1  +


Цитата
О! Спасибо большое...тут даже с поянениями)) А вот ещё что: нет какого-нибудь класса с уже реализованными методами сортировки? а то времени особо на реализацию нет...


Есть STL, подключаешь <algorithm> и юзаешь сортировки. smile.gif

Например, квик сорт:

#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;
}



--------------------
Я бы изменил мир, да Бог не дает исходников.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Знаток
****

Группа: Пользователи
Сообщений: 306
Пол: Мужской
Реальное имя: Евгений

Репутация: -  0  +


Цитата(first_day @ 3.05.2008 20:06) *

Есть STL, подключаешь <algorithm> и юзаешь сортировки. smile.gif

Например, квик сорт:

#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;
}



В задании непосредственно нужно свой класс с алгоритмами сортировок написать... Какие методы относятся к простым алгоритмам прямой сортировки?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Гость






К простым - наверное все-таки сортировка выбором, пузырьком и простыми вставками. Может быть - Шелл.

Ну, а прямой или обратной - это уж как направление задашь, любой алгоритм должен уметь сортировать в обоих направлениях.

Что именно не получается с написанием класса? По ссылке же приведены даже шаблонные процедуры, просто собрать их под одной крышей...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #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;
}


 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Гость






Ну, в принципе, можно сделать так:
template <class T>
void setMin(T& val) {
val = static_cast<T>(std::numeric_limits<double>::min());
}

, для большинства POD-типов будет работать (с целочисленными, вещественными и char-ами точно работает)
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Знаток
****

Группа: Пользователи
Сообщений: 306
Пол: Мужской
Реальное имя: Евгений

Репутация: -  0  +


Цитата(volvo @ 10.05.2008 19:34) *


val = static_cast<T>(std::numeric_limits<double>::min());



Не могли бы вы пояснить эту строчку?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Гость






Что именно непонятно в этой строчке? Берем из класса numeric_limits стандартной библиотеки минимально возможное значение типа double, и приводим его static_cast ом к типу, с которым работаем (т.е., к типу T)...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Знаток
****

Группа: Пользователи
Сообщений: 306
Пол: Мужской
Реальное имя: Евгений

Репутация: -  0  +


Цитата(volvo @ 11.05.2008 13:43) *

Что именно непонятно в этой строчке? Берем из класса numeric_limits стандартной библиотеки минимально возможное значение типа double, и приводим его static_cast ом к типу, с которым работаем (т.е., к типу T)...

Ну в общем я и хотел узнать о static_cast и numeric_limits smile.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #13


Знаток
****

Группа: Пользователи
Сообщений: 306
Пол: Мужской
Реальное имя: Евгений

Репутация: -  0  +


Допустим, я хочу проверить работу различных сортировок на массиве из 1000 элементов. Как инициализировать массив случайными числами? то есть с помощью random.
Возможно ли в программе организовать какой-нибудь таймер, чтобы засечь время работы метода сортировки, для дальнейшего сравнения быстродействия?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #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;
}

 К началу страницы 
+ Ответить 
сообщение
Сообщение #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() не описана.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #16


Гость






#include <iostream>
#include <windows.h>
 К началу страницы 
+ Ответить 
сообщение
Сообщение #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. И вообще, такой метод проверки эффективности методов имеет право на существование?) и есть ли какие-нибудь другие способы?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #18


Гость






Цитата
что мы делаем этой функцией
Инициализируем генератор случайных чисел тем значением, которое в данное время находится в системном таймере (фактически - случайное число). Это аналог Randomize, я же написал там...

Цитата
Допустим, выводится time = 312. Как это адаптировать к реальному времени?
312 миллисекунд... Но учти, что у этой функции довольно высокая погрешность - порядка 55 мс... Если хочешь точнее - смотри в сторону QueryPerformanceCounter или RDTSC. Вот тут я об этом написал: Как замерить время выполнения программы?
 К началу страницы 
+ Ответить 
сообщение
Сообщение #19


Знаток
****

Группа: Пользователи
Сообщений: 306
Пол: Мужской
Реальное имя: Евгений

Репутация: -  0  +


Всё работаю над этой программой... У меня возникла идея реализовать что-то вроде менюшки. Какие библиотеки нужно подключать и вообще какие основные функции для вывода текста различных цветов, ну и вобщем для вывода?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #20


Знаток
****

Группа: Пользователи
Сообщений: 306
Пол: Мужской
Реальное имя: Евгений

Репутация: -  0  +


Вот собрал все основные методы в одну прогу. Она сортирует данные целого типа. Как её видоизменить, чтобы была возможность работы с данными вещественного, строкового и т.п. типа?


Прикрепленные файлы
Прикрепленный файл  SortX.cpp ( 11.65 килобайт ) Кол-во скачиваний: 240
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

2 страниц V  1 2 >
 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 28.03.2024 23:44
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name