Заметили ошибку ?
Выделите это место и нажмите Ctrl + Q

Информатика. Шейкер-сортировка.


Привет, Друзья! Сегодня разберём алгоритм сортировки "метод встряхивания" или Шейкер-сортировку. Данная тема хорошо подходит для повторения массивов на уроке информатики. Алгоритм основан на методе пузырька, который я уже разбирал на своём сайте.


Предположим нам необходимо отсортировать массив: 3, 4, 22, 6, 1 . Если мы будем сортировать этот массив классическим методом пузырька, то самый последний элемент 1 встанет на своё место только после прохождения длина массива - 1 раз по всему массиву.


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


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


Реализовывать программу будем на языке C#, который отлично подходит для изучения информатики в старших классах.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp14
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] a = { 3, 4, 22, 6, 1 };
            int l = 0;
            int r = a.Length - 1;
            bool exchange;
           
            do
            {
                exchange = false;

                bubble(ref a, l, r, ref exchange);
                r--;

                bubble(ref a, r, l, ref exchange);
                l++;
            } while (exchange);


            for (int i=0; i < a.Length;i++)
            { 
                Console.WriteLine(a[i]);
            }
           
            Console.ReadKey();

        }

        static void bubble( ref int[] b, int n, int m, ref bool exchange)
        {
            int temp;

            if (m == n) return ;
  
            if (n < m)
            {
                for(int i = n; i < m; i++)
                {
                    if(b[i] > b[i+1])
                    {
                        temp = b[i];
                        b[i] = b[i + 1];
                        b[i + 1] = temp;
                        exchange = true;
                    }  
                }
            }
            else
            {
                for (int i = n; i > m; i--)
                {
                    if (b[i] < b[i-1])
                    {
                        temp = b[i];
                        b[i] = b[i - 1];
                        b[i - 1] = temp;
                        exchange = true;
                    }
                }
            }
            return ;
        } 
    }
}




На этом всё, любите информатику и алгоритмы. Можете посмотреть видеоурок.


Счастливого программрования!





25-01-2018 в 17:19:58





Похожая статья:

Приёмы на уроке информатики - меняем переменные местами без использования третьей переменной

Сегодня разберём хороший приём по информатике: как поменять значения п...

Категория: Алгоритмы  Подкатегория: Задачи
Дата: 15-01-2018 в 16:47:34 0



Оставить коментарий:



Напишите email, чтобы получать сообщения о новых комментариях (необязательно):


Задача против робота. Расположите картинки горизонтально:


Последние
видео:



Присылайте ваши задачи
Шейкер-сортировка (С#)


Подготовка к
ОГЭ


Подготовка к ОГЭ по информатике


Давайте
дружить!


Группа Вконтакте Code-Enjoy

Твиттер Александра Калужского

YouTube канал Code-Enjoy


Препод напал на тебя как вампир? Не бойся! Студланс защитит этот мир!