93 lines
2.3 KiB
C
93 lines
2.3 KiB
C
/* ************************************************************************** */
|
|
/* */
|
|
/* ::: :::::::: */
|
|
/* ft_sorting.c :+: :+: :+: */
|
|
/* +:+ +:+ +:+ */
|
|
/* By: alier <alier@student.42mulhouse.fr> +#+ +:+ +#+ */
|
|
/* +#+#+#+#+#+ +#+ */
|
|
/* Created: 2024/10/31 09:34:43 by alier #+# #+# */
|
|
/* Updated: 2025/01/17 11:07:04 by alier ### ########.fr */
|
|
/* */
|
|
/* ************************************************************************** */
|
|
|
|
#include <stddef.h>
|
|
#include <stdint.h>
|
|
#include <stdbool.h>
|
|
#include <stdlib.h>
|
|
#include <limits.h>
|
|
#include "ft_sorting.h"
|
|
|
|
static void ft_swap_bytes(void *a, void *b, size_t count)
|
|
{
|
|
uint8_t *x;
|
|
uint8_t *y;
|
|
uint8_t t;
|
|
size_t i;
|
|
|
|
x = (uint8_t *) a;
|
|
y = (uint8_t *) b;
|
|
i = 0;
|
|
while (i < count)
|
|
{
|
|
t = x[i];
|
|
x[i] = y[i];
|
|
y[i] = t;
|
|
i++;
|
|
}
|
|
}
|
|
|
|
/*
|
|
* Worst-case performance: O(n^2) comparisons, O(n^2) swaps
|
|
* Worst-case space complexity: O(n) total, O(1) auxiliary
|
|
*/
|
|
void ft_naive_bubblesort(void *base, size_t nmemb, size_t size,
|
|
t_compar compar)
|
|
{
|
|
bool swapped;
|
|
size_t i;
|
|
|
|
if (nmemb == 0)
|
|
return ;
|
|
swapped = true;
|
|
while (swapped)
|
|
{
|
|
swapped = false;
|
|
i = 0;
|
|
while (i < nmemb * size - size)
|
|
{
|
|
if (compar(base + i, base + i + size) > 0)
|
|
{
|
|
ft_swap_bytes(base + i, base + i + size, size);
|
|
swapped = true;
|
|
}
|
|
i += size;
|
|
}
|
|
}
|
|
}
|
|
|
|
static int compare_ints_asc(const void *a, const void *b)
|
|
{
|
|
if (*(int *) a > *(int *)b)
|
|
return (1);
|
|
else
|
|
return (-1);
|
|
}
|
|
|
|
int compare_strs_ptrs_asc(const void *a, const void *b)
|
|
{
|
|
const char *left;
|
|
const char *right;
|
|
|
|
left = *(const char **)a;
|
|
right = *(const char **)b;
|
|
return (ft_strcmp(left, right));
|
|
}
|
|
|
|
/*
|
|
* Worst-case performance: O(n^2) comparisons, O(n^2) swaps
|
|
* Worst-case space complexity: O(n) total, O(1) auxiliary
|
|
*/
|
|
void ft_naive_bubblesort_int_asc(int *base, size_t size)
|
|
{
|
|
ft_naive_bubblesort(base, size, sizeof(int), compare_ints_asc);
|
|
}
|