Mercurial > public > algo-animator
changeset 21:8a5a7aee69ce
add description
author | Dennis C. M. <dennis@denniscm.com> |
---|---|
date | Tue, 27 Jun 2023 20:04:25 +0100 |
parents | fc44102980fb |
children | a83fa0b5ea96 |
files | README.md main.c |
diffstat | 2 files changed, 124 insertions(+), 82 deletions(-) [+] |
line wrap: on
line diff
--- a/README.md Mon Jun 26 18:12:03 2023 +0100 +++ b/README.md Tue Jun 27 20:04:25 2023 +0100 @@ -1,7 +1,34 @@ # algo-animator -## Compile and run +This project is inspired by - off course - the video by Timo Bingmann called [15 sorting algorithms in 6 minutes](https://www.youtube.com/watch?v=kPRA0W1kECg). + +## Compile + ```bash gcc main.c -lglut -lGL -lGLU -lm -I/usr/local/include/freetype2 -L/usr/local/lib -lfreetype -./a.out ``` + +## To improve + +Since `GLUT` is single-thread, I cannot call `glutPostRedisplay()` within `while` or `for loops` to redraw the screen in every +step of the selected sorting algorithm. I guess the solution is multi-threading, so I can perform the sorting in the second thread +and post notifications to the main thread to redraw the screen. + +Since this is my first OpenGL project and just my second program in C, I am tired and I don't want to spend more time in this project, +but maybe in the future I'll do it. Right now there are just two algorithms supported. I've implemented them in a way that every function +call is a single step of the sorting. So, storing the "state" outside the function, I can use `idle()` as the loop of the sorting algorithm. + +Let's say we selected `bubble sort`. Once you press `ENTER`, the process will be like this: + +```c +run = true; +bubble_sort(); +glutPostRedisplay; +bubble_sort(); +glutPostRedisplay; +bubble_sort(); +glutPostRedisplay; + +// Continue until the array is sorted +run = false; +```
--- a/main.c Mon Jun 26 18:12:03 2023 +0100 +++ b/main.c Tue Jun 27 20:04:25 2023 +0100 @@ -8,17 +8,66 @@ #include FT_FREETYPE_H +#define WINDOW_WIDTH 1920 #define WINDOW_HEIGHT 1080 -#define WINDOW_WIDTH 1920 #define VPADDING 150 #define RECT_WIDTH 5 #define SPACE 1 -/* Global variables */ +/* Helper functions */ + +struct Element { + float value; + bool current; +}; + +struct Element *arr; +int arr_size; + +void create_array() { + arr_size = WINDOW_WIDTH / (RECT_WIDTH + SPACE); + arr = malloc(arr_size * sizeof(struct Element)); + + float rect_increase = (WINDOW_HEIGHT - VPADDING * 2) / (float)(arr_size - 1); + + for (int i = 1; i <= arr_size; i++) { + arr[i - 1].value = i * rect_increase; + arr[i - 1].current = false; + } +} + -FT_Library ft_library; -FT_Face ft_face; +void swap_elements(int x, int y) { + struct Element temp = arr[x]; + arr[x] = arr[y]; + arr[y] = temp; +} + + +void randomize_array() { + srand(time(NULL)); + + // Fisher-Yates shuffle + for (int i = arr_size - 1; i > 0; i--) { + int j = rand() % (i + 1); + + // Swap + swap_elements(i, j); + } +} + + +bool array_sorted() { + for (int i = 0; i < arr_size - 1; i++) { + if (arr[i].value > arr[i + 1].value) { + return false; + } + } + + return true; +} + struct Algo { char name[50]; @@ -26,22 +75,17 @@ }; struct Algo algos[2]; - int selected_algo = 0; -int speed = 1; -int refresh_counter = 0; -int iter_counter = 0; -int arr_size; - -struct Element { - float value; - bool current; -}; +void algo_selector(int direction) { + int selection = selected_algo + direction; + int lower = 0; + int upper = (sizeof(algos) / sizeof(algos[0])) - 1; -struct Element *arr; - -bool run; + if (selection >= lower && selection <= upper) { + selected_algo = selection; + } +} /* Algorithms */ @@ -53,13 +97,12 @@ int c; }; -struct AlgoState as = {0, 0, 0}; - +struct AlgoState as; -void swap_elements(int x, int y) { - struct Element temp = arr[x]; - arr[x] = arr[y]; - arr[y] = temp; +void reset_state() { + as.a = 0; + as.b = 0; + as.c = 0; } @@ -92,13 +135,13 @@ * b: Index of boundary of sorted array * c: Index of the minimum element */ - + if (as.a < arr_size) { arr[as.a].current = true; if (arr[as.a].value < arr[as.c].value) { - + // Save new minimum as.c = as.a; } @@ -114,63 +157,29 @@ } -/* Helper functions */ - -void create_array() { - arr_size = WINDOW_WIDTH / (RECT_WIDTH + SPACE); - arr = malloc(arr_size * sizeof(struct Element)); +void quick_sort() { - float rect_increase = (WINDOW_HEIGHT - VPADDING * 2) / (float)(arr_size - 1); - - for (int i = 1; i <= arr_size; i++) { - arr[i - 1].value = i * rect_increase; - arr[i - 1].current = false; - } } -void randomize_array() { - srand(time(NULL)); +void insertion_sort() { - // Fisher-Yates shuffle - for (int i = arr_size - 1; i > 0; i--) { - int j = rand() % (i + 1); - - // Swap - swap_elements(i, j); - } } -bool array_sorted() { - for (int i = 0; i < arr_size - 1; i++) { - if (arr[i].value > arr[i + 1].value) { - return false; - } - } - - return true; -} - +void merge_sort() { -void algo_selector(int direction) { - int selection = selected_algo + direction; - int lower = 0; - int upper = (sizeof(algos) / sizeof(algos[0])) - 1; - - if (selection >= lower && selection <= upper) { - selected_algo = selection; - } } - - /* Render functions */ +FT_Library ft_library; +FT_Face ft_face; + void render_text(int x, int y, char* text) { for (const char *c = text; *c; c++) { - + // Get glyph index from character code FT_UInt glyph_index = FT_Get_Char_Index(ft_face, *c); @@ -203,11 +212,11 @@ memcpy(dest_row, src_row, glyph_bitmap->width); } - glyph_bitmap->buffer = flipped_bitmap; + glyph_bitmap->buffer = flipped_bitmap; - // Calculate the adjusted y position based on the glyph's bearing - int adjusted_y = y + (slot->bitmap_top - glyph_bitmap->rows); - + // Calculate the adjusted y position based on the glyph's bearing + int adjusted_y = y + (slot->bitmap_top - glyph_bitmap->rows); + glRasterPos2f(x, adjusted_y); glDrawPixels(glyph_bitmap->width, glyph_bitmap->rows, GL_LUMINANCE, GL_UNSIGNED_BYTE, glyph_bitmap->buffer); @@ -216,6 +225,9 @@ } +int speed = 50; +int iter_counter = 0; + void display() { glClear(GL_COLOR_BUFFER_BIT); @@ -223,7 +235,7 @@ int x = 0; for (int i = 0; i < arr_size; i++) { - + if (arr[i].current) { glColor3f(1.0, 1.0, 1.0); } else { @@ -255,10 +267,10 @@ // Top: Column 1 sprintf(text, "Algorithm: %s", algos[selected_algo].name); render_text(20, WINDOW_HEIGHT - 50, text); - + sprintf(text, "Speed: %i", speed); render_text(20, WINDOW_HEIGHT - 80, text); - + // Top: Column 2 sprintf(text, "Number of elements: %i", arr_size); render_text(500, WINDOW_HEIGHT - 50, text); @@ -274,6 +286,7 @@ // Bottom: Column 2 render_text(800, VPADDING - 50, "Press enter to run the algorithm."); + render_text(800, VPADDING - 80, "Press p to pause the algorithm."); glutSwapBuffers(); } @@ -281,6 +294,10 @@ /* Refresh function */ + +bool run; +int refresh_counter = 0; + void idle() { if (run) { algos[selected_algo].function(); @@ -326,9 +343,9 @@ run = false; // Reset algo steps - as = (struct AlgoState){0, 0}; + reset_state(); } - + // u: Increase speed if (key == 117) { speed++; @@ -340,7 +357,7 @@ speed--; } } - + // enter: Run program if (key == 13) { run = true; @@ -350,8 +367,6 @@ if (key == 112) { run = false; } - - } @@ -419,7 +434,7 @@ strcpy(algos[1].name, "Selection sort"); algos[1].function = &selection_sort; - + create_array(); glutInit(&argc, argv); @@ -438,7 +453,7 @@ free(arr); FT_Done_Face(ft_face); - FT_Done_FreeType(ft_library); + FT_Done_FreeType(ft_library); return 0; }