91 lines
1.7 KiB
C
91 lines
1.7 KiB
C
#include <stdlib.h>
|
|
#include "array.h"
|
|
|
|
void IntArray_new(IntArray* a, size_t size) {
|
|
a->arr = malloc(size * sizeof(int));
|
|
a->used = 0;
|
|
a->size = size;
|
|
}
|
|
|
|
int IntArray_append(IntArray* a, int el) {
|
|
if (a->used == a->size) {
|
|
a->size *= 2;
|
|
a->arr = realloc(a->arr, a->size * sizeof(int));
|
|
}
|
|
|
|
a->used++;
|
|
|
|
a->arr[a->used] = el;
|
|
return a->used;
|
|
}
|
|
|
|
int IntArray_get(IntArray* a, int idx, int dflt) {
|
|
if (idx > a->used) {
|
|
return dflt;
|
|
}
|
|
|
|
return a->arr[idx];
|
|
}
|
|
|
|
int IntArray_length(IntArray* a) {
|
|
return a->used;
|
|
}
|
|
|
|
void IntArray_mergesort(IntArray* a) {
|
|
IntArray left_side;
|
|
IntArray right_side;
|
|
|
|
size_t split = a->used / 2;
|
|
|
|
IntArray_new(&left_side, split);
|
|
IntArray_new(&right_side, split);
|
|
|
|
for (int i = 0; i < split; ++i) {
|
|
IntArray_append(&left_side, IntArray_get(a, i, 0));
|
|
}
|
|
|
|
for (int i = split; i < a->used; ++i) {
|
|
IntArray_append(&right_side, IntArray_get(a, i, 0));
|
|
}
|
|
|
|
IntArray_mergesort(&left_side);
|
|
IntArray_mergesort(&right_side);
|
|
|
|
IntArray_mergesort_merge(a, &left_side, &right_side);
|
|
}
|
|
|
|
void IntArray_mergesort_merge(IntArray* a, IntArray* left_side, IntArray* right_side) {
|
|
IntArray_free(a);
|
|
|
|
size_t i = 0;
|
|
size_t j = 0;
|
|
|
|
while (i < left_side->used && j < right_side->used) {
|
|
if (left_side->arr[i] <= right_side->arr[j]) {
|
|
IntArray_append(a, left_side->arr[i]);
|
|
i++;
|
|
} else {
|
|
IntArray_append(a, right_side->arr[j]);
|
|
j++;
|
|
}
|
|
}
|
|
|
|
for (size_t li = 0; li < left_side->used; ++li) {
|
|
IntArray_append(a, left_side->arr[li]);
|
|
}
|
|
|
|
for (size_t ri = 0; ri < right_side->used; ++ri) {
|
|
IntArray_append(a, right_side->arr[ri]);
|
|
}
|
|
}
|
|
|
|
void IntArray_quicksort(IntArray* a) {
|
|
return;
|
|
}
|
|
|
|
void IntArray_free(IntArray* a) {
|
|
free(a->arr);
|
|
a->arr = NULL;
|
|
a->used = a->size = 0;
|
|
}
|