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

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

Сортировка перемешиванием (англ. Cocktail sort) — разновидность пузырьковой сортировки. Анализируя метод пузырьковой сортировки, можно отметить два обстоятельства.
Во-первых, если при движении по части массива перестановки не происходят, то эта часть массива уже отсортирована и, следовательно, ее можно исключить из рассмотрения.
Во-вторых, при движении от конца массива к началу минимальный элемент “всплывает” на первую позицию, а максимальный элемент сдвигается только на одну позицию вправо.

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

Лучший случай для этой сортировки — отсортированный массив (О(n)), худший — отсортированный в обратном порядке (O(n²)).

Наименьшее число сравнений в алгоритме Шейкер-сортировки C=N-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");
        }
    }
}

Образно алгоритм можно описать так: на каждом шаге основного цикла рассматривается массив 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. Аналогично для минимального. После выполнения цикла по всем подмассивам он отсортируется. Трассировка программы:

3 1 5 8 1 0 4 6 6 7
3 1 5 8 0 1 4 6 6 7
3 1 5 0 8 1 4 6 6 7
3 1 0 5 8 1 4 6 6 7
3 0 1 5 8 1 4 6 6 7
0 3 1 5 8 1 4 6 6 7 Left=1
0 1 3 5 8 1 4 6 6 7
0 1 3 5 1 8 4 6 6 7
0 1 3 5 1 4 8 6 6 7
0 1 3 5 1 4 6 8 6 7
0 1 3 5 1 4 6 6 8 7
0 1 3 5 1 4 6 6 7 8 Right=8
0 1 3 1 5 4 6 6 7 8
0 1 1 3 5 4 6 6 7 8 Left=3
0 1 1 3 4 5 6 6 7 8

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