Визуализация базовых сортировок, алгоритмов
Содержание
Описание[править]
Визуализация алгоритмов, базовых сортировок на языке программирования JavaScript
Исполнители: Цветкова Дарья - работа с дизайном
Сазыкин Георгий - работа с дизайном и технической составляющей проекта
Васин Данила - работа с технической частью проекта
Группа 3630103/00001 Кафедра Теоретической механики
Визуализация[править]
Введение[править]
Данный курсовой проект “Ресурс с визуализацией сортировок и базовых алгоритмов” предназначен для ознакомления и понимания, какие существуют сортировки. Сама визуализация сортировок показывает принцип их работы, а также плюсы и минусы каждой из них. Также представлена работа числа Фибоначчи и Капрекара.
Актуальность[править]
Сортировки используются во всех областях программирования (базы данных или математические программы) для упорядочения некоторого множества элементов, поэтому не коснуться данной темы невозможно, чтобы стать успешным программистом. Визуализация игры «камень-ножницы-бумага» несёт развлекательный характер. Показывает работу функции Math.random. Визуализация числа Капрекара: - демонстрация свойств чисел; Визуализация чисел Фибоначчи: - демонстрация рекурсии.
Теория[править]
В этом курсовом проекте мы затронули такие сортировки:
- глупая (stupid);
- гномья (gnome);
- пузырьковая (bubble);
- шейкерная (shake);
Последовательности:
- число Фибоначчи;
- число Капрекара;
Stupid sort (глупая сортировка): пробегаемся по массиву (по порядку!) и, встретив два неотсортированных «соседа», меняем их местами. После этого возвращаемся в начало и опять бежим до тех пор, пока не встретим следующих неотсортированных «соседей», если же массив отсортирован, наша работа закончена.
Gnome sort (гномья): алгоритм данной сортировки разработан гномами, сортировавшими садовые горшки (шутка!). У нас есть массив, в котором сравниваются 2 рядом стоящих элемента, если они расположены в порядке, который мы хотим получить в конце, то идём дальше, если нет – меняем местами и переходим на предыдущий. Однако бывают случаи, когда предыдущего элемента нет, тогда мы идём вперед до тех пор, пока массив не закончится. Важно! Сортировка начинается со второго элемента массива.
Bubble sort (сортировка пузырьком): также она называется сортировкой простыми обменами. Её принцип действия заключается в прохождении по массиву от начала и до конца. В результате первого прохода на второе место уходит максимальный элемент. Например: сортировка из 2 элементов: 5, 2. Сравниваем 5 и 2, 5 > 2 => меняем местами и получаем 2, 5. По сути, мы берем первые 2 элемента массива, сравниваем их, если они стоят в неправильном порядке – меняем местами и потом уже рассматриваем 2 элемент с 3 и так до последнего. После первого пробега делаем все то же самое, чтобы получить отсортированный массив.
Shake sort (шейкерная/коктейльная сортировка): принцип работы похож на пузырьковую, только пробегаться по массиву надо туда-сюда. Рассматриваем первые 2 элемента, если они отсортированы – идем дальше, если нет – меняем местами и тоже идем дальше. После того, как мы нашли максимальный элемент массива, бежим в обратную сторону, попутно сравнивая каждые 2 элемента. Важно! Отсортированные (боковые) элементы мы уже не трогаем.
Числа Фибоначчи: элементы числовой последовательности, в которой каждое последующее число равно сумме двух предыдущих чисел.
Число Капрекара: 6174 Выбираем любое четырехзначное число, в котором разряды не повторяются. После этого переставляем цифры так, чтобы получить самое большое число и самое маленькое – вычитаем и повторяем операцию с полученным числом до тех пор, пока не получим 6174. Пример: 1789.
9871-1789=8082
8820-0288=8532
8532-2358 =6174!
Особенности реализации[править]
Код программы на Javascript 1 function stupidSort(){
2 if (T[i]<T[i-1])
3 {
4 var tmp = T[i];
5 T[i] = T[i-1];
6 T[i-1] = tmp;
7 i = 0;
8 }
9 i++;
10 return i;
11 }
12
13
14 function draw(){
15 if (i==0){
16 i=150;
17 }
18 ctx.clearRect(0,0,w,h);
19 ctx.font = "small-caps 170px STXinwei"
20 ctx.fillStyle = "DarkSlateBlue"
21 ctx.fillText(z, 200, 250);
22 ctx.fillText(x, 200+i, 250);
23 i= i-2;
24 n= n-2;
25 if (n<=0){
26 i=150;
27 x=0;
28 y=1;
29 ctx.clearRect(0,0,w,h);
30 ctx.fillText(z, 300, 250);
31 }
32
33 }
34
35 function Fibb()
36 {
37 if(i==0){
38 console.log(x);
39 console.log(y);
40
41 z = x + y;
42 x = y;
43 y = z;
44 }
45 }
Для визуализации сортировок не был использован цикл for(необходимый сортировкам в частности). Числа Фибоначчи появляются на экране с помощью отрисовки каждого шага, конечный результат - появление следующего числа Фибоначчи.
Вывод[править]
Подводя итоги курсовой работы, мы можем сказать, что поставленная задача была выполнена, а также достигнуты сопутствующие ей цели. В ходе выполнения данного проекта был получен ценный опыт работы с необходимым инструментарием языка JavaScript, а также мы научились использовать CSS для анимации и работать в группе.
