Сортировка обменом си шарп

Сортировка массива C#. Алгоритм «Сортировка перемешиванием»

уважаемые посетители блога, если Вам понравилась, то, пожалуйста, помогите автору с лечением. Подробности тут.

В литературе можно также встретить такие названия сортировки перемешиванием — шейкерная сортировка и двунаправленная пузырьковая сортировка. Алгоритм представляет собой одну из разновидностей «сортировки пузырьком«. Основное отличие заключается в том, что в классической сортировке пузырьком происходит однонаправленное движение элементов (снизу — вверх), в то время, как сортировке перемешиванием мы сначала проходим снизу-вверху, а затем сверху-вниз.

Алгоритм

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

Реализация алгоритма сортировки перемешиванием в C#

Для реализации алгоритма написано два метода: Swap() — меняет местами два элемента массива, CocktailSort() проводит шейкерную сортировку массива целых чисел.

static void Swap(int[] array, int i, int j) < int temp = array[i]; array[i] = array[j]; array[j] = temp; >static void CocktailSort(int[] inArray) < int left = 0, right = inArray.Length - 1; while (left < right) < for (int i = left; i < right; i++) < if (inArray[i] >inArray[i + 1]) Swap(inArray, i, i + 1); > right--; for (int i = right; i > left; i--) < if (inArray[i - 1] >inArray[i]) Swap(inArray, i - 1, i); > left++; > >

Пример сортировки массива

Console.WriteLine("Введите через запятую целые числа и нажмите Enter"); string[] nums = Console.ReadLine().Split(new char[] < ',' >); int[] intArray = new int[nums.Length]; for (int i = 0; i < nums.Length; i++) < intArray[i] = int.Parse(nums[i]); >CocktailSort(intArray); Console.WriteLine("\r\nОтсортированный массив:"); foreach (int value in intArray) < Console.Write($""); >

-10 0 1 1 2 2 3 3 4 5 6 7 8 9 100 101

уважаемые посетители блога, если Вам понравилась, то, пожалуйста, помогите автору с лечением. Подробности тут.

Источник

Шейкерная сортировка

Сортировка перемешиванием (cocktail sort, shaker sort), или шейкерная сортировка – это усовершенствованная разновидность сортировки пузырьком, при которой сортировка производиться в двух направлениях, меняя направление при каждом проходе.

Описание алгоритма шейкерной сортировки

Проанализировав алгоритм пузырьковой сортировки, можно заметить:

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

Исходя из приведенных идей, модифицируем сортировку пузырьком следующим образом:

• на каждой итерации, фиксируем границы части массива в которой происходит обмен;
• массив обходиться поочередно от начала массива к концу и от конца к началу;

При этом минимальный элемент перемещается в начало массива, а максимальный — в конец, после этого уменьшается рабочая область массива.

Реализация шейкерной сортировки

using System; class Program < //метод обмена элементов static void Swap(ref int e1, ref int e2) < var temp = e1; e1 = e2; e2 = temp; > //сортировка перемешиванием static int[] ShakerSort(int[] array) < for (var i = 0; i < array.Length / 2; i++) < var swapFlag = false; //проход слева направо for (var j = i; j < array.Length - i - 1; j++) < if (array[j] > array[j + 1]) < Swap(ref array[j], ref array[j + 1]); swapFlag = true; > > //проход справа налево for (var j = array.Length - 2 - i; j > i; j--) < if (array[j - 1] > array[j]) < Swap(ref array[j - 1], ref array[j]); swapFlag = true; > > //если обменов не было выходим if (!swapFlag) < break; > > return array; > static void Main(string[] args) < Console.WriteLine("Шейкерная сортировка"); Console.Write("Введите элементы массива: "); var parts = Console.ReadLine().Split(new[] < " ", ",", ";" >, StringSplitOptions.RemoveEmptyEntries); var array = new int[parts.Length]; for (int i = 0; i < parts.Length; i++) < array[i] = Convert.ToInt32(parts[i]); >Console.WriteLine("Отсортированный массив: ", string.Join(", ", ShakerSort(array))); Console.ReadLine(); > > 

Результат работы программы:

Источник

Сортировка обменами

Сортировка обменами. 1)Дана последовательность чисел a1, a2 , . an. Требуется представить числа в порядке возрастания. Для этого сравниваются два соседних числа ai и ai +1. Если ai > ai +1, то делается перестановка. Так продолжается до тех пор, пока все элементы не будут расположены в порядке возрастания. Составить алгоритм сортировки, подсчитывая при этом количество перестановок.
2)Даны два массива. Массив А состоит из N элементов и отсортирован по возрастанию. Массив В состоит из М элементов и отсортирован по убыванию. Разработать программу для слияния этих массивов в отсортированный по убыванию массив С, не содержащий одинаковых элементов.

Сортировка выбором, сортировка вставкой, сортировка заменой, сортировка обменом («пузырьковая» сортировка)
Создать класс, содержащий массив и реализующий алгоритмы сортировки и бинарного поиска в этом.

Сортировка обменами
Дана последовательность чисел a1, a2. an. Требуется переставить числа в порядке возрастания. Для.

Сортировка обменами
Сортировка обменами. Дана последовательность чисел a1, a2, …, an Требуется представить числа.

Сортировка обменами
Доброго времени суток. У меня есть часть кода программы, которую я хочу реализовать: #include.

int[] A = { 1, 2, 3, 4 }; int[] B = { 8, 7, 6, 5 }; Array.Reverse(A); int[] C = B.Concat(A).ToArray();

int[] A = { 1, 2, 3, 4 }; int[] B = { 8, 7, 6, 5 }; int[] C = A.Concat(B).Distinct().OrderByDescending(i => i).ToArray();

А вообще, в #2 дана часть ответа на 2), так же можно погуглить, как объединить два массива и как удалить повторяющиеся элементы в массиве.

EveKS, можно сделать чтобы нужно было после ввода массивов в консоли нужно отсортировать их, и после этого выполнить слияние не содержащее одинаковых элементов?

Сообщение было отмечено Программер010 как решение

Решение

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

Random random = new Random(); int[] a = new int[10]; for (int i = 0; i  a.Length; i++) { a[i] = random.Next(0, 100); Console.Write(a[i] + " "); } bool flag = true; Console.WriteLine(); int numshuffle = 0; while (flag) { flag = false; for (int i = 0; i  a.Length - 1; i++) if (a[i] > a[i + 1]) { int b = a[i]; a[i] = a[i + 1]; a[i + 1] = b; flag = true; numshuffle++; } } Console.Write(numshuffle+"\n"); for (int i = 0; i  a.Length; i++) Console.Write(a[i] + " "); Console.ReadKey(true);

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

static void Print(int [] array) { for (int i = 0; i  array.Length; i++) Console.Write(array[i] + " "); } static void Main(string[] args) { Console.WriteLine("Введите 1-й массив через пробел:"); int[] Array1 = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse); Console.WriteLine("Введите 2-й массив через пробел:"); int[] Array2 = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse); Array.Sort(Array1); Array.Sort(Array2); Array.Reverse(Array1); Console.WriteLine("1-й массив:"); Print(Array1); Console.WriteLine("\n2-й массив:"); Print(Array2); int[] result = Array1.Concat(Array2).Distinct().OrderByDescending(x => x).ToArray(); Console.WriteLine("\nРезультат"); Print(result); Console.ReadKey(true); }

Источник

Сортировка обменом си шарп

Шейкерная (коктейльная) сортировка (Cocktail Sort)

Модифицированный и немного улучшенный алгоритм пузырьковой сортировки, при котором обмен выполняется в двух направлениях – наибольшие элементы перемещаются в правую сторону, а во время обратного движения наименьшие движутся в левую сторону. Выполняется также за квадратичное время O(n*n) .

Сортировка вставками (Insertion Sort)

Сортировка вставками – достаточно простой в реализации и понятный для понимания алгоритм, который прекрасно работает на частично упорядоченных последовательностях и когда сортируемая коллекция последовательно заполняется элементами. Работает, как и рассмотренные ранее алгоритмы, за квадратичное время O(n*n) . Элементы последовательно добавляются в отсортированную позицию в нужное место, пока вся коллекция не будет отсортирована.

Сортировка Шелла (Shell Sort)

Данный алгоритм является усовершенствованной реализацией предыдущей сортировки вставками. Идея состоит в том, чтобы сортировать элементы, стоящие на некотором расстоянии друг от друга, что в результате даст частично отсортированную последовательность, которую можно будет легко и быстро отсортировать сортировкой вставками. Несмотря на то, что в худшем случае сортировка также отрабатывает за квадратичное время O(n*n) , этот алгоритм обычно показывает значительно лучший линейно-логарифмический результат O(n*log n) .

Сортировка выбором (Selection Sort)

Наверное, самый простой с точки зрения понимания алгоритм сортировки – просто последовательно выбирай самый большой элемент из всей сортируемой последовательности. Но, как это часто бывает, чем проще идея и реализация, тем хуже работает. Данный алгоритм работает строго за квадратичное время O(n*n), что, естественно, не очень хорошо.

Сортировка деревом (Tree Sort)

Данный алгоритм основан на структуре данных двоичное дерево поиска (BST), за что и получил свое имя. Принцип достаточно простой – построить дерево и выполнить его инфиксный обход. Если еще не знакомы с двоичным деревом, то можно посмотреть здесь .

Несмотря на то, что в худшем случае, когда дерева вырождается в связный список, время падает до квадратичного O(n*n) , при нормальной балансировке алгоритм работает за линейно-логарифмическое время O(n*log n) .

Пирамидальная сортировка (Heapsort)

Сортировка кучей является одним из оптимальных и часто используемых на практике алгоритмов сортировки. Выполняется он за линейно-квадратическое время O(n*log n) и при этом является достаточно устойчивым. Принцип его работы, так же как и у предыдущего алгоритма, связан со структурой данных – Двоичная куча (heap). Посмотреть про этот структуру можно в моем видео .

Реализация сортировки достаточно простая – нужно просто построить двоичную кучу с минимальным/максимальным элементом в корне и извлекать из неё корневой элемент до тех пор, пока в ней будут элементы. За счёт балансировки кучи в корне всегда будет следующий по очереди элемент.

Сортировка слиянием (merge sort)

Сортировка слиянием постоянно борется за пальму первенства по скорости со следующим алгоритмом и зачастую даже выигрывает за счёт большей устойчивости. Работает ожидаемо за линейно-логарифмическое O(n*log n) время и применяет принцип «разделяй и властвуй». Вся сортируемая последовательность разбивается пополам на группы до тех пор, пока в каждой из них не будет по два элемента. Затем эта маленькая группа упорядочивается и сливается с другой такой же группой. При слиянии в результирующую коллекцию помещаются по порядку элементы из двух исходных групп. И так до тех пор, пока не останется одна отсортированная последовательность.

Быстрая сортировка (quicksort)

Данная сортировка не зря получила свое имя – зачастую она позволяет выполнить сортировку быстрее любого другого алгоритма. Именно быстрая сортировка чаще всего применяется на практике. Работает за линейно-логарифмическое время O(n*log n) . И это был бы идеальный алгоритм, если бы не одно «но»: в редких случаях он может деградировать до сортировки пузырьком с квадратичным временем O(n*n) . Принцип работы алгоритма связан с выбором опорного элемента, относительно которого выполняется сортировка. Условно коллекция делится пополам относительно его, и все, что меньше опорного элемента, перемещается влево от него, все, что больше – вправо. Все работает прекрасно, когда значение опорного элемента близко к середине, но если он постоянно оказывается максимальным или минимальным, то результаты оказываются плачевными.

Источник