Skip to content

Instantly share code, notes, and snippets.

@Fluf22

Fluf22/heapsort.c

Last active December 31, 2015 11:19
Show Gist options
  • Save Fluf22/7978816 to your computer and use it in GitHub Desktop.
Save Fluf22/7978816 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
heapsort.c
/* ************************************************************************** */
/* */
/* ::: :::::::: */
/* heapsort.c :+: :+: :+: */
/* +:+ +:+ +:+ */
/* By: thoraffr <[email protected]> +#+ +:+ +#+ */
/* +#+#+#+#+#+ +#+ */
/* Created: 2013/12/14 22:26:19 by thoraffr #+# #+# */
/* Updated: 2013/12/15 16:18:41 by ksicart ### ########.fr */
/* */
/* ************************************************************************** */
#include "hotrace.h"
void sift_down(t_list **array, int start, int end)
{
int root;
int child;
root = start;
while ((root * 2 + 1) < end)
{
child = (root * 2 + 1);
if ((child + 1 < end) &&
(FAST_STRCMP(array[child]->keyword, array[child + 1]->keyword) < 0))
child++;
if (FAST_STRCMP(array[root]->keyword, array[child]->keyword) < 0)
{
ft_swap(array[child], array[root]);
root = child;
}
else
return ;
}
}
void ft_heapsort(t_list **array, int count)
{
int start;
int end;
start = (((count - 2) / 2) + 1);
while (--start >= 0)
sift_down(array, start, count);
end = count - 1;
while (end > 0)
{
ft_swap(array[end], array[0]);
sift_down(array, 0, end);
end--;
}
}
void ft_insertion_sort(t_list **tab, size_t n)
{
size_t i;
size_t j;
t_list *value;
i = 1;
while (i < n)
{
value = tab[i];
j = i;
while ((j > 0) && (FAST_STRCMP(value->keyword,
tab[j - 1]->keyword) > 0))
{
tab[j] = tab[j - 1];
j--;
}
tab[j] = value;
i++;
}
}
Raw
hotrace.c
/* ************************************************************************** */
/* */
/* ::: :::::::: */
/* hotrace.c :+: :+: :+: */
/* +:+ +:+ +:+ */
/* By: thoraffr <[email protected]> +#+ +:+ +#+ */
/* +#+#+#+#+#+ +#+ */
/* Created: 2013/12/14 12:55:02 by thoraffr #+# #+# */
/* Updated: 2013/12/15 21:22:54 by ksicart ### ########.fr */
/* */
/* ************************************************************************** */
#include "hotrace.h"
t_list **ft_init_tab(int nb_link, t_list **begin_list, t_list **tab)
{
t_list *tmp;
long int i;
i = 0;
tmp = *begin_list;
tab = (t_list **)malloc(sizeof(t_list *) * (nb_link));
while (tmp->next != NULL)
{
tab[i] = tmp;
tmp = tmp->next;
i++;
}
tab[i] = tmp;
return (tab);
}
t_list *ft_create_elem(char *keyword, char *data)
{
t_list *new_elem;
new_elem = malloc(sizeof(t_list));
new_elem->keyword = ft_strdup(keyword);
new_elem->data = ft_strdup(data);
new_elem->next = NULL;
return (new_elem);
}
void ft_list_push_front(t_list **begin_list, char *keyword, char *data)
{
t_list *new_link;
if (begin_list == NULL)
*begin_list = ft_create_elem(keyword, data);
else
{
new_link = ft_create_elem(keyword, data);
new_link->next = *begin_list;
*begin_list = new_link;
}
}
int main()
{
char *keyword;
char *data;
int nb_link;
t_list *begin_list;
t_list **tab;
tab = NULL;
begin_list = NULL;
nb_link = 0;
while (gnl(0, (char **)(&keyword)))
{
if (ft_strncmp(keyword, "\n", 1) < 0)
break ;
gnl(0, (char **)(&data));
ft_list_push_front(&begin_list, keyword, data);
nb_link++;
free(keyword);
free(data);
}
tab = ft_init_tab(nb_link, &begin_list, tab);
introsort(tab, nb_link);
ft_display(nb_link, tab);
return (0);
}
Raw
hotrace.h
/* ************************************************************************** */
/* */
/* ::: :::::::: */
/* hotrace.h :+: :+: :+: */
/* +:+ +:+ +:+ */
/* By: thoraffr <[email protected]> +#+ +:+ +#+ */
/* +#+#+#+#+#+ +#+ */
/* Created: 2013/12/14 12:40:08 by thoraffr #+# #+# */
/* Updated: 2013/12/15 22:25:20 by ksicart ### ########.fr */
/* */
/* ************************************************************************** */
#ifndef HOTRACE_C
# define HOTRACE_H
#include <unistd.h>
#include <stdlib.h>
#include <string.h>
#define BUFF_SIZE 1000
#define FAST_STRCMP(x, y) (*(x) != *(y) ? \
((unsigned char) *(x) - (unsigned char) *(y)) : \
strcmp((x), (y)))
typedef struct s_read
{
int size;
int index;
char *read;
int fd;
struct s_read *next;
} t_read;
typedef struct s_list
{
struct s_list *next;
char *keyword;
char *data;
} t_list;
int gnl(int const fd, char **line);
size_t ft_strlen(char const *str);
void ft_putstr(char const *s);
void ft_putendl(char const *s);
int ft_strcmp(const char *s1, const char *s2);
int ft_strncmp(const char *s1, const char *s2, size_t n);
char *ft_strdup(const char *s1);
double ft_log(float size);
double ft_pow(double nb, int p);
void ft_heapsort(t_list **array, int count);
void sift_down(t_list **array, int start, int end);
void introsort(t_list **data, int size);
void introsort_loop(t_list **data, int p, int r, int limit);
int tmedian(t_list **data, int e1, int e2, int e3);
int partition (t_list **data, int p, int r, int pivot);
void ft_swap(t_list *e1, t_list *e2);
void ft_search(int nb_link, t_list **tab, char *keyword, long int minor);
t_list **ft_init_tab(int nb_link, t_list **begin_list, t_list **tab);
void ft_display(int nb_link, t_list **tab);
void ft_insertion_sort(t_list **tab, size_t n);
void ft_list_push_front(t_list **begin_list, char *keyword, char *data);
t_list *ft_create_elem(char *keyword, char *data);
char **ft_sort_str(char **tab, t_list **keyword_list, int key_nb);
char *ft_strcpy(char *dest, const char *src);
#endif
Raw
introsort.c
/* ************************************************************************** */
/* */
/* ::: :::::::: */
/* introsort.c :+: :+: :+: */
/* +:+ +:+ +:+ */
/* By: ksicart <[email protected]> +#+ +:+ +#+ */
/* +#+#+#+#+#+ +#+ */
/* Created: 2013/12/14 14:45:00 by ksicart #+# #+# */
/* Updated: 2013/12/15 16:19:18 by ksicart ### ########.fr */
/* */
/* ************************************************************************** */
#include "hotrace.h"
void introsort(t_list **data, int size)
{
introsort_loop(data, 0, size - 1, (int)(ft_log(size) / 0.693147));
ft_insertion_sort(data, size);
}
void introsort_loop(t_list **data, int p, int r, int limit)
{
int pivot;
int pivot_loc;
if (limit == 0)
{
ft_heapsort((data + p), r - p + 1);
return ;
}
limit--;
pivot = tmedian(data, p, (p + r) / 2, r);
pivot_loc = partition(data, p, r, pivot);
if (pivot_loc - p - 1 > 16)
introsort_loop(data, p, pivot_loc - 1, limit);
if (pivot_loc - r - 1 > 16)
introsort_loop(data, pivot_loc + 1, r, limit);
}
int tmedian(t_list **data, int e1, int e2, int e3)
{
if (FAST_STRCMP(data[e1]->keyword, data[e2]->keyword) < 0)
{
if (FAST_STRCMP(data[e2]->keyword, data[e3]->keyword) < 0)
return (e2);
else
{
return ((FAST_STRCMP(data[e1]->keyword, data[e3]->keyword) < 0)
? e3 : e1);
}
}
else
{
if (FAST_STRCMP(data[e2]->keyword, data[e3]->keyword) < 0)
{
return ((FAST_STRCMP(data[e1]->keyword, data[e3]->keyword) < 0)
? e1 : e3);
}
else
return (e2);
}
}
int partition(t_list **data, int p, int r, int pivot)
{
char *x;
int i;
i = p;
x = ft_strdup(data[pivot]->keyword);
ft_swap(*(data + r), *(data + pivot));
while (p <= r)
{
if (FAST_STRCMP(data[p]->keyword, x) <= 0)
ft_swap(*(data + (i++)), *(data + p));
p++;
}
return (i - 1);
}
void ft_swap(t_list *e1, t_list *e2)
{
t_list *swap;
swap = e1;
e1 = e2;
e2 = swap;
}
Raw
search.c
/* ************************************************************************** */
/* */
/* ::: :::::::: */
/* search.c :+: :+: :+: */
/* +:+ +:+ +:+ */
/* By: thoraffr <[email protected]> +#+ +:+ +#+ */
/* +#+#+#+#+#+ +#+ */
/* Created: 2013/12/14 23:48:07 by thoraffr #+# #+# */
/* Updated: 2013/12/15 16:19:27 by ksicart ### ########.fr */
/* */
/* ************************************************************************** */
#include "hotrace.h"
#include <stdio.h>
void ft_put_error(char *s)
{
ft_putstr(s);
ft_putendl(": Not found.");
}
void ft_search(int nb_link, t_list **tab, char *key, long int min)
{
long int index;
long int maj;
maj = nb_link - 1;
while (1)
{
if (FAST_STRCMP(tab[index = maj]->keyword, key) == 0)
break ;
else if (FAST_STRCMP(tab[index = min]->keyword, key) == 0)
break ;
index = (maj + min) / 2;
if (FAST_STRCMP(tab[index]->keyword, key) < 0 && maj > 0)
maj = index - 1;
else if (FAST_STRCMP(tab[index]->keyword, key) > 0 && min < nb_link - 1)
min = index + 1;
if ((FAST_STRCMP(tab[index]->keyword, key) == 0)
|| (min >= maj))
break ;
}
if (FAST_STRCMP(tab[index]->keyword, key) == 0)
ft_putendl(tab[index]->data);
else
ft_put_error(key);
}
void ft_display(int nb_link, t_list **tab)
{
char *keyword;
while (gnl(0, (char **)(&keyword)) != 0)
{
ft_search(nb_link, tab, keyword, 0);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment