Анпоо колледж воронежского института высоких технологий
 Скачать 440.67 Kb.
|
1.4 Принципы программирования сортировки данных.Программирование сортировки данных может быть выполнено на различных языках. Наиболее популярным до сих пор остается язык Cдля системного программирования и C++. Пример такой сортировки приведен в приложении 1 к данной работе.При запуске этого программного кода на локальной машине он создает образец входного файла "input.txt" с 10000 случайными числами. Он сортирует числа и помещает отсортированные числа в файл "output.txt". Он также генерирует файлы с именами 1, 2, ... для хранения отсортированных прогонов. Раздел 2. проблемы, связанные с технологией программирования описание назначения каждого модуля с особенностями его реализации, строится структурная схема программы.В предыдущем разделе мы привели пример сортировки на языке С. Язык С предоставляет пять методов сортировки, которые выглядят следующим образом - Пузырьковая сортировка (или) ExchangeSort. Сортировка по выбору. Сортировка вставкой (или) Линейная сортировка. Быстрая сортировка (или) Сортировка с обменом разделами. Теперь рассмотрим структуру и принципы программирования сортировки на С#.В языке C#также есть библиотеки и функции, которые можно использовать для сортировки данных. Для сортировки данных можно использовать два метода Array.sort()и Array.Reverse()вместе, чтобы отсортировать массив в порядке убывания. Метод Array.Sort()сортирует массив в порядке возрастания. Мы перевернем массив, используя метод Array.Reverse()сортировки массива в порядке убывания. Существует несколько перегрузок этих методов. Правильный синтаксис для использования этих методов следующий. Array.Sort(Array array) Пример использования кодирования сортировки показан ниже. using System; class Sort { public static void Main() { int[] arr = new int[] {2, 10, 5, 8, 4, 11}; Console.WriteLine("Массив до сортировки:\n"); foreach(int value in arr) { Console.Write(value + " "); } Console.WriteLine("\n"); Array.Sort(arr); Array.Reverse(arr); Console.WriteLine("Массив после сортировки:\n"); foreach(int value in arr) { Console.Write(value + " "); } } } Таким образом мы можем отсортировать значения массива и получить вывод: Массив до сортировки: 2 10 5 8 4 11 Массив после сортировки: 11 10 8 5 4 2  Рисунок 1 На рисунке 1 представлен результат сортировки. Результатом сортировки комплексной программой с применением различных методов в том числе каскадной сортировки будет результат, представленный на рисунке 2  Рисунок 2 Полный текст программы представлен в приложении 2 к данной работе Также для сортировки по убыванию в C# можно воспользоваться методом Enumerable.OrderByDescending, который сортирует элементы массива автоматически. Этот метод позволяет избежать изменения исходного массива и вместо него возвращает новый отсортированный массив в соответствии с заданным компаратором. Чаще в C# при сортировке пользуются списками или List. Список в C# - это коллекция сильно типизированных объектов. К этим объектам можно легко получить доступ, используя соответствующий индекс. Вызов индекса дает гибкость при сортировке, поиске и изменении списков, если это необходимо. Проще говоря, List в C# - это обобщенная версия ArrayList. Встроенный метод Sort сортирует элементы или часть элементов в списке. Метод имеет четыре перегрузки: Sort(Comparison Sort(Int32, Int32, IComparer Sort() - Сортирует элементы во всем List Sort(IComparer Компилировать программы на C# можно как в специализированных средах разработки, так и средствами онлайн компиляции и сборки, если такая программа не подразумевает наличие пользовательского интерфейса. Для того, чтобы запрограммировать алгоритм сортировки данных, нам необходимо работать с массивами данных. Для этого зададим временные массивы данных и опишем функцию, которую будем использовать в дальнейшем. Поменяем местами два значения данных в позициях m и n в заданном целочисленном массиве: Publicstaticvoidexchange (int[] data, int m, int n) { int temporary; temporary = data [m]; data [m] = data [n]; data [n] = temporary; } В целом, замена двух значений в массиве ничем не отличается от замены любых двух целых чисел. Предположим, у нас есть следующие целые числа a и b: Inta,b; Intt; a=25; b=35; t=a; a=b; b=t; После того как этот код выполнит свою работу, значение a будет равно 35, а значение b - 25. Таким образом, в функции exchange() выше, если у нас есть два различных элемента массива в позициях m и n, мы, по сути, получаем каждое значение в этих позициях, например, data[m] и data[n], и рассматриваем их так, как если бы они были a и b в приведенном выше коде. Возможно, вам будет полезно проверить, что приведенный выше код делает то, о чем мы говорим, и хороший способ - ввести его непосредственно в интерпретатор C# (csharp), чтобы вы могли убедиться в этом сами. Функция exchange() жизненно важна для всех алгоритмов сортировки следующим образом. Она используется всякий раз, когда обнаруживается, что два элемента расположены не по порядку. Когда это происходит, они меняются местами. Это не означает, что элемент попадает на свое последнее место в массиве. Это просто означает, что на данный момент элементы были переупорядочены, и мы приблизимся к получению отсортированного массива. Алгоритм пузырьковой сортировки работает путем многократного сканирования массива с заменой соседних элементов, которые не в порядке. Наблюдая за этой работой со стратегически расположенным Console.WriteLine() во внешнем цикле, вы увидите, что отсортированный массив растет справа налево. При каждом проходе выбирается самый большой оставшийся элемент и перемещается вправо. Поэтому при каждом проходе не нужно просматривать весь массив, а только начало отсортированной части. Мы определяем количество инверсий как количество пар элементов, которые находятся не по порядку. Они не обязательно должны быть соседними. Если data[7] >data[16], то это инверсия. Каждый раз, когда требуется инверсия, мы также говорим, что происходит соответствующее перемещение данных. Если вы посмотрите на код exchange(), то увидите, что для обмена требуется три перемещения, что происходит очень быстро на большинстве процессоров, но все же составляет значительную стоимость. В массиве длины N может быть не более N⋅N-12 инверсий. Максимальное количество инверсий происходит, когда массив отсортирован в обратном порядке и не имеет одинаковых элементов. Каждый обмен в пузырьковой сортировке удаляет ровно одну инверсию; поэтому пузырьковая сортировка требует O(N2) обменов. PublicstaticvoidIntArrayBubbleSort(int[]data) { inti,j; intN=data.Length; for(j=N-1;j>0;j--){ for(i=0;i if(data[i]>data[i+1]) exchange(data,i,i+1); } } } В алгоритме сортировки вставкой мы строим отсортированный список снизу массива. Мы многократно вставляем следующий элемент в отсортированную часть массива, сдвигая его вниз (используя наш знакомый метод exchange()) в нужную позицию. Для этого потребуется столько же обменов, как и при пузырьковой сортировке, поскольку за один обмен удаляется только одна инверсия. Таким образом, сортировка вставками также требует O(N2) обменов. В среднем сортировка вставками требует в два раза меньше сравнений, чем пузырьковая сортировка, поскольку среднее расстояние, на которое должен переместиться элемент при случайном вводе, равно половине длины сортируемой части. PublicstaticvoidIntArrayInsertionSort(int[]data) { inti,j; intN=data.Length; for(j=1;j for(i=j;i>0&&data[i] exchange(data,i,i-1); } } } Еще одним методом внешней сортировки является метод Шелла. Этот метод позволяет ускорить работу сортировки по вставке, рассмотренной ранее. Поскольку сортировка вставкой удаляет одну инверсию за обмен, она не может работать быстрее, чем количество инверсий в данных, которое в худшем случае равно O(N2). Конечно, она также не может работать быстрее, чем N, потому что она должна просматривать каждый элемент, независимо от того, находится он вне позиции или нет. Мы ничего не можем сделать с нижней границей O(N), но мы можем что-то сделать с количеством шагов для удаления инверсий. Хитрость сортировки Шелла заключается в том, чтобы начать менять местами элементы, которые находятся дальше друг от друга. Хотя иногда это может удалить только одну инверсию, часто с помощью промежуточных элементов удаляется гораздо больше инверсий. Такой метод рассматривает под последовательности элементов, расположенных на расстоянии k элементов друг от друга. Существует k таких последовательностей, начинающихся с позиций от 0 до k-1 в массиве. В этих сортировках элементы, расположенные на расстоянии k позиций друг от друга, меняются местами, удаляя от 1 до 2(k-1)+1 инверсий. Как правило, поменять элементы местами недостаточно, поэтому при сортировке методом Шелла выполняется несколько проходов с уменьшающимися значениями k, заканчивающихся k=1. Следующие примеры экспериментируют с различными сериями значений k. PublicstaticvoidIntArrayShellSort(int[]data,int[]intervals) { inti,j,k,m; intN=data.Length; // The intervals for the shell sort must be sorted, ascending for(k=intervals.Length-1;k>=0;k--){ intinterval=intervals[k]; for(m=0;m for(j=m+interval;j for(i=j;i>=interval&&data[i] exchange(data,i,i-interval); } } } } } publicstaticvoidIntArrayShellSortNaive(int[]data) { int[]intervals={1,2,4,8}; IntArrayShellSort(data,intervals); } Схема алгоритма для сортировки методом Шелла представлена ниже  Схема 1 В целом, сортировка с последовательностью скачков, которые являются кратными друг другу, работает не так хорошо, как сортировка, в которой большинство скачков не являются кратными другим, что приводит к большему перемешиванию данных. Кроме того, количество интервалов должно увеличиваться по мере увеличения размера сортируемого массива, что объясняет, почему мы позволяем задавать произвольный массив интервалов. |