Сортировка Шейкерная-Перемешиванием (Shaker,Cocktail sort)

Рейтинг:  0 / 5

Звезда не активнаЗвезда не активнаЗвезда не активнаЗвезда не активнаЗвезда не активна
 

Cортировка перемешиванием, двунаправленная пузырьковая сортировка, шейкерная сортировка, пульсирующая сортировка (ripple sort), трансфертная сортировка (shuttle sort), и даже сортировка «счастливый час» (happy hour sort). Второй вариант (двунаправленная пузырьковая сортировка) наиболее точно описывает процесс работы алгоритма. Здесь, в его название, довольно-таки удачно включен термин «пузырьковая». Это действительно альтернативная версия известного метода, модификации в котором заключаются, по большей части, в реализации, упомянутой в названии, двунаправленности: алгоритм перемещается, ни как в обменной (пузырьковой) сортировке – строго снизу вверх (слева направо), а сначала снизу вверх, потом сверху вниз.

Образно алгоритм можно описать так: на каждом шаге основного цикла рассматривается массив a[Left]?a[Right], после выполнения двух внутренних циклов минимальный и максимальный элемент в исходном массиве перетекают к краям, минимальный в — a[Left], максимальный — в a[Right]. Пусть максимальный элемент имеет индекс k, тогда массив можно изобразить так: a[Left],a[1],..,a[k-1],A[k],a[k+1],..,a[Right];После сравнения A[k] с a[k+1] значение A[k] перейдет в k+1-ую ячейку,после сравнения k+1-й c k+2-й – в k+2-eю,и так далее,пока он не сместится в крайне правое положение с индексом Right. Аналогично для минимального. После выполнения цикла по всем подмассивам он отсортируется.

 

 

Худшее время

О(n2) сравнений, обменов

Лучшее время

O(n) сравнений, O(1) обмен

Среднее время

О(n2) сравнений, обменов

Реализация алгоритма на различных языках программирования:

 

Pascal

 

k:= 25; {Индекс последнего изменения}
s:= 1; {Первый элемент массива}
e:= 25; {Последний элемент массива}
while e > s do
begin
   for i:= e downto s+1 do if Arr[i] < Arr[i-1] then
   begin
      tmp := Arr[i];
      Arr[i] := Arr[i-1];
      Arr[i-1] := tmp;
      k := i;
   end;
   s:=k;
   for i:= s to e-1 do if Arr[i]>Arr[i+1] then
   begin
      tmp := Arr[i];
      Arr[i] := Arr[i+1];
      Arr[i+1] := tmp;
      k := i;
   end;
   e:=k;
end;

 

 

 

 

C++

 

#include "stdafx.h"
#include <iostream>
using namespace std;
//функция обмена
void Swap(int *Mas, int i)
{
int temp;
temp=Mas[i];
Mas[i]=Mas[i-1];
Mas[i-1]=temp;
}
//функция шейкерной сортировки
void ShakerSort(int *Mas, int Start, int N)
{
int Left, Right, i;
Left=Start;
Right=N-1;
while (Left<=Right)
{
for (i=Right; i>=Left; i--)
if (Mas[i-1]>Mas[i]) Swap(Mas, i);
Left++;
for (i=Left; i<=Right; i++)
if (Mas[i-1]>Mas[i]) Swap(Mas, i);
Right--;
}
}
//главная функция
void main()
{
setlocale(LC_ALL,"Rus");
int n, k;
cout<<"Размер массива > "; cin>>n;
int *A=new int[n];
for (k=0; k<n; k++)
{ cout<<k+1<<" элемент > "; cin>>A[k]; }
ShakerSort(A, 1, n);
cout<<"Результирующий массив: ";
for (k=0; k<n; k++)cout<<" "<<A[k];
system("pause>>void");
}

 

 

C#

 

#include "stdafx.h"
#include <iostream>
using namespace std;
//функция обмена
void Swap(int *Mas, int i)
{
int temp;
temp=Mas[i];
Mas[i]=Mas[i-1];
Mas[i-1]=temp;
}
//функция шейкерной сортировки
void ShakerSort(int *Mas, int Start, int N)
{
int Left, Right, i;
Left=Start;
Right=N-1;
while (Left<=Right)
{
for (i=Right; i>=Left; i--)
if (Mas[i-1]>Mas[i]) Swap(Mas, i);
Left++;
for (i=Left; i<=Right; i++)
if (Mas[i-1]>Mas[i]) Swap(Mas, i);
Right--;
}
}
//главная функция
void main()
{
setlocale(LC_ALL,"Rus");
int n, k;
cout<<"Размер массива > "; cin>>n;
int *A=new int[n];
for (k=0; k<n; k++)
{ cout<<k+1<<" элемент > "; cin>>A[k]; }
ShakerSort(A, 1, n);
cout<<"Результирующий массив: ";
for (k=0; k<n; k++)cout<<" "<<A[k];
system("pause>>void");
}

 

 

Fortran

 

program cocktailsort
 
integer A(17)
integer i,t
logical::sort=.true.
open(1,file='massiv.txt',status='old')
	read(1,*) A
		do i=1,17
			write(*,*) A(i)
		enddo
do while(sort)
sort=.false.
	do i=1, 16
		if(A(i)>A(i+1)) then
			t=A(i)
			A(i)=A(i+1)
			A(i+1)=t
			sort=.true.
		endif
	enddo
sort=.false.
 
	do i=16, 1, -1
		if(A(i)>A(i+1)) then
			t=A(i)
			A(i)=A(i+1)
			A(i+1)=t
			sort=.true.
		endif
	enddo
enddo
write(*,*) '---'
do i=1,17
	write(*,*) A(i)
enddo
pause
end

 

 

PHP

 

<?php
function swap(&$a, &$b) {
    $a = $a ^ $b;
    $b = $a ^ $b;
    $a = $a ^ $b;
}
 
 
 
function sheker($mas, $n)
{
        $last = $n-1; $left = 1; $right = $n-1;
 
        do
        {
                for($j = $right; $j >= $left; $j--)
                {
                        if($mas[$j-1] > $mas[$j])
                        {
                                swap($mas[$j-1], $mas[$j]);
                                $last = $j;
                        }
                }
 
                $left = $last + 1;
 
                for($j = $left; $j <= $right; $j++)
                {
                        if($mas[$j-1] > $mas[$j])
                        {
                                swap($mas[$j-1], $mas[$j]);
                                $last = $j;
                        }
                }
 
                $right = $last-1;
 
        } while($left < $right);
}
//(sheker($array,count($array)));
?>

 

 

Perl

 

while ( $left < $right ) {
	for ( my $j = $right; $j >= $left; $j-- ) {
		if ( $array_for_sort[$j-1] > $array_for_sort[$j] ) {
			( $array_for_sort[$j-1],$array_for_sort[$j]) = ( $array_for_sort[$j],$array_for_sort[$j-1] );
			$last = $j;
		}
	}
	$left = $last + 1;
	for( my $j = $left; $j <= $right; $j++ ) {
		if ( $array_for_sort[$j-1] > $array_for_sort[$j] ) {
			( $array_for_sort[$j-1],$array_for_sort[$j] ) = ( $array_for_sort[$j],$array_for_sort[$j-1] );
			$last = $j;
		}
	}
	$right = $last - 1;
}

 

 

С++

#include <vcl.h>
#include <conio.h>
#include <iostream.h>
#pragma hdrstop
#pragma argsused
 
// Шейкер-сортировка
 
int main(int argc, TCHAR* argv[])
{
    const int Count = 10;
    int TestArr[Count] = {3, 1, 5, 8, 1, 0, 6, 4, 6, 7};
 
    ShakerSort(TestArr,0,Count);
    ArrayOutput(TestArr,0,Count);
 
    return 0;
}
 
//Поменять местами 2 элемента
void Swap(int* e1, int* e2)
{
    *e1 ^= *e2;
    *e2 ^= *e1;
    *e1 ^= *e2;
}
 
void ShakerSort(int Arr[], int Start, int N)
{
    int Left, Right; //границы сортировки
 
    Left = Start;
    Right = N - 1;
 
 
    do
    {
        //Сдвигаем к началу массива "легкие элементы"
        for (int i = Right; i > Left; i--)
        {
            if (Arr[i] < Arr[i - 1])
            {
                Swap(&Arr[i], &Arr[i-1]);
            }
        }
 
        Left = Left + 1;
 
        //Сдвигаем к концу массива "тяжелые элементы"
        for (int i = Left; i < Right; i++)
        {
            if (Arr[i] > Arr[i + 1])
            {
                Swap(&Arr[i], &Arr[i + 1]);
            }
        }
 
        Right = Right - 1;
    }
    while (Left <= Right);
}
 
//Вывод элементов массива на консоль
void ArrayOutput(int* Arr, int Start, int N)
{
    for (int i = Start; i < N; i++)
    {
        cout << Arr[i] << '\n';
    }
    getch();
}

 

 С#

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;
 
            for (int i = 0; i < myint.Length/2; i++) //можно переберать за кол-во итераций, в 2 раза меньше
            {                                        //целочисленное деление округляет в меньшую сторону
                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");
        }
    }
}

 

 

 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 -= 1;
		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 += 1;
	} while ($left <= $right);
}

 

 Java

public class CocktailSort
{
 
    public static void main(String[] args)
    {
        int[] array = {3, 1, 5, 8, 1, 0, 6, 4, 6, 7};
        int left = 0; // левая граница
        int right = array.length - 1; // правая граница
 
        do
        {
            //Сдвигаем к концу массива "тяжелые элементы"
            for (int i = left; i < right; i++)
            {
                if(array[i] > array[i+1])
                {
                    array[i] ^= array[i+1];
                    array[i+1] ^= array[i];
                    array[i] ^= array[i+1];
                }
            }
            right--; // уменьшаем правую границу
            //Сдвигаем к началу массива "легкие элементы"
            for (int i = right; i > left ; i--)
            {
                if(array[i] < array[i-1])
                {
                    array[i] ^= array[i-1];
                    array[i-1] ^= array[i];
                    array[i] ^= array[i-1];
                }
            }
            left++; // увеличиваем левую границу
        } while (left <= right);
 
        for (int i : array) System.out.print(i + " "); // вывод массива на экран
    }
}

 

При написании статьи были использованы открытые источники сети интернет :

Wikipedia

Kvodo

Youtube

 

 




Реклама



Ваше мнение

Видиотека

Рейтинг@Mail.ru

Яндекс.Метрика