Визуализация метода

Сортировка Шейкера

Теоретическая часть

Описание метода

Сортировка перемешиванием — разновидность пузырьковой сортировки. Уникальность метода заключается в следующих двух пунктах:

1) При движении по части массива перестановки не происходят, то эта часть массива уже отсортирована и, следовательно, ее можно исключить из рассмотрения.

2) При движении от конца массива к началу минимальный элемент “всплывает” на первую позицию, а максимальный элемент сдвигается только на одну позицию вправо.

Характеристики метода

Границы рабочей части массива (т.е. части массива, где происходит движение) устанавливаются в месте последнего обмена на каждой итерации. Массив просматривается поочередно справа налево и слева направо.

Асимптотическая сложность выполнения метода. Лучший случай - э т о отсортированный массив (О(n)). Худший - это отсортированный в обратном порядке (O(n²)). Наименьшее число сравнений в алгоритме Шейкер-сортировки C = N-1.

Визуализация метода

Заключение

Шейкерная сортировка позволяет сократить число сравнений, хотя порядком оценки по-прежнему остается n². Число же пересылок, вообще говоря, не меняется. Шейкерную сортировку рекомендуется использовать в тех случаях, когда известно, что массив "почти упорядочен".

Реализация метода на C#

using System;using System.Collections.Generic;using System.Linq;using System.Text;using System.Threading.Tasks; namespace SortLab{ class Program { /*Вызов метода сортировки*/ static void Main() { Sort(); } /*Основная программа*/ static void Sort() { int[] myint = { 99,88,77,66,55,44,33,22,11,8,5,3,1}; // Задаём массив данных WriteArray(myint); // Выводим массив до сортировки ShakerSort(myint); WriteArray(myint); // Выводим массив после сортировки Console.ReadLine(); } /* Шейкер-сортировка */ static void ShakerSort(int[] myint) { int beg, end; int count = 0; /* можно перебирать за кол-во итераций, в 2 раза меньше, при этом целочисленное деление округляет в меньшую сторону / for (int i = 0; i < myint.Length/2; i++) { beg = 0; end = myint.Length - 1; do { count += 2; /* идем спереди */ if (myint[beg] > myint[beg + 1]) Swap(myint,beg,beg+1); beg++; //сдвигаем позицию вперед /* идем сзади */ if (myint[end-1] > myint[end]) Swap(myint, end - 1, end); end--; //сдвигаем позицию назад } while (beg <= end);// условия усреднения } Console.Write(" \n Количество сравнений = {0} \n ",count); } /* Вспомогательная функция, которая позволяет поменять элементы местами */ static void Swap(int[] myint, int i, int j) { int glass; glass = myint[i]; myint[i] = myint[j]; myint[j] = glass; } /*Вывод массива*/ static void WriteArray(int[] a) { foreach (int i in a) Console.Write("{0}|", i); Console.WriteLine(" \n\n\n "); } }}

Дата добавления: 2015-08-17