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

Опубликовано: 12 Января, 2022

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

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

Подход:

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

Примеры:

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

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

Below is the program to visualize theSelection Sort algorithm:

// C++ program for visualization
// of bubble sort
  
#include "graphics.h"
#include <bits/stdc++.h>
  
using namespace std;
  
// Initialize the size
// with the total numbers to sorted
// and the gap to be maintained in graph
vector<int> numbers;
int size = 200;
int gap = 4;
  
// Function for swapping the lines graphically
void swap_colors(int i, int j, int x, int y)
{
  
    // y is the minimum element,
    // first make this number green
    // Now, swapping it by making black again
    // and then draw the pixels
    // for white colour with x value.
    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 is the element to be swapped,
    // first make this number black
    // Now, highlight y with green
    // representing the minimum element
    // and then draw the pixels
    // for white colour with y value.
    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);
}
  
// Function for swapping two numbers
void swap(int* xp, int* yp)
{
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}
  
// Selection sort function
void selsort()
{
    for (int i = 0; i < size - 1; i++) {
  
        // Find the minimum element
        // in unsorted array
        int min_idx = i;
  
        for (int j = i + 1; j < size; j++) {
            if (numbers[j] < numbers[min_idx]) {
                min_idx = j;
            }
        }
  
        // Swap the found minimum element
        // with the first element
        // delay(500);
        swap(&numbers[min_idx],
             &numbers[i]);
  
        // Function to show transition in swapping
        swap_colors(gap * i + 1,
                    gap * (min_idx) + 1,
                    numbers[min_idx],
                    numbers[i]);
    }
}
  
// Driver program
int main()
{
  
    // auto detection of screen size
    int gd = DETECT, gm;
    int wid1;
  
    // Graph initialization
    initgraph(&gd, &gm, NULL);
  
    // setting up window size (gap*size) * (size)
    wid1 = initwindow(gap * size + 1, size + 1);
    setcurrentwindow(wid1);
  
    // Initializing the array
    for (int i = 1; i <= size; i++)
        numbers.push_back(i);
  
    // Find a seed and shuffle the array
    // to make it random.
    // Here  different type of array
    // can be taken to results
    // such as nearly sorted, already sorted,
    // reverse sorted to visualize the result
    unsigned seed
        = chrono::system_clock::now()
              .time_since_epoch()
              .count();
  
    shuffle(numbers.begin(),
            numbers.end(),
            default_random_engine(seed));
  
    // Initial plot of numbers in graph taking
    // the vector position as x-axis and its
    // corresponding value will be the height of line.
    for (int i = 1; i <= gap * size; i += gap) {
        line(i, size, i, (size - numbers[i / gap]));
    }
  
    // Delay the code
    delay(200);
  
    // Call sort
    selSort();
  
    for (int i = 0; i < size; i++) {
        cout << numbers[i] << " ";
    }
    cout << endl;
  
    // Wait for sometime .
    delay(5000);
  
    // Close the graph
    closegraph();
  
    return 0;
}

Output:

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

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Алгоритмы Структуры данных

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

РЕКОМЕНДУЕМЫЕ СТАТЬИ