Рубрики

Алгоритмы сортировки Визуализация | Выбор сортировки

Предварительное условие: Выбор Сортировка

Человеческий мозг может легко обрабатывать визуальные эффекты, несмотря на длинные коды для понимания алгоритмов. В этой статье визуализация выбора сортировки была реализована с использованием библиотеки graphics.h . Как мы все знаем, выборочная сортировка сначала находит минимальный элемент из несортированного массива и заменяет его первым элементом несортированного массива в каждом проходе. Становится трудно анализировать данные вручную между двумя алгоритмами или наоборот, но графическое построение намного проще для понимания.

Подходить:

  • Белая линия используется для представления длины числа (9 представлено 9 пикселями по вертикали вверх), а его позиция представляет индекс в массиве.
  • Графическое представление случайно распределенных чисел показано ниже.
  • Графически сортировку можно показать, сначала закрасив минимальный элемент из несортированного массива зеленым цветом.
  • Теперь поменяйте его местами с первым элементом несортированного массива, а также поменяйте цвет этих двух чисел, как показано в коде функцией swap_colors () .
  • Здесь delay () можно увеличить, чтобы увидеть переход на графике.

Примеры:

Используемые заранее определенные функции:

  • setcurrentwindow (): функция, которая используется для установки размера текущего окна.
  • setcolor (n): функция, которая используется для изменения цвета курсора путем изменения значения n.
  • delay (n): функция, которая используется для задержки программы на n миллисекунд. Используется для замедления скорости переходов
  • линия (x1, y1, x2, y2): функция, которая используется для рисования линии от точки (x1, y1) к точке (x2, y2). (0, 0) — левый верхний угол экрана, а нижний правый — (n1, n2), где n1, n2 — ширина и высота текущего окна. Есть другие графики, которые можно применить к этой строке, используя setcolor () .

Ниже приведена программа для визуализации алгоритма сортировки выбора :

// C ++ программа для визуализации
// пузырьковой сортировки

  
#include "graphics.h"
#include <bits/stdc++.h>

  

using namespace std;

  
// Инициализируем размер
// с общим количеством отсортированных
// и разрыв, который будет поддерживаться в графике

vector<int> numbers;

int size = 200;

int gap = 4;

  
// Функция графического обмена линиями

void swap_colors(int i, int j, int x, int y)

{

  

    // у минимальный элемент,

    // сначала делаем это число зеленым

    // Теперь меняем его местами, снова делая черным

    // а затем рисуем пиксели

    // для белого цвета со значением х.

    setcolor(GREEN);

    line(j, size, j, size - y);

  

    delay(500);

  

    setcolor(BLACK);

    line(j, size, j, size - y);

  

    setcolor(WHITE);

    line(j, size, j, size - x);

  

    // X - это элемент, который нужно поменять местами,

    // сначала делаем это число черным

    // Теперь выделите y зеленым цветом

    // представляющий минимальный элемент

    // а затем рисуем пиксели

    // для белого цвета со значением у.

    setcolor(BLACK);

    line(i, size, i, size - x);

  

    setcolor(GREEN);

    line(i, size, i, size - y);

  

    delay(500);

  

    setcolor(WHITE);

    line(i, size, i, size - y);

}

  
// Функция для замены двух чисел

void swap(int* xp, int* yp)

{

    int temp = *xp;

    *xp = *yp;

    *yp = temp;

}

  
// Функция сортировки выделения

void selsort()

{

    for (int i = 0; i < size - 1; i++) {

  

        // Находим минимальный элемент

        // в несортированном массиве

        int min_idx = i;

  

        for (int j = i + 1; j < size; j++) {

            if (numbers[j] < numbers[min_idx]) {

                min_idx = j;

            }

        }

  

        // Меняем найденный минимальный элемент

        // с первым элементом

        // задержка (500);

        swap(&numbers[min_idx],

             &numbers[i]);

  

        // Функция для показа перехода при обмене

        swap_colors(gap * i + 1,

                    gap * (min_idx) + 1,

                    numbers[min_idx],

                    numbers[i]);

    }

}

  
// Драйвер программы

int main()

{

  

    // автоматическое определение размера экрана

    int gd = DETECT, gm;

    int wid1;

  

    // Инициализация графика

    initgraph(&gd, &gm, NULL);

  

    // настройка размера окна (промежуток * размер) * (размер)

    wid1 = initwindow(gap * size + 1, size + 1);

    setcurrentwindow(wid1);

  

    // Инициализация массива

    for (int i = 1; i <= size; i++)

        numbers.push_back(i);

  

    // Найти семя и перемешать массив

    // сделать случайным

    // Здесь другой тип массива

    // можно принять к результатам

    // такие как почти отсортированные, уже отсортированные,

    // обратный порядок сортировки для визуализации результата

    unsigned seed

        = chrono::system_clock::now()

              .time_since_epoch()

              .count();

  

    shuffle(numbers.begin(),

            numbers.end(),

            default_random_engine(seed));

  

    // Начальный график чисел при построении графика

    // положение вектора по оси х и его

    // соответствующее значение будет высотой строки.

    for (int i = 1; i <= gap * size; i += gap) {

        line(i, size, i, (size - numbers[i / gap]));

    }

  

    // Задержка кода

    delay(200);

  

    // Call sort

    selSort();

  

    for (int i = 0; i < size; i++) {

        cout << numbers[i] << " ";

    }

    cout << endl;

  

    // Подожди немного.

    delay(5000);

  

    // Закрыть график

    closegraph();

  

    return 0;

}

Выход:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57
58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84
85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108
109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128
129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148
149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168
169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188
189 190 191 192 193 194 195 196 197 198 199 200

Визуализация:

  • Входная визуализация:

    Несортированный массив

  • Выходная визуализация:

    Сортировка массива с использованием Selection Sort

Рекомендуемые посты:

Алгоритмы сортировки Визуализация | Выбор сортировки

0.00 (0%) 0 votes