Программирование на C и C++

Онлайн справочник программиста на C и C++

шейкер сортировка

Аватар пользователя merkul40
пн, 08/21/2017 - 21:09 -- merkul40

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

#include<stdio.h>
#include<stdlib.h>
#define N 100000        // 10000 3-5 сек; 100 000 1 мин 30 сек

int Mass[N];
void determination(void);
void shaker(void);
void printing(void);

int main()
{
       
        determination();
        //printing();
        shaker();
        printing();
       
        return 0;        
        }
       
void determination(void)//функция присвоения значений массиву
{
        for (int i = 0; i <= (N - 1); i++)
        {
                Mass[i] = rand() % (N * 5);
                }
       
        }

void shaker(void)//функция упорядочения массива
{
        int tmp = 0, high = 0, low = (N - 1);
        while (high < low)
        {
                for (int i = high; i < low; i++)//двигаемся сверху вниз
                {
                        if (Mass[i] > Mass[i + 1])      //если текущее значение больше
                        {
                                tmp = Mass[i];          //следующего меняем их местами
                                Mass[i] = Mass[i + 1];  //(двигаем его вниз)
                                Mass[i + 1] = tmp;                      //
                               
                                }
                                }
                        low--;//обратите внимание, что нижняя граница поднимается
                                        //вверх    (если сделать наоборот, ,,,,)
                for (int j = low; j > high; j--)//двигаемся снизу вверх
                {
                        if (Mass[j] < Mass[j - 1])      //если текущее значение меньше
                        {
                               
                                tmp = Mass[j];          //следующего меняем их местами
                                Mass[j] = Mass[j - 1];  //(двигаем его вверх)
                                Mass[j - 1] = tmp;                      //
                               
                                }
                                }
                high++;
                }
       
        }
       
void printing(void)//функция вывода массива на экран
{
        for (int i = 0; i <= (N - 1); i++)
        {
                printf("%d\t%d\n", i + 1, Mass[i]);
                }
        }