Сортировка перемешиванием
Сортировка перемешиванием, или Шейкерная сортировка, или двунаправленная (англ. Cocktail sort) — разновидность пузырьковой сортировки. Анализируя метод пузырьковой сортировки, можно отметить два обстоятельства.
Во-первых, если при движении по части массива перестановки не происходят, то эта часть массива уже отсортирована и, следовательно, её можно исключить из рассмотрения.
Во-вторых, при движении от конца массива к началу минимальный элемент «всплывает» на первую позицию, а максимальный элемент сдвигается только на одну позицию вправо.
Эти две идеи приводят к следующим модификациям в методе пузырьковой сортировки. Границы рабочей части массива (то есть части массива, где происходит движение) устанавливаются в месте последнего обмена на каждой итерации. Массив просматривается поочередно справа налево и слева направо.
C++
#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) {
fillArray(arr);
shakerSort(arr);
System.out.println(Arrays.toString(arr));
}
private static void fillArray(int arr[]) {
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
Ссылки
| Теория |
|
|---|---|
| Обменные | |
| Выбором | |
| Вставками | |
| Слиянием | |
| Без сравнений | |
| Гибридные | |
| Прочее | |
| Непрактичные | |
