Алгоритмы сортировки и их производительность23.09.2022 02:47

Вступление

Здравствуйте, давно читаю Хабр и все хотел написать кому-нибудь статью, но не знал с чего начать и о чем писать. Но решил что тянуть кота за причинное место. Надо просто взять и написать обзор о чем то что я знаю и что будет просто для начало. Поэтому решил описать алгоритмы сортировки в размере 37 штук. Я понимаю, что на Хабре есть подобные статьи, одна постараюсь их добавить количеством алгоритмов и приведением небольшого числа графиков.

Список алгоритмов

Bubble
Shaker
Insertion
Stooge
Pancake
Shell
Merge
Selection
Quick
Gnome
Tree
Comb
BasicCounting
CombinedBubble
Heapify
Cocktail
OddEven
Tim
Counting
Radix
Bucket
BinaryInsertion
Bogo
Cycle
Exchange
Heap
MSDRadix

Ниже представлена таблица с основными характеристиками алгоритмов сортировок.

Название	Время	Память
Лучшее	Среднее	Худшее
Bubble		$O(n^{2})$	$O(n^{2})$
Shaker		$O(n^{2})$	$O(n^{2})$
Insertion		$O(n^{2})$	$O(n^{2})$
Stooge	$O(\frac{a^{log 3}}{log 1.5})$	$O(\frac{a^{log 3}}{log 1.5})$	$O(\frac{a^{log 3}}{log 1.5})$
Pancake		$O(n^{2})$	$O(n^{2})$
Shell	$O(n\times log^{2}n)$	Зависит от выбора шага	$O(n^{2})$
Merge	$O(n\times logn)$	$O(n\times logn)$	$O(n\times logn)$
Selection	$O(n^{2})$	$O(n^{2})$	$O(n^{2})$
Quick	$O(n\times logn)$	$O(n\times logn)$	$O(n^{2})$
Gnome		$O(n^{2})$	$O(n^{2})$
Tree		$O(n\times logn)$	$O(n\times logn)$
Comb		$O(\frac{n^2}{2^p})$	$O(n^{2})$
BasicCounting
CombinedBubble		$O(n^{2})$	$O(n^{2})$
Heapify	$O(n\times logn)$	$O(n\times logn)$	$O(n\times logn)$
Cocktail		$O(n^{2})$	$O(n^{2})$
OddEven		$O(n^{2})$	$O(n^{2})$
Tim		$O(n\times logn)$	$O(n\times logn)$
Counting
Radix	$O(n\times k)$	$O(n\times k)$
Bucket	$O(n^{2})$	$O(n\times k)$
BinaryInsertion		$O(n\times logn)$	$O(n\times logn)$
Bogo		$O(n\times n!)$	$O(n\times n!)$
Cycle		$O(n^{2})$	$O(n^{2})$
Exchange	$O(n^{2})$	$O(n^{2})$	$O(n^{2})$
Heap	$O(n\times logn)$	$O(n\times logn)$	$O(n\times logn)$
MSDRadix	$O(n\times k)$	$O(n\times k)$	$O(n\times logn)$

Описание алгоритмов

Bubble

Алгоритм состоит в повторяющихся проходах по сортируемому массиву. На каждой итерации последовательно сравниваются соседние элементы, и, если порядок в паре неверный, то элементы меняют местами. За каждый проход по массиву как минимум один элемент встает на свое место, поэтому необходимо совершить не более n-1 проходов, где размер массива, чтобы отсортировать массив.

Ниже приведен псевдокод сортировки пузырьком, на вход которой подается массив a[0..n-1] .

        public static void Bubble(ref int[] array) //сортировка пузырьком
        {
            var len = array.Length;
            for (var i = 1; i < len; i++)
            {
                for (var j = 0; j < len - i; j++)
                {
                    if (array[j] > array[j + 1])
                    {
                        Swap(ref array[j], ref array[j + 1]);
                    }
                }
            }

        }

10 → 2000 Случайные числа

10 → 2000 Реальные

Shaker

Производится многократный прогон по массиву, соседние элементы сравниваются и, в случае необходимости, меняются местами. При достижении конца массива направление меняется на противоположное. Таким образом по очереди выталкиваются крупные и мелкие элементы массива в конец и начало структуры соответственно.

public static void Shaker(ref int[] array) //сортировка перемешиванием
        {
            for (var i = 0; i < array.Length / 2; i++)
            {
                var swapFlag = false;
                //проход слева направо
                for (var j = i; j < array.Length - i - 1; j++)
                {
                    if (array[j] > array[j + 1])
                    {
                        Swap(ref array[j], ref array[j + 1]);
                        swapFlag = true;
                    }
                }

                //проход справа налево
                for (var j = array.Length - 2 - i; j > i; j--)
                {
                    if (array[j - 1] > array[j])
                    {
                        Swap(ref array[j - 1], ref array[j]);
                        swapFlag = true;
                    }
                }

                //если обменов не было выходим
                if (!swapFlag)
                {
                    break;
                }
            }

        }

10 → 2000 Synthetic

10 → 10000 Real

Insertion

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

        public static void Insertion(ref int[] array) //сортировка вставками
        {
            int n = array.Length;
            for (int i = 1; i < n; ++i)
            {
                int key = array[i];
                int j = i - 1;

                // Move elements of arr[0..i-1],
                // that are greater than key,
                // to one position ahead of
                // their current position
                while (j >= 0 && array[j] > key)
                {
                    array[j + 1] = array[j];
                    j = j - 1;
                }
                array[j + 1] = key;
            }
        }

10 → 2000 Synthetic

10 → 10000 Real

Stooge

Рекурсивный алгоритм сортировки. Время работы алгоритма, таким образом, крайне большое по сравнению с эффективными алгоритмами сортировки

Aлгоритм сортировки списка элементов заключается в следующем:

Если значение элемента в конце списка меньше, чем значение элемента в начале, то поменять их местами.
Если есть 3 или более элементов в текущем подмножестве списка, то:
- Рекурсивно вызвать Stooge sort для первых 2/3 списка
- Рекурсивно вызвать Stooge sort для последних 2/3 списка
- Рекурсивно вызвать Stooge sort для первых 2/3 списка снова
Иначе: return

        public static void Stooge(ref int[] array, int startIndex, int endIndex) //сортировка по частям
        {
            if (array[startIndex] > array[endIndex])
            {
                Swap(ref array[startIndex], ref array[endIndex]);
            }

            if (endIndex - startIndex > 1)
            {
                var len = (endIndex - startIndex + 1) / 3;
                Stooge(ref array, startIndex, endIndex - len);
                Stooge(ref array, startIndex + len, endIndex);
                Stooge(ref array, startIndex, endIndex - len);
            }

        }
        public static void Stooge(ref int[] array) //сортировка по частям
        {
            Stooge(ref array, 0, array.Length - 1);
        }

10 → 1000 Synthetic

10 → 1000 Real

Pancake

Единственная операция, допустимая в алгоритме — переворот элементов последовательности до какого-либо индекса. В отличие от традиционных алгоритмов, в которых минимизируют количество сравнений, в блинной сортировке требуется сделать как можно меньше переворотов. Процесс можно визуально представить как стопку блинов, которую тасуют путём взятия нескольких блинов сверху и их переворачивания

        public static void Pancake(ref int[] array) //блинная сортировка
        {
            for (var subArrayLength = array.Length - 1; subArrayLength >= 0; subArrayLength--)
            {
                //получаем позицию максимального элемента подмассива
                var indexOfMax = IndexOfMax(array, subArrayLength);
                if (indexOfMax != subArrayLength)
                {
                    //переворот массива до индекса максимального элемента
                    //максимальный элемент подмассива расположится вначале
                    Flip(array, indexOfMax);
                    //переворот всего подмассива
                    Flip(array, subArrayLength);
                }
            }

        }

10 → 2000 Synthetic

10 → 2000 Real

Shell

Каждый проход в алгоритме характеризуется смещением $h_{i}$ , таким, что сортируются элементы отстающие друг от друга на $h_{i}$ позиций. Шелл предлагал использовать $h_{i}=N/2, h_{t-1}=h_{t}/2, …… , h_{0}=1$ Возможны и другие смещения, но $h_{i} =1$ всегда.

Начало.
Шаг 0. .
Шаг 1. Разобьем массив на списки элементов, отстающих друг от друга на $h_{i}$ Таких списков будет $h_{i}$
Шаг 2. Отсортируем элементы каждого списка сортировкой вставками.
Шаг 3. Объединим списки обратно в массив. Уменьшим . Если неотрицательно — вернемся к шагу 1
Конец.

        public static void Shell(ref int[] array) //сортировки Шелла
        {
            //расстояние между элементами, которые сравниваются
            var d = array.Length / 2;
            while (d >= 1)
            {
                for (var i = d; i < array.Length; i++)
                {
                    var j = i;
                    while ((j >= d) && (array[j - d] > array[j]))
                    {
                        Swap(ref array[j], ref array[j - d]);
                        j = j - d;
                    }
                }

                d = d / 2;
            }

        }

10 → 10000 Synthetic

10 → 10000 Real

Merge

Алгоритм использует принцип «разделяй и властвуй»: задача разбивается на подзадачи меньшего размера, которые решаются по отдельности, после чего их решения комбинируются для получения решения исходной задачи. Конкретно процедуру сортировки слиянием можно описать следующим образом:

Если в рассматриваемом массиве один элемент, то он уже отсортирован — алгоритм завершает работу.
Иначе массив разбивается на две части, которые сортируются рекурсивно.
После сортировки двух частей массива к ним применяется процедура слияния, которая по двум отсортированным частям получает исходный отсортированный массив.

        private static void merge(int[] arr, int l, int m, int r)
        {
            // original array is broken in two parts  
            // left and right array  
            int len1 = m - l + 1, len2 = r - m;
            int[] left = new int[len1];
            int[] right = new int[len2];

            for (int x = 0; x < len1; x++)
                left[x] = arr[l + x];

            for (int x = 0; x < len2; x++)
                right[x] = arr[m + 1 + x];

            int i = 0;
            int j = 0;
            int k = l;

            // after comparing, we merge those two array  
            // in larger sub array  
            while (i < len1 && j < len2)
            {
                if (left[i] <= right[j])
                {
                    arr[k] = left[i];
                    i++;
                }
                else
                {
                    arr[k] = right[j];
                    j++;
                }
                k++;
            }

            // copy remaining elements of left, if any  
            while (i < len1)
            {
                arr[k] = left[i];
                k++;
                i++;
            }

            // copy remaining element of right, if any  
            while (j < len2)
            {
                arr[k] = right[j];
                k++;
                j++;
            }
        }
        public static void Merge(ref int[] array) //сортировка слиянием
        {
            MergeSort(array, 0, array.Length - 1);
        }

10 → 10000 Synthetic

10 → 10000 Real

Selection

На каждом -ом шаге алгоритма находим -ый минимальный элемент и меняем его местами с -ым элементом в массиве. Таким образом будет получен массив, отсортированный по не убыванию.

        public static void Selection(ref int[] array, int currentIndex = 0) //сортировка выбором
        {
            if (currentIndex == array.Length)
                return;

            var index = IndexOfMin(array, currentIndex);
            if (index != currentIndex)
            {
                Swap(ref array[index], ref array[currentIndex]);
            }

             Selection(ref array, currentIndex + 1);
        }

10 → 2000 Synthetic

10 → 2000 Real

Quick

Быстрый метод сортировки функционирует по принципу «разделяй и властвуй».

        static int[] QuickSort(int[] array, int minIndex, int maxIndex) //быстрая сортировка
        {
            if (minIndex >= maxIndex)
            {
                return array;
            }

            var pivotIndex = Partition(array, minIndex, maxIndex);
            QuickSort(array, minIndex, pivotIndex - 1);
            QuickSort(array, pivotIndex + 1, maxIndex);

            return array;
        }
        public static void Quick(ref int[] array) //сортировка Хоара
        {
            QuickSort(array, 0, array.Length - 1);
        }

10 → 2000 Synthetic

10 → 10000 Real

Gnome

Гномья сортировка основана на технике, используемой обычным голландским садовым гномом. Это метод, которым садовый гном сортирует линию цветочных горшков. По существу он смотрит на следующий и предыдущий садовые горшки: если они в правильном порядке, он шагает на один горшок вперёд, иначе он меняет их местами и шагает на один горшок назад. Граничные условия: если нет предыдущего горшка, он шагает вперёд; если нет следующего горшка, он закончил.

        public static void Gnome(ref int[] unsortedArray) //Гномья сортировка
        {
            var index = 1;
            var nextIndex = index + 1;

            while (index < unsortedArray.Length)
            {
                if (unsortedArray[index - 1] < unsortedArray[index])
                {
                    index = nextIndex;
                    nextIndex++;
                }
                else
                {
                    Swap(ref unsortedArray[index - 1], ref unsortedArray[index]);
                    index--;
                    if (index == 0)
                    {
                        index = nextIndex;
                        nextIndex++;
                    }
                }
            }
        }

10 → 2000 Synthetic

10 → 10000 Real

Tree

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

Построение двоичного дерева.
Сборка результирующего массива путём обхода узлов в необходимом порядке следования ключей.

class TreeNode //простая реализация бинарного дерева
    {
        public TreeNode(int data)
        {
            Data = data;
        }
        public int Data { get; set; } //данные
        public TreeNode Left { get; set; } //левая ветка дерева
        public TreeNode Right { get; set; } //правая ветка дерева
        public void Insert(TreeNode node) //рекурсивное добавление узла в дерево
        {
            if (node.Data < Data)
            {
                if (Left == null)
                {
                    Left = node;
                }
                else
                {
                    Left.Insert(node);
                }
            }
            else
            {
                if (Right == null)
                {
                    Right = node;
                }
                else
                {
                    Right.Insert(node);
                }
            }
        }
        public int[] Transform(List elements = null) //преобразование дерева в отсортированный массив
        {
            if (elements == null)
            {
                elements = new List();
            }

            if (Left != null)
            {
                Left.Transform(elements);
            }

            elements.Add(Data);

            if (Right != null)
            {
                Right.Transform(elements);
            }

            return elements.ToArray();
        }
    }
        public static void Tree(ref int[] array) //метод для сортировки с помощью двоичного дерева
        {
            var treeNode = new TreeNode(array[0]);
            for (int i = 1; i < array.Length; i++)
            {
                treeNode.Insert(new TreeNode(array[i]));
            }

            array = treeNode.Transform();
        }

10 → 2000 Synthetic

10 → 2000 Real

Comb

Производятся неоднократные прогоны по массиву, при которых сравниваются пары элементов. Если они неотсортированно друг относительно друга — то производится обмен. В результате крупные элементы мигрируют в конец массива, а небольшие по значению — в начало.

public static void Comb(ref int[] array) //Сортировка расческой
        {
            var arrayLength = array.Length;
            var currentStep = arrayLength - 1;

            while (currentStep > 1)
            {
                for (int i = 0; i + currentStep < array.Length; i++)
                {
                    if (array[i] > array[i + currentStep])
                    {
                        Swap(ref array[i], ref array[i + currentStep]);
                    }
                }

                currentStep = GetNextStep(currentStep);
            }

            //сортировка пузырьком
            for (var i = 1; i < arrayLength; i++)
            {
                var swapFlag = false;
                for (var j = 0; j < arrayLength - i; j++)
                {
                    if (array[j] > array[j + 1])
                    {
                        Swap(ref array[j], ref array[j + 1]);
                        swapFlag = true;
                    }
                }

                if (!swapFlag)
                {
                    break;
                }
            }
        }

10 → 10000 Synthetic

10 → 10000 Real

BasicCounting

Алгоритм сортировки, в котором используется диапазон чисел сортируемого массива для подсчёта совпадающих элементов. Применение сортировки подсчётом целесообразно лишь тогда, когда сортируемые числа имеют (или их можно отобразить в) диапазон возможных значений, который достаточно мал по сравнению с сортируемым множеством, например, миллион натуральных чисел меньших 1000.

public static void BasicCounting(ref int[] array) //простой вариант сортировки подсчетом
        {
            int n = array.Length;
            int max = 0;
            for (int i = 0; i < n; i++)
            {
                if (max < array[i])
                {
                    max = array[i];
                }
            }

            int[] freq = new int[max + 1];
            for (int i = 0; i < max + 1; i++)
            {
                freq[i] = 0;
            }
            for (int i = 0; i < n; i++)
            {
                freq[array[i]]++;
            }

            for (int i = 0, j = 0; i <= max; i++)
            {
                while (freq[i] > 0)
                {
                    array[j] = i;
                    j++;
                    freq[i]--;
                }
            }
        }

10 → 100000 Synthetic

10 → 100000 Real

CombinedBubble

Алгоритм состоит из повторяющихся проходов по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется перестановка элементов. Проходы по массиву повторяются N-1 раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При каждом проходе алгоритма по внутреннему циклу очередной наибольший элемент массива ставится на своё место в конце массива рядом с предыдущим «наибольшим элементом», а наименьший элемент перемещается на одну позицию к началу массива («всплывает» до нужной позиции, как пузырёк в воде — отсюда и название алгоритма).

public static void CombinedBubble(ref int[] array)
        {
            int length = array.Length;

            int temp = array[0];

            for (int i = 0; i < length; i++)
            {
                for (int j = i + 1; j < length; j++)
                {
                    if (array[i] > array[j])
                    {
                        temp = array[i];

                        array[i] = array[j];

                        array[j] = temp;
                    }
                }
            }
        }

10 → 2000 Synthetic

10 → 2000 Real

Heapify

Необходимо отсортировать массив , размером . Построим на базе этого массива за O(n) кучу для максимума. Так как максимальный элемент находится в корне, то если поменять его местами с A[n−1] , он встанет на своё место. Далее вызовем процедуру siftDown(0) , предварительно уменьшив heapSize на 1. Она за O(logn) просеет A[0] на нужное место и сформирует новую кучу (так как мы уменьшили её размер, то куча располагается с A[0] по A[n−2] , а элемент A[n−1] находится на своём месте). Повторим эту процедуру для новой кучи, только корень будет менять местами не с , а . Делая аналогичные действия, пока heapSize не станет равен 1, мы будем ставить наибольшее из оставшихся чисел в конец не отсортированной части. Очевидно, что таким образом, мы получим отсортированный массив.

        public static void Heapify(ref int[] array) // Heapify
        {
            for (int i = array.Length / 2 - 1; i >= 0; i--)
                Heapify(array, array.Length, i);

            for (int i = array.Length - 1; i >= 0; i--)
            {
                int temp = array[0];
                array[0] = array[i];
                array[i] = temp;
                Heapify(array, i, 0);
            }
        }

10 → 10000 Synthetic

10 → 10000 Real

Cocktail

Производится многократный прогон по массиву, соседние элементы сравниваются и, в случае необходимости, меняются местами. При достижении конца массива направление меняется на противоположное. Таким образом по очереди выталкиваются крупные и мелкие элементы массива в конец и начало структуры соответственно. Коктейльная сортировка ещё называется двухсторонней сортировкой простыми обменами. Есть аналогичная модификация и для сортировки выбором.

public static void Cocktail(ref int[] array) // cocktail
        {
            int start = 0;
            int end = array.Length - 1;
            int temp;
            bool swapped = true;

            while (swapped)
            {
                swapped = false;

                for (int i = 0; i < end; i++)
                {
                    if (array[i] > array[i + 1])
                    {
                        temp = array[i];
                        array[i] = array[i + 1];
                        array[i + 1] = temp;
                        swapped = true;
                    }
                }

                if (!swapped)
                {
                    break;
                }

                swapped = false;
                end -= 1;

                for (int i = end; i >= start; i--)
                {
                    if (array[i] > array[i + 1])
                    {
                        temp = array[i];
                        array[i] = array[i + 1];
                        array[i + 1] = temp;
                        swapped = true;
                    }
                }

                start += 1;
            }
        }

10 → 2000 Synthetic

10 → 10000 Real

OddEven

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

public static void OddEven(ref int[] array)
        {
            //Initialization
            int Flag = 0;
            int temp = 0;

            //Initialize flag =0 or f!=1
            while (Flag == 0)
            {

                /*Initialize Flag is 1
                When both if condiotion is false so the flag remain 1 
                and the while loop is terminate*/

                Flag = 1;

                //use Even Loop for comparing even idexes of an array 

                for (int i = 0; i < array.Length - 1; i += 2)
                {
                    /* Use if conditon for comparing adjacents elements
                   
                     if they are in wrong order than swap*/

                    if (array[i] > array[i + 1])
                    {

                        temp = array[i];
                        array[i] = array[i + 1];
                        array[i + 1] = temp;
                        //This Flag variable is always remain 0 when if condition is true
                        Flag = 0;
                    }
                }


                //use Odd Loop for comparing odd idexes of an array 
                for (int i = 1; i < array.Length - 1; i += 2)
                {

                    /* Use if conditon for comparing adjacents elements
                        if they are in wrong order than swap*/
                    if (array[i] > array[i + 1])
                    {
                        //This Flag variable is always remain 0 when if condition is true
                        temp = array[i];
                        array[i] = array[i + 1];
                        array[i + 1] = temp;
                        Flag = 0;
                    }
                }

            }
            //return sorted array

        } // OddEven

10 → 2000 Synthetic

10 → 2000 Real

Tim

гибридный алгоритм сортировки, сочетающий различные подходы.

Данный алгоритм является относительно новым и был придуман Тимом Петерсом. На массивах данных, которые содержат упорядоченные под массивы, алгоритм Тима Петерса показывает себя намного лучше других сортировок. В настоящее время Timsort является стандартной сортировкой в Python и GNU Octave, реализован в OpenJDK 7 и Android JDK 1.5.

Алгоритм Timsort состоит из нескольких частей:

Начало.
Шаг 1. Входной массив разделяется на подмассивы фиксированной длины, вычисляемой определённым образом.
Шаг 2. Каждый под массив сортируется сортировкой вставками, сортировкой пузырьком или любой другой устойчивой сортировкой.
Шаг 3. Отсортированные под массивы объединяются в один массив с помощью модифицированной сортировки слиянием.
Конец.

        public static void Tim(ref int[] array)
        {
            int RUN = 32;

            for (int i = 0; i < array.Length; i += RUN)
                insertionSort(array, i, Math.Min((i + 31), (array.Length - 1)));

            for (int size = RUN; size < array.Length; size = 2 * size)
            {
                for (int left = 0; left < array.Length; left += 2 * size)
                {
                    int mid = left + size - 1;
                    int right = Math.Min((left + 2 * size - 1), (array.Length - 1));

                    merge(array, left, mid, right);
                }
            }

        } // Tim

10 → 20000 Synthetic

10 → 20000 Real

Counting

Исходная последовательность чисел длины nn, а в конце отсортированная, хранится в массиве A. Также используется вспомогательный массив Cс индексами от 0 до k−1 , изначально заполняемый нулями.

public static void Counting(ref int[] array)
        {
            int min = 0;
            int max = 0;
            for (int i = 0; i < array.Length; i++)
            {
                if (array[i] < min)
                    min = array[i];
                if (array[i] > max)
                    max = array[i];
            }

            int[] count = new int[max - min + 1];
            int z = 0;

            for (int i = 0; i < count.Length; i++)
                count[i] = 0;

            for (int i = 0; i < array.Length; i++)
                count[array[i] - min]++;

            for (int i = min; i <= max; i++)
            {
                while (count[i - min]-- > 0)
                {
                    array[z] = i;
                    ++z;
                }
            }

        } // Counting

10 → 50000 Synthetic

10 → 50000 Real

Bucket

Для карманной сортировки нужно разбить элементы массива входных данных на k блоков (карманов, корзин). Далее каждый из таких блоков сортируется либо другой сортировкой, либо рекурсивно тем же методом разбиения. После сортировок внутри каждых блоков