Алгоритмы сортировки

      Например  в массиве А, размерностью от 1 до 10 могут содержаться числа ТОЛЬКО от 1 до 10. Иначе алгоритм уже не сработает!

      Суть  заключается в следующем: в массив счетчиков С записывается значение счетчика для каждого элемента. Т.е., если цифра 5 в исходном массиве встречается 3 раза, то значение будет соответственно 3. Далее, за счет того, что числа не выходят за рамки размерности массива, происходит сама сортировка. Заключается она в последовательной записи чисел в выходной массив от 0 (или от 1, в зависимости от нумерации массива) до N, где каждое число будет записано столько раз, сколько оно встречается в исходном массиве.

      Описание 2 (модифицированный алгоритм).

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

      Временная и ёмкостная сложности алгоритма

      Пусть n — длина исходного массива, k — максимальное число в массиве.

Тогда временная сложность алгоритма равна O(n+k), а ёмкостная — O(n+k).

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

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

    Когда данные сортируются не в оперативной  памяти, а на жестком диске, особенно если ключ связан с большим объемом  дополнительной информации, то количество перемещений элементов существенно  влияет на время работы. Этот алгоритм уменьшает количество таких перемещений, действуя следующим образом: за один проход из всех элементов выбирается минимальный и максимальный. Потом минимальный элемент помещается в начало массива, а максимальный, соответственно, в конец. Далее алгоритм выполняется для остальных данных. Таким образом, за каждый проход два элемента помещаются на свои места, а значит, понадобится N/2 проходов, где N - количество элементов.

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

ЗАКЛЮЧЕНИЕ 

    Рассмотрев некоторые, самые распространенные различные алгоритмы сортировки, можно сказать следующее:

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

 
 
 
 

Изображенный  ниже график иллюстрирует разницу в эффективности изученных алгоритмов.

(нумерация  линий сверху вниз)

первая линия:           сортировка пузырьком;

вторая линия:           сортировка перемешиванием;

третья линия:           сортировка выбором;

четвертая линия:     сортировка вставками;

пятая линия:            сортировка вставками со сторожевым элементом;

       шестая линия:          сортировка Шелла. 
 
 
 
 
 
 
 
 
 
 
 

СПИСОК  ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ 

Дональд Кнут Искусство программирования, том 3. Сортировка и поиск = The Art of Computer Programming, vol.3. Sorting and Searching. — 2-е изд. М.: «Вильямс», 2007. — С. 824. — ISBN 0-201-89685-0

Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1  
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

ПРАКТИЧЕСКАЯ  ЧАСТЬ №7 

1. Общая характеристика  задачи 

      Фирма ООО «Стройдизайн» осуществляет деятельность, связанную с выполнением  работ по ремонту помещений. Прайс-лист на выполняемые работы приведен в таблице №1. Данные о заказанных работах указаны в таблице №2. 

      Таблица №1

 

      Таблица №2

 

      Задача:

1. Построить таблицы по приведенным выше данным.
2. Выполнить расчет стоимости выполняемых работ по полученному заказу, данные расчета занести в таблицу №2.
3. Организовать межтабличные связи для автоматического формирования счета, выставляемого клиенту для оплаты выполняемых работ.
4. Результаты расчета стоимости каждого вида работ по полученному заказу представить в графическом виде.

 

2. Описание алгоритма решения задачи

1) Запустить  табличный процессор MS Excel.

2) Создать книгу  с именем «Стройдизайн».

3) Лист1 переименовать  в лист Прайс-лист.

4) На рабочем  листе Прайс-лист MS Excel создать таблицу прайс-листа.

5) Заполнить  таблицу прайс-листа исходными  данными из Таблицы №1.

6) Лист2 переименовать  в лист Расчет стоимости работ.

7) На рабочем  листе Расчет стоимости работ MS Excel создать таблицу, в которой будет рассчитываться стоимость выполняемых работ по полученному заказу.

8) Заполнить  таблицу со списком работ исходными данными из Таблицы №2.

9) Заполнить графу Цена за ед. изм., руб. таблицы Расчет стоимости работ, находящейся на листе Расчет стоимости работ следующим образом:

      Занести в ячейку D5 формулу:

      =ВПР(A5;'Прайс-лист'!$A$4:$C$9;3).

      Размножить введенную формулу в ячейку D5 для остальных ячеек (с D6 по D8) данной графы.

10) В графе  Стоимость работ, руб. таблицы Расчет стоимости работ, находящейся на листе Расчет стоимости работ в ячейку E5 внести формулу:

      =C5*D5

      Размножить  введенную формулу в ячейку E5 для остальных ячеек (с E6 по E8) данной графы.

11) Лист3 переименовать в лист с названием Форма счета.

12) На рабочем листе Форма счета MS Excel создать форму счета.

13) Путем создания  межтабличных связей заполнить  созданную форму полученными  данными из таблицы Расчет стоимости выполняемых работ.

14) Лист4 переименовать в лист с названием График.

15) На рабочем  листе График MS Excel представить графически результаты стоимости работ полученные на листе Форма счета в графе Стоимость работ, руб. (Подписями по оси X будут являться Наименования работ, значениями по оси Y будут являться полученные в данном заказе стоимости каждого вида работ). 

3. Результаты выполнения контрольного примера 

лист Расчет стоимости работ