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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

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

С#[править | править код]

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) {
    // console.log('first array :', array);
    let left = 0; //начало массива
    let right = array.length - 1; //конец массива
    let temp; //буфер
    do {
        for (let i = left; i < right; i++) {
            if (array[i] > array[i + 1]) {
                temp = array[i];
                array[i] = array[i + 1];
                array[i + 1] = temp;
            }
        }
        // console.log('array :', array);
        right--;
        for (let i = right; left < i; i--) {
            if (array[i] < array[i - 1]) {
                temp = array[i];
                array[i] = array[i - 1];
                array[i - 1] = temp;
            }
        }
        // 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 -= 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[править | править код]

 1     public static void main(String[] args) {
 2         filling();
 3         shakerSort();
 4         System.out.println(Arrays.toString(arr));
 5        
 6     }
 7 
 8     private static void filling() {
 9         for (int i = 0; i < arr.length; i++) {
10             arr[i] = (int) (Math.random() * 10 + 1);
11         }
12         System.out.println(Arrays.toString(arr));
13     }
14 
15     public static void shakerSort(int arr[]) {
16         int buff;
17         int left = 0;
18         int right = arr.length-1;
19         do {
20             for (int i = left; i < right; i++) {
21                 if (arr[i] > arr[i+1]) {
22                     buff = arr[i];
23                     arr[i] = arr[i + 1];
24                     arr[i + 1] = buff;
25                 }
26             }
27             right--;
28             for (int i = right; i > left; i--) {
29                 if (arr[i] < arr[i-1]) {
30                     buff = arr[i];
31                     arr[i] = arr[i - 1];
32                     arr[i - 1] = buff;
33                 }
34             }
35             left++;
36         } while (left <right);
37     }

Python[править | править код]

 1 sample = [0, -1, 5, -2, 3]
 2 
 3 left = 0
 4 right = len(sample) - 1
 5 
 6 while left <= right:
 7     for i in range(left, right, +1):
 8         if sample[i] > sample[i + 1]:
 9             sample[i], sample[i + 1] = sample[i + 1], sample[i]
10     right -= 1
11 
12     for i in range(right, left, -1):
13         if sample[i - 1] > sample[i]:
14             sample[i], sample[i - 1] = sample[i - 1], sample[i]
15     left += 1
16 
17 print(sample)

Fortran[править | править код]

 1 subroutine sort_cocktail(array_size,array)
 2     integer i,j
 3     integer last_unsorted, firs_unsorted, exchange
 4     logical way
 5     integer,intent(in)      :: array_size
 6     integer,intent(inout)   :: array(array_size)
 7     last_unsorted = array_size
 8     firs_unsorted = 1
 9     way = .true.
10     do j=1,array_size
11         if (way) then
12             do i=firs_unsorted,last_unsorted-1
13                 if (array(i) .gt. array(i+1)) then
14                     exchange   = array(i)
15                     array(i)   = array(i+1)
16                     array(i+1) = exchange
17                 end if
18             end do
19             last_unsorted = last_unsorted -1
20         else
21             do i=last_unsorted-1,firs_unsorted,-1
22                 if (array(i) .gt. array(i+1)) then
23                     exchange   = array(i)
24                     array(i)   = array(i+1)
25                     array(i+1) = exchange
26                 end if
27             end do
28             firs_unsorted = firs_unsorted +1
29         end if
30         way = .not. way
31         if(firs_unsorted .ge. last_unsorted) exit
32     end do
33 end subroutine

Ссылки[править | править код]