20.07.2021

Сортировка перемешиванием, или Шейкерная сортировка, или двунаправленная (англ. Cocktail sort) — разновидность пузырьковой сортировки. Анализируя метод пузырьковой сортировки, можно отметить два обстоятельства.

Во-первых, если при движении по части массива перестановки не происходят, то эта часть массива уже отсортирована и, следовательно, её можно исключить из рассмотрения.

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

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

С++

#include <iostream> #include <vector> #include <ctime> void filling(std::vector<int>& arr) { for (size_t i = 0; i < arr.size(); ++i) { arr[i] = static_cast<int>(rand() % 100); std::cout<< arr[i] << " "; } std::cout << std::endl; } void shakerSort(std::vector<int>& arr) { int control = arr.size() - 1; int left = 0; int right = arr.size() - 1; do { for (int i = left; i < right; i++) { if (arr[i] > arr[i + 1]) { std::swap(arr[i], arr[i + 1]); control = i; } } right = control; for (int i = right; i > left; i--) { if (arr[i] < arr[i - 1]) { std::swap(arr[i], arr[i - 1]); control = i; } } left = control; } while (left < right); } int main() { const int N = 20; std::vector<int> arr; arr.reserve(N); for (int i = 0; i < N; i++) arr.push_back(0); srand(time(0)); filling(arr); shakerSort(arr); for (int i = 0; i < arr.size(); i++) { std::cout << arr[i] << " "; } arr.clear(); std::cin.ignore(); }

С#

using System; 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 left = 0, right = myint.Length - 1, count = 0; while (left < right) { for (int i = left; i < right; i++) { count++; if (myint[i] > myint[i + 1]) Swap(myint, i, i + 1); } right--; for (int i = right; i > left; i--) { count++; if (myint[i - 1] > myint[i]) Swap(myint, i - 1, i); } left++; } Console.WriteLine(" Количество сравнений = {0}", count.ToString()); } /* Поменять элементы местами */ static void Swap(int[] myint, int i, int j) { int glass = myint[i]; myint[i] = myint[j]; myint[j] = glass; } /*Вывести массив*/ static void WriteArray(int[] a) { foreach (int i in a) Console.Write("{0}|", i.ToString()); Console.WriteLine(" "); } } }

JavaScript

function shakerSort(array) { // console.log('first array :', array); let left = 0; //начало массива let right = array.length - 1; //конец массива do { for (let i = left; i < right; i++) { if (array[i] > array[i + 1]) { [array[i], array [i + 1]] = [array[i + 1], array [i]] } } // console.log('array :', array); right--; for (let i = right; left < i; i--) { if (array[i] < array[i - 1]) { [array[i], array [i - 1]] = [array[i - 1], array [i]] } } // console.log('array :', array); left++; } while (left < right); // console.log('array :', array); return array; }

PHP

function cocktailSorting(&$a) { $n = count($a); $left = 0; $right = $n - 1; do { for ($i = $left; $i < $right; $i++) { if ($a[$i] > $a[$i + 1]) { list($a[$i], $a[$i + 1]) = array($a[$i + 1], $a[$i]); } } $right--; for ($i = $right; $i > $left; $i--) { if ($a[$i] < $a[$i - 1]) { list($a[$i], $a[$i - 1]) = array($a[$i - 1], $a[$i]); } } $left++; } while ($left <= $right); }

ИЛИ

function FunctionCoocktailSort(&$array) { $leftItem = 0; $rightItem = count($array) - 1; for ($i = $leftItem; $i < $rightItem; $i++) { for ($j = $leftItem; $j < $rightItem; $j++) { if ($array[$j] > $array[$j + 1]) { FunctionSwapVariables($array[$j], $array[$j + 1]); } } $rightItem--; for ($j = $rightItem; $j > $leftItem; $j--) { if ($array[$j] < $array[$j - 1]) { FunctionSwapVariables($array[$j], $array[$j - 1]); } } } }

Java

public static void main(String[] args) { filling(); shakerSort(); System.out.println(Arrays.toString(arr)); } private static void filling() { for (int i = 0; i < arr.length; i++) { arr[i] = (int) (Math.random() * 10 + 1); } System.out.println(Arrays.toString(arr)); } public static void shakerSort(int arr[]) { int buff; int left = 0; int right = arr.length - 1; do { for (int i = left; i < right; i++) { if (arr[i] > arr[i + 1]) { buff = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = buff; } } right--; for (int i = right; i > left; i--) { if (arr[i] < arr[i - 1]) { buff = arr[i]; arr[i] = arr[i - 1]; arr[i - 1] = buff; } } left++; } while (left < right); }

Python

sample = [0, -1, 5, -2, 3] left = 0 right = len(sample) - 1 while left <= right: for i in range(left, right, +1): if sample[i] > sample[i + 1]: sample[i], sample[i + 1] = sample[i + 1], sample[i] right -= 1 for i in range(right, left, -1): if sample[i - 1] > sample[i]: sample[i], sample[i - 1] = sample[i - 1], sample[i] left += 1 print(sample)

Fortran

subroutine sort_cocktail(array_size,array) integer i,j integer last_unsorted, firs_unsorted, exchange logical way integer,intent(in) :: array_size integer,intent(inout) :: array(array_size) last_unsorted = array_size firs_unsorted = 1 way = .true. do j=1,array_size if (way) then do i=firs_unsorted,last_unsorted-1 if (array(i) .gt. array(i+1)) then exchange = array(i) array(i) = array(i+1) array(i+1) = exchange end if end do last_unsorted = last_unsorted -1 else do i=last_unsorted-1,firs_unsorted,-1 if (array(i) .gt. array(i+1)) then exchange = array(i) array(i) = array(i+1) array(i+1) = exchange end if end do firs_unsorted = firs_unsorted +1 end if way = .not. way if(firs_unsorted .ge. last_unsorted) exit end do end subroutine

Имя:*
E-Mail:
Комментарий: