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

Сортировка перемешиванием, или Шейкерная сортировка, или двунаправленная (англ. 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("\nКоличество сравнений = {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("\n\n\n");
        }
    }
}

JavaScript

function shakerSort(array) {
    let left = 0; // начало массива
    let right = array.length - 1; // конец массива
    while (left < right) {
        for (let i = left; i < right; i++) {
            if (array[i] > array[i + 1]) {
                [array[i], array [i + 1]] = [array[i + 1], array [i]]
            }
        }
        right--;
        for (let i = right; left < i; i--) {
            if (array[i] < array[i - 1]) {
                [array[i], array [i - 1]] = [array[i - 1], array [i]]
            }
        }
        left++;
    }
    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)

T-SQL

create table #temp1
(
    id int primary key identity , -- ідентефикатор строки
    point int --значение
)

declare @left int = 0,
        @right int = (select count(*) from #temp1) - 1,
        @i int,
        @swap int

while @left <= @right
    begin
        set @i = @left
        while @i < @right + 1
            begin
                if (select point from #temp1 where id = @i) > (select point from #temp1 where id = @i + 1)
                    begin
                        set @swap = (select point from #temp1 where id = @i)

                        update #temp1
                        set point = (select point from #temp1 where id = @i + 1)
                        where id = @i

                        update #temp1
                        set point = @swap
                        where id = @i + 1
                    end
                set @i = @i + 1
            end

        set @right = @right - 1


        set @i = @right
        while @i > @left - 1
            begin
                if (select point from #temp1 where id = @i) < (select point from #temp1 where id = @i - 1)
                    begin
                        set @swap = (select point from #temp1 where id = @i)

                        update #temp1
                        set point = (select point from #temp1 where id = @i - 1)
                        where id = @i

                        update #temp1
                        set point = @swap
                        where id = @i - 1
                    end
                set @i = @i - 1
            end
        set @left = @left + 1


    end


select point
from #temp1

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

Ссылки

Динамическая визуализация 7 алгоритмов сортировки с открытым исходным кодом

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

Алгоритмы сортировки
Теория	Сложность О-нотация Отношение порядка Типы сортировки Устойчивая Внутренняя Внешняя
Обменные	Пузырьком Перемешиванием Гномья Быстрая Расчёской Сортировка чёт-нечет Поразрядная
Выбором	Выбором Пирамидальная Плавная
Вставками	Вставками Шелла Деревом
Слиянием	Слиянием
Без сравнений	Подсчётом Блочная
Гибридные	Introsort Timsort
Прочее	Топологическая Сети Битонная
Непрактичные	Bogosort Stooge sort Блинная Медленная