commit 59546d01e6ed263ce8f472ef9542bef5a1c7fe08
parent ce773fce3e485d96e8c5757518487e926823c71e
Author: klewer-martin <martin.cachari@gmail.com>
Date: Fri, 25 Mar 2022 00:27:40 -0300
Improved sorting algorithms
Diffstat:
| M | Makefile | | | 2 | +- |
| M | README.md | | | 4 | ++-- |
| M | sav.c | | | 88 | ++++++++++++++++++++++++++++++++++++------------------------------------------- |
| A | sort.c | | | 56 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | sort.h | | | 7 | +++++++ |
5 files changed, 106 insertions(+), 51 deletions(-)
diff --git a/Makefile b/Makefile
@@ -1,7 +1,7 @@
CC := cc
CLIBS :=
CFLAGS := `sdl2-config --libs --cflags` -lSDL2_image -lm
-SRCS := sav.c util.c
+SRCS := sav.c util.c sort.c
OBJS := $(SRCS:.c=.o)
TARGET := sav
diff --git a/README.md b/README.md
@@ -1,3 +1,3 @@
-# Sorting Algorithms Visualized [ WIP ]
+# SAV - Sorting Algorithms Visualized
-The idea is to make a visual program that shows how an array is being sorted
+The idea is to develop a visual program that shows how an array is being sorted
diff --git a/sav.c b/sav.c
@@ -8,6 +8,7 @@
#include "drw.h"
#include "util.h"
+#include "sort.h"
#define WINDOW_TITLE "Sorting Algorithms Visualized"
#define WINDOW_WIDTH 0
@@ -17,8 +18,6 @@
#define Y_BORDER 50
#define RECT_WIDTH 5
-#define INIT_SIZE 50
-
typedef struct {
SDL_Window *window;
SDL_Renderer *rend;
@@ -27,13 +26,17 @@ typedef struct {
} Root;
Root root;
-static size_t x = 0;
+
+SDL_Window *window;
+SDL_Renderer *renderer;
+int w, h;
+size_t x = 0;
void setup(void) {
SDL_Init(SDL_INIT_VIDEO);
// Create an application window with the following settings:
- root.window = SDL_CreateWindow(
+ window = SDL_CreateWindow(
WINDOW_TITLE, // window title
SDL_WINDOWPOS_UNDEFINED, // initial x position
SDL_WINDOWPOS_UNDEFINED, // initial y position
@@ -43,22 +46,19 @@ void setup(void) {
SDL_WINDOW_RESIZABLE // window flags
);
- root.x_border = 5;
- root.y_border = 5;
+ renderer = SDL_CreateRenderer(window, -1, SDL_RENDERER_ACCELERATED);
- root.rend = SDL_CreateRenderer(root.window, -1, SDL_RENDERER_ACCELERATED);
+ if (!window) end("SDL: window cannot be created");
- if (!root.window) end("SDL: window cannot be created");
-
- SDL_SetRenderDrawColor(root.rend, 32, 32, 32, 0);
- SDL_RenderClear(root.rend);
- SDL_RenderPresent(root.rend);
- SDL_RenderClear(root.rend);
+ SDL_SetRenderDrawColor(renderer, 32, 32, 32, 0);
+ SDL_RenderClear(renderer);
+ SDL_RenderPresent(renderer);
+ SDL_RenderClear(renderer);
}
void cleanup(void) {
- SDL_DestroyRenderer(root.rend);
- SDL_DestroyWindow(root.window);
+ SDL_DestroyRenderer(renderer);
+ SDL_DestroyWindow(window);
SDL_Quit();
}
@@ -66,44 +66,24 @@ void drw_element(size_t height) {
SDL_Rect r;
r.x = X_BORDER + x; // bottom left + x
- r.y = root.h - Y_BORDER + 1; // bottom
+ r.y = h - Y_BORDER + 1; // bottom
r.w = RECT_WIDTH; // fixed width
r.h = -height;
- SDL_RenderDrawRect(root.rend, &r);
- SDL_SetRenderDrawColor(root.rend, 255, 0, 0, 0);
- SDL_RenderFillRect(root.rend, &r);
+ SDL_RenderDrawRect(renderer, &r);
+ SDL_SetRenderDrawColor(renderer, 255, 0, 0, 0);
+ SDL_RenderFillRect(renderer, &r);
- SDL_SetRenderDrawColor(root.rend, 0, 0, 0, 0);
- SDL_RenderDrawLine(root.rend,
+ SDL_SetRenderDrawColor(renderer, 0, 0, 0, 0);
+ SDL_RenderDrawLine(renderer,
x + X_BORDER,
- root.h - Y_BORDER,
+ h - Y_BORDER,
x + X_BORDER,
- root.h - Y_BORDER - height);
+ h - Y_BORDER - height);
x += RECT_WIDTH;
}
-void bubble_sort(int *arr, size_t len)
-{
- if(arr == NULL) return;
-
- size_t swaps, top;
- top = len;
- for(size_t i = 0; i < len; ++i) {
- for(size_t j = 0; j < (top - 1); j++) {
- if(arr[j] > arr[j + 1]) {
- swap(&arr[j], &arr[j + 1]);
- swaps++;
- } else if(arr[top - 1] == (arr[top] - 1)) {
- len--;
- }
- }
- if(swaps == 0) break;
- top--;
- }
-}
-
int main (void) {
setup();
@@ -117,6 +97,8 @@ int main (void) {
arr[i] = (rand() % arr_max);
bool run = true;
+ bool sorted = false;
+
while(run) {
SDL_Event event;
@@ -128,15 +110,25 @@ int main (void) {
break;
}
}
- SDL_SetRenderDrawColor(root.rend, 28, 28, 28, 0);
- SDL_RenderPresent(root.rend);
- SDL_RenderClear(root.rend);
- SDL_GetWindowSize(root.window, &root.w, &root.h);
+ SDL_SetRenderDrawColor(renderer, 28, 28, 28, 0);
+ SDL_RenderPresent(renderer);
+ SDL_RenderClear(renderer);
+ SDL_GetWindowSize(window, &w, &h);
for(size_t i = 0; i < len; i++)
drw_element(arr[i]);
- SDL_RenderPresent(root.rend);
+ SDL_RenderPresent(renderer);
+
+ if(sorted == false) {
+ if(!insertion_sort(arr, len)) {
+ sorted = true;
+ printf("The array has been sorted\n");
+ }
+ }
+
+ SDL_Delay(100);
+
x = 0;
}
diff --git a/sort.c b/sort.c
@@ -0,0 +1,56 @@
+#include <stdio.h>
+
+#include "sort.h"
+#include "util.h"
+
+int bubble_sort(int *arr, size_t len) {
+ if(arr == NULL) return 1;
+
+ size_t swaps, top;
+ top = len;
+
+ static size_t i = 0;
+ static size_t j = 100;
+
+ if(i < len) {
+ if(j > (i + 1)) {
+ if(arr[j] < arr[j - 1])
+ swap(&arr[j], &arr[j + 1]);
+
+ printf("j: %ld\n", j);
+
+ j--;
+ return 1;
+ }
+ /* if(swaps == 0) break; */
+ printf("i: %ld\n", i);
+ i++;
+ j = 100;
+ } else return 0;
+
+ return 1;
+}
+
+int insertion_sort(int *arr, size_t len) {
+ static size_t i = 1;
+ int j;
+
+ int key;
+
+ if(i < len) {
+ key = arr[i];
+ j = i - 1;
+
+ while((j >= 0) && (arr[j] > key)) {
+ arr[j + 1] = arr[j];
+ j = j - 1;
+ }
+
+ arr[j + 1] = key;
+ i++;
+ return 1;
+ }
+
+ return 0;
+}
+
diff --git a/sort.h b/sort.h
@@ -0,0 +1,7 @@
+#ifndef __SORT_H__
+#define __SORT_H__
+
+int bubble_sort(int *arr, size_t len);
+int insertion_sort(int *arr, size_t len);
+
+#endif // __SORT_H__
