Версия для печати темы

Автор: Rocket 3.05.2008 22:14

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

Автор: volvo 3.05.2008 22:28

На http://algolist.manual.ru/sort/index.php есть...

Автор: Rocket 3.05.2008 22:46

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

Автор: volvo 3.05.2008 23:05

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

Автор: first_day 3.05.2008 23:06

#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 23:07

Цитата(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 23:42

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

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

Что именно не получается с написанием класса? По ссылке же приведены даже шаблонные процедуры, просто собрать их под одной крышей...

Автор: Rocket 10.05.2008 22:00

Цитата(volvo @ 5.05.2008 20:42)

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 22:34

Ну, в принципе, можно сделать так:

template <class T>
void setMin(T& val) {
    val = static_cast<T>(std::numeric_limits<double>::min());
}

Автор: Rocket 11.05.2008 16:36

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

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

Автор: volvo 11.05.2008 16:43

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

Автор: Rocket 11.05.2008 17:11

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

Автор: Rocket 11.05.2008 17:41

Допустим, я хочу проверить работу различных сортировок на массиве из 1000 элементов. Как инициализировать массив случайными числами? то есть с помощью random.
Возможно ли в программе организовать какой-нибудь таймер, чтобы засечь время работы метода сортировки, для дальнейшего сравнения быстродействия?

Автор: volvo 11.05.2008 20: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;
}

Автор: Rocket 11.05.2008 20:33

Цитата(volvo @ 11.05.2008 17:16)

...

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

Автор: volvo 11.05.2008 21:03

#include <iostream>
#include <windows.h>

Автор: Rocket 11.05.2008 21:30

Цитата(volvo @ 11.05.2008 17:16)

...

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

srand((unsigned int)time(0)) 

Автор: volvo 11.05.2008 21:40

Автор: Rocket 25.05.2008 18:06

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

Автор: Rocket 4.06.2008 20:52

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


Прикрепленные файлы
 SortX.cpp ( 11.65 килобайт ) Кол-во скачиваний: 244

Автор: volvo 4.06.2008 21:51

Что значит

template <class T>
void work() {
  // и здесь производить все операции, которые пользователь выберет
  // из меню Message(), инстанцируя шаблоны сортировок типом T, например:

                T a[size];
                // для инициализации массива "a" можно написать шаблонную
                // функцию Random, и сделать ее явные специализации для любого
                // типа, с которым ты хочешь работать...
                // Ну, а потом - ...

                int time=GetTickCount(); 
                BubbleSortVer2<T>(a, size);
                time=GetTickCount()-time; 
}

int main() {
  cout << "1: int; 2: double; 3: char; 4: string" << endl;
  cin >> choice;

  switch(choice) {
    case 1:
      Work<int>();
      break;
    case 2:
      Work<double>();
      break;
    case 3:
      Work<char>();
      break;
    case 4:
      Work<string>();
      break;
  }
}

Автор: Rocket 4.06.2008 22:30

Цитата(volvo @ 4.06.2008 18:51)

template <class T>
void work() {
  // и здесь производить все операции, которые пользователь выберет
  // из меню Message(), инстанцируя шаблоны сортировок типом T, например:

                T a[size];
                // для инициализации массива "a" можно написать шаблонную
                // функцию Random, и сделать ее явные специализации для любого
                // типа, с которым ты хочешь работать...
                // Ну, а потом - ...

                int time=GetTickCount(); 
                BubbleSortVer2<T>(a, size);
                time=GetTickCount()-time; 
}

int main() {
  cout << "1: int; 2: double; 3: char; 4: string" << endl;
  cin >> choice;

  switch(choice) {
    case 1:
      Work<int>;
      break;
    case 2:
      Work<double>;
      break;
    case 3:
      Work<char>;
      break;
    case 4:
      Work<string>;
      break;
  }
}

Автор: volvo 4.06.2008 22:49

Ну да, я накосячил, забыл вызов функции... Поправлю в предыдущем посте...

Кстати, у тебя в main() лишняя закрывающая скобка... И еще, чтобы программа компилировалась, надо явно задать специализацию SetMin() для типа string:

void SetMin(string& val) {
    val = "";
}

Автор: Rocket 4.06.2008 23:05

Цитата(volvo @ 4.06.2008 19:49)

void SetMin(string& val) {
    val = "";
}

Автор: volvo 4.06.2008 23:20

Ты чего творишь?

int ch,size;
// Это как понимать? Сначала описываешь массив непонятно какого размера ...
T a[size]; 

// и только потом вводишь собственно размер?
cout<<"Please, enter the size of massive to sort!"<<endl;
cin>>size;

int ch, size;
cout<<"Please, enter the size of massive to sort!"<<endl;
cin>>size;

T *a = new T[size];
... // здесь работа с массивом, ничего не меняется
delete a; 

Автор: Rocket 4.06.2008 23:30

Цитата(volvo @ 4.06.2008 20:20)

Ты чего творишь?

int ch,size;
// Это как понимать? Сначала описываешь массив непонятно какого размера ...
T a[size]; 

// и только потом вводишь собственно размер?
cout<<"Please, enter the size of massive to sort!"<<endl;
cin>>size;

Я бы сделал вот так:

int ch, size;
cout<<"Please, enter the size of massive to sort!"<<endl;
cin>>size;

T *a = new T[size];
... // здесь работа с массивом, ничего не меняется
delete a;