Пятница, 01.11.2024, 02:29
Главная Регистрация RSS поиск
Приветствую Вас, Гость
Меню сайта
Категории раздела
HTML [44]
Visual C++ и MFC [21]
c++ [78]
php [19]
Javascript [15]
C# [51]
загрузки [0]
XNA [10]
создание игр с помощью xna
Наш опрос
Каким языком программирования вы увлекаетесь
Всего ответов: 2420
Статистика

Онлайн всего: 1
Гостей: 1
Пользователей: 0
Реклама
Главная » Статьи » c++

Сортировка

Исторически зарождение методов машинной сортировки можно отнести еще к прошлому столетию, и за столь длительное время многие специалисты успели испробовать свои силы в этой области. Нет нужды говорить о важности самой области. Сортировка и поиск в той или иной мере присутствуют во всех приложениях; в частности, при обработке больших объемов данных эффективность именно этих операций определяет эффективность, а иногда и работоспособность всей системы. Поэтому можно сказать, что достаточно четкие представления об этой области нужны при решении любой задачи на ЭВМ как обязательные элементы искусства програмирования. В этом уроке мы обсудим простейшие известные способы сортировки.

Примечание: все функции сортировок для удобства представлены в виде шаблонов функций. Следовательно они справедливы для любых простейших типов данных, как-то: char, short, int, unsigned, long, float, double. Для сортировки более сложных элементов данных (строк, объектов), которые будут рассматриваться в последующих уроках, все нижеописанные функции сортировок претерпят незначительные изменения.

Итак, начнем...

Сортировка выбором

Алгоритм сортировки выбором основан на использовании элементов в качестве ключей для сравнения, при этом конце каждого просмотра только один элемент помещается в свою правильную позицию. Этот алгоритм прост, но неэффективен, так как он не учитывает частично или полностью отсортированных наборов данных. Это означает, что число проводимых сравнений зависит только от количества элементов, и не зависит от содержимого набора данных.

Алгоритм:

Пусть в массиве X находится N элементов, тогда для i от 0 до N - 1 необходимо выполнить следующие шаги:

  1. Считаем, что i-ый элемент цепочки является минимальным среди элементов, идущих после него.
  2. Для элементов от X[i + 1] до X[N - 1] выполнить сравнение по ключам и найти наименьший элемент. Назовем его X[min].
  3. Поменять местами X[min] и X[i]. X[min] теперь находится в своей отсортированной позиции.

После окончания цикла массив отсортирован.

Пример:

Возьмем массив из чисел:

5 2 4 -4 3

Первый проход:

5 2 4 -4 3
i min

Замена:

-4 2 4 5 3

Второй проход:

-4 2 4 5 3
i min

Третий проход:

-4 2 4 5 3
i min

Замена:

-4 2 3 5 4

Четвертый проход:

-4 2 3 5 4
i min

Замена:

-4 2 3 4 5

Массив отсортирован

Реализация алгоритма:

// Сортировка выбором

#include <iostream.h>
#include <iomanip.h>
#include <stdlib.h>
#include <time.h>

template <typename T>
void CSort(T array[] /* Сортируемый массив */, int size /* Размер массива */)
{
 // Переменные циклов
 int i, j; 
 // Временная переменная для обмена значений элементов
 T temp; 
 // Переменная для хранения индекса минимального элемента в последовательности
 int min; 

 // Находим наименьший элемент в последовательности и помещаем его
 // в нужную позицию
 for(i = 0; i < size - 1; i++)
 {
 // На каждой итерации определяем элемент с индексом i 
 // как минимальный
 min = i;
 for(j = i + 1; j < size; j++)
 {
 // Поиск минимального элемента
 if(array[j] < array[min])
 min = j;
 }
 // Если переменная min не изменилась, то i-ый элемент
 // находится на своем месте
 if(min == i)
 continue;

 // Иначе меняем i-ый и найденный (меньший) элемент местами
 temp = array[i];
 array[i] = array[min];
 array[min] = temp;
 }
}

// Функция для вывода массива
template <typename T>
void PrintArray(T array[], int size)
{
 // функция setw(n) создает поле для вывода с шириной n символов
 for(int i = 0; i < size; i++)
 {
 if(i % 5 == 0)
 cout << endl;
 cout << setw(15) << array[i];
 }
 cout << endl;
}

// Тестирование
void main()
{
 // Инициализация генератора случайных чисел
 srand(time(0));
 // Размер массивов
 const N = 10;
 
 int i;
 int a[N];
 float b[N];

 // Инициализация массивов случайными числами в диапазоне от -10 до 10
 for(i = 0; i < N; i++)
 {
 a[i] = rand() % 21 - 10;
 b[i] = rand() / (float)32767 * 20 - 10;
 }

 // Вывод массивов
 cout << "Array A:\n";
 PrintArray(a, N); 

 cout << "Array B:\n";
 PrintArray(b, N); 

 // Сортировка массивов
 CSort(a, N);
 CSort(b, N);

 // Вывод отсортированных массивов
 cout << endl;
 cout << "Array A:\n";
 PrintArray(a, N); 

 cout << "Array B:\n";
 PrintArray(b, N); 
}
Категория: c++ | Добавил: slava (29.04.2011)
Просмотров: 1228 | Рейтинг: 0.0/0
Всего комментариев: 0
Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]