Программа должна сортировать массивы двумя способами. Заполнение массивов выполнять автоматически, с помощью генератора случайных чисел rand . Каждый алгоритм сортировки оформить как отдельную функцию, которая возвращает значение характеризуемое трудоемкость алгоритма (например, количество сравнений чисел или время, которое было потрачено на сортировку). Выполнить сравнение алгоритмов на предмет эффективности.
- Сортировка выбором. Сначала выполняется поиск минимального элемента в массиве, после чего сохраняется во временную переменную. Затем этот элемент удаляется в массиве, а все последующие за ним элементы передвигаются на одну позицию влево. После этого сохраненный элемент заносится в последнюю позицию, которая освободилась после сдвига элементов влево.
- Шейкер-сортировка. Движение в прямом и обратном направлениях организовать с помощью одного цикла.
Это решение нам предоставила Лилия Марьенко, поблагодарим ее за это. Вот исходник:
#include #include #include #include int SortOtbor(int[], int);//прототип функции Сортировка выбором int ShakerSort(int[], int);//прототип функции Шейкерной сортировки using namespace std; int main() < setlocale(LC_ALL, «rus»); const int size = 4000; //размер массива int array[size] = <>; int array2[size]=<>;//создаем еще один массив, чтобы обе функции сортировок, использовали идентичные масивы(копия массива array) int timeOfSortArray = 0; int timeOfSortArray2 = 0; //заполним массивы случайными числами от 1-го до 800-та srand(time(NULL)); for(int i = 0; i < size; i++) < array[i] = 1 + rand() % 800; array2[i] = array[i];//копируем значения первого массива во второй, чтобы использовать его в функции шейкерной сортировки >//выводим исходный (неотсортированный) массив на экран cout else if (timeOfSortArray2 < timeOfSortArray) < cout else cout int SortOtbor(int Array[], int Size) < int startTime = 0; // начальное время работы функции сортировки int endTime = 0; // конечное время работы функции сортировки int searchTime = 0; //продолжительность работы функции сортировки int min; //минимальный элемент в массиве int index; int temp; // временная переменная для хранения минимального значения элемента startTime = clock(); //начинаем отсчет продолжительности сортировки for (int i = Size — 1; i >= 1; i—) < //задаем начальные значения min = Array[i]; index = i; //цикл перебора элементов массива for (int j = i — 1; j >= 0; j—) < //находим минимальный элемент if (min >Array[j]) < //запоминаем минимальный элемент и его индекс min = Array[j]; index = j; >> //запоминаем минимум temp = Array[index]; for(int x = index; x < i; x++)//сдвигаем элементы влево < Array[x] = Array[x+1]; >Array[i] = temp; > endTime = clock(); // конечное время работы функции сортировки return searchTime = (endTime — startTime); //искомое время работы функции ; > int ShakerSort(int Array2[], int Size) < int startTime = 0; // начальное время работы функции сортировки int endTime = 0; // конечное время работы функции сортировки int searchTime = 0; //продолжительность работы функции сортировки int temp; //буфер int Left, Right; //границы сортировки Left = 1; Right = Size — 1; startTime = clock(); //начинаем отсчет продолжительности сортировки do < for (int i = Right, j = Left; i >= Left, j Array2[i]) < temp = Array2[i]; Array2[i] = Array2[i — 1]; Array2[i — 1] = temp; >if (Array2[j — 1] > Array2[j]) < temp = Array2[j]; Array2[j] = Array2[j — 1]; Array2[j — 1] = temp; >> Left = Left + 1; Right = Right — 1; > while (Left
Код сопровождается большим количеством комментариев, думаю по программе должно быть все понятно. Результат работы программы:
Сортировка массива в Javascript
Сортировка пузырьком в python. Bubble sort in Python
CppStudio.com
747 747 747 747 747 747 747 748 748 749 749 749 749 749 749 750 750 750 751 751 751 751 752 753 754 754 755 755 755 755 755 755 756 756 756 757 757 757 757 758 758 758 758 758 759 759 759 759 759 760 760 760 760 760 760 761 761 761 761 761 762 762 762 763 763 763 763 764 764 764 764 764 764 764 764 764 765 765 765 765 765 765 765 766 766 766 766 766 767 767 767 767 767 767 767 767 768 768 768 768 768 768 769 769 769 769 769 769 769 769 769 769 769 769 770 770 770 770 770 771 771 771 771 771 771 772 772 773 773 773 773 774 774 774 774 774 775 775 775 775 775 775 776 776 776 776 776 777 777 777 777 777 778 778 778 779 779 779 779 779 780 780 780 780 780 780 780 780 780 780 780 780 780 781 781 781 782 782 782 782 782 782 782 783 783 783 783 783 784 784 784 784 785 785 785 786 786 786 786 786 786 787 787 787 788 788 788 788 788 788 788 788 788 788 789 789 789 789 789 789 789 790 790 790 790 791 791 791 791 791 791 791 791 792 792 792 792 792 792 792 793 793 793 793 794 794 794 794 794 794 794 795 795 795 795 795 796 796 796 796 796 797 797 797 797 798 798 798 798 798 798 799 799 799 799 799 799 799 800 800
На сортировку массива методом выбора потрачено: 50000 временных тактов процессора!
На сортировку массива методом «Шейкер» потрачено: 70000 временных тактов процессора!
Более эффективным оказался метод сортировки выбором!
Это всего-лишь фрагмент работы программы, а точнее — его концовка, так как весь массив не было смысла копировать. Как оказалось, Шейкер сортировка выполнялась дольше ,чем сортировка выбором.
P.S. Немного поменял код, так как единицы измерения времени неправильно были указаны.
Источник: cppstudio.com
Сортировка выбором
Требуется отсортировать массив по возрастанию методом сортировки выбором.
Для этого можно воспользоваться следующим алгоритмом.
- Найти максимальный элемент ( max ) в массиве ( arr ).
- Поместить его на последнее место ( j ).
- Элемент, находившийся в конце массива переместить на место, где прежде находился max .
- Уменьшить просматриваемую область массива на единицу ( j – 1 ).
- Снова найти максимальный элемент в оставшейся области.
- Поместить его в конец просматриваемой области массива.
- и так далее.
Программа на языке Паскаль:
const n = 10; var arr: array[1..n] of byte; max, id_max, i, j: byte; begin randomize; for i := 1 to n do begin arr[i] := random(256); write(arr[i]:4) end; writeln; j := n; while j > 1 do begin max := arr[1]; id_max := 1; for i := 2 to j do if arr[i] > max then begin max := arr[i]; id_max := i end; arr[id_max] := arr[j]; arr[j] := max; j := j — 1 end; for i := 1 to n do write(arr[i]:4); end.
Источник: pas1.ru
linarMinachev / Lesson_8 (Task 54).cs
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
| // Задача 54: Задайте двумерный массив. Напишите программу, которая упорядочит по убыванию элементы каждой строки двумерного массива. |
| // Например, задан массив: |
| // 1 4 7 2 |
| // 5 9 2 3 |
| // 8 4 2 4 |
| // В итоге получается вот такой массив: |
| // 7 4 2 1 |
| // 9 5 3 2 |
| // 8 4 4 2 |
| int [ , ] table = new int [ 3 , 4 ] ; |
| FillArrayRandom ( table ) ; |
| PrintArray ( table ) ; |
| SortToLower ( table ) ; |
| Console . WriteLine ( ) ; |
| PrintArray ( table ) ; |
| // Функция заполнения массива рандомно числами от 1 до 9 |
| void FillArrayRandom ( int [ , ] array ) |
| for ( int i = 0 ; i < array . GetLength ( 0 ) ; i ++ ) |
| for ( int j = 0 ; j < array . GetLength ( 1 ) ; j ++ ) |
| array [ i , j ] = new Random ( ) . Next ( 1 , 10 ) ; |
| > |
| > |
| > |
| // Функция сортировки элементов в строке двумерного массива, по убыванию |
| void SortToLower ( int [ , ] array ) |
| for ( int i = 0 ; i < array . GetLength ( 0 ) ; i ++ ) |
| for ( int j = 0 ; j < array . GetLength ( 1 ) ; j ++ ) |
| for ( int k = 0 ; k < array . GetLength ( 1 ) — 1 ; k ++ ) |
| if ( array [ i , k ] < array [ i , k + 1 ] ) |
| int temp = array [ i , k + 1 ] ; |
| array [ i , k + 1 ] = array [ i , k ] ; |
| array [ i , k ] = temp ; |
| > |
| > |
| > |
| > |
| > |
| // Функция вывода двумерного массива |
| void PrintArray ( int [ , ] array ) |
| for ( int i = 0 ; i < array . GetLength ( 0 ) ; i ++ ) |
| for ( int j = 0 ; j < array . GetLength ( 1 ) ; j ++ ) |
| Console . Write ( $» < array [ i , j ] >» ) ; |
| > |
| Console . WriteLine ( ) ; |
| > |
| > |
Источник: gist.github.com