HTML [44] |
Visual C++ и MFC [21] |
c++ [78] |
php [19] |
Javascript [15] |
C# [51] |
загрузки [0] |
XNA
[10]
создание игр с помощью xna
|
Главная » Статьи » c++ |
Исторически зарождение методов машинной сортировки можно отнести еще к прошлому столетию, и за столь длительное время многие специалисты успели испробовать свои силы в этой области. Нет нужды говорить о важности самой области. Сортировка и поиск в той или иной мере присутствуют во всех приложениях; в частности, при обработке больших объемов данных эффективность именно этих операций определяет эффективность, а иногда и работоспособность всей системы. Поэтому можно сказать, что достаточно четкие представления об этой области нужны при решении любой задачи на ЭВМ как обязательные элементы искусства програмирования. В этом уроке мы обсудим простейшие известные способы сортировки.
Итак, начнем... Сортировка выборомАлгоритм сортировки выбором основан на использовании элементов в качестве ключей для сравнения, при этом конце каждого просмотра только один элемент помещается в свою правильную позицию. Этот алгоритм прост, но неэффективен, так как он не учитывает частично или полностью отсортированных наборов данных. Это означает, что число проводимых сравнений зависит только от количества элементов, и не зависит от содержимого набора данных. Алгоритм:Пусть в массиве X находится N элементов, тогда для i от 0 до N - 1 необходимо выполнить следующие шаги:
После окончания цикла массив отсортирован. Пример: Возьмем массив из чисел:
Первый проход:
Замена:
Второй проход:
Третий проход:
Замена:
Четвертый проход:
Замена:
Массив отсортирован Реализация алгоритма:// Сортировка выбором #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); } | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Просмотров: 1228 | Рейтинг: 0.0/0 |
Всего комментариев: 0 | |