forked from 131/lab4_sort
185 lines
3.6 KiB
Plaintext
185 lines
3.6 KiB
Plaintext
#include <assert.h>
|
||
#include <stdio.h>
|
||
#include <stdlib.h>
|
||
#include <string.h>
|
||
|
||
#include "vector.h"
|
||
#include "util.h"
|
||
|
||
#define VECTOR_START_SIZE 8
|
||
#define VECTOR_GROW_FACTOR 2
|
||
#define ITEMSZ sizeof(int)
|
||
|
||
void
|
||
vector_init(ivector *v)
|
||
{
|
||
assert(v);
|
||
|
||
v->n = 0;
|
||
v->maxsz = VECTOR_START_SIZE;
|
||
v->data = xmalloc(ITEMSZ * VECTOR_START_SIZE);
|
||
}
|
||
|
||
void
|
||
vector_initdata(ivector *v, int *arr, size_t arrsz)
|
||
{
|
||
assert(v && arrsz);
|
||
|
||
v->n = arrsz;
|
||
v->maxsz = (arrsz > VECTOR_START_SIZE) ? arrsz : VECTOR_START_SIZE;
|
||
v->data = xmalloc(ITEMSZ * v->maxsz);
|
||
memcpy(v->data, arr, ITEMSZ * arrsz);
|
||
}
|
||
|
||
void
|
||
vector_free(ivector *v)
|
||
{
|
||
assert(v);
|
||
|
||
v->n = 0;
|
||
v->maxsz = 0;
|
||
xfree(v->data);
|
||
v->data = NULL;
|
||
}
|
||
|
||
size_t
|
||
vector_len(const ivector *v)
|
||
{
|
||
assert(v);
|
||
|
||
return v->n;
|
||
}
|
||
|
||
int *
|
||
vector_data(const ivector *v)
|
||
{
|
||
assert(v);
|
||
return v->data;
|
||
}
|
||
|
||
void
|
||
vector_resize(ivector *v, int n)
|
||
{
|
||
assert(v);
|
||
|
||
if (n < 0) return;
|
||
|
||
if ((size_t)n > v->maxsz) {
|
||
size_t new_maxsz = v->maxsz;
|
||
while (new_maxsz < (size_t)n) {
|
||
new_maxsz *= VECTOR_GROW_FACTOR;
|
||
}
|
||
v->data = xrealloc(v->data, ITEMSZ * new_maxsz);
|
||
v->maxsz = new_maxsz;
|
||
}
|
||
v->n = n;
|
||
}
|
||
|
||
void
|
||
vector_set(ivector *v, size_t idx, int val)
|
||
{
|
||
assert(v && idx < v->n);
|
||
v->data[idx] = val;
|
||
}
|
||
|
||
int
|
||
vector_get(const ivector *v, size_t idx)
|
||
{
|
||
assert(v && idx < v->n);
|
||
return v->data[idx];
|
||
}
|
||
|
||
void
|
||
vector_push(ivector *v, int val)
|
||
{
|
||
assert(v);
|
||
|
||
if (v->n == v->maxsz) {
|
||
vector_resize(v, v->n + 1);
|
||
} else {
|
||
v->n++;
|
||
}
|
||
v->data[v->n - 1] = val;
|
||
}
|
||
|
||
void
|
||
vector_pop(ivector *v)
|
||
{
|
||
assert(v && v->n > 0);
|
||
v->n--;
|
||
}
|
||
|
||
void
|
||
vector_insert(ivector *v, size_t idx, int val)
|
||
{
|
||
assert(v && v->n >= idx);
|
||
|
||
if (v->n == v->maxsz) {
|
||
vector_resize(v, v->n + 1);
|
||
} else {
|
||
v->n++;
|
||
}
|
||
|
||
// Сдвигаем элементы вправо, начиная с idx
|
||
for (size_t i = v->n - 1; i > idx; i--) {
|
||
v->data[i] = v->data[i - 1];
|
||
}
|
||
v->data[idx] = val;
|
||
}
|
||
|
||
void
|
||
vector_del(ivector *v, size_t idx)
|
||
{
|
||
assert(v && idx < v->n);
|
||
|
||
// Сдвигаем элементы влево, начиная с idx+1
|
||
for (size_t i = idx; i < v->n - 1; i++) {
|
||
v->data[i] = v->data[i + 1];
|
||
}
|
||
v->n--;
|
||
}
|
||
|
||
void
|
||
vector_clear(ivector *v)
|
||
{
|
||
vector_resize(v, 0);
|
||
}
|
||
}
|
||
}
|
||
}
|
||
}
|
||
}
|
||
}
|
||
}
|
||
}
|
||
}
|
||
}
|
||
}
|
||
}
|
||
}
|
||
}
|
||
}
|
||
}
|
||
}
|
||
}
|
||
}
|
||
}
|
||
}
|
||
----------
|
||
|
||
Задачи:
|
||
|
||
* Форкнуть и Склонить git-репозиторий https://timplab.syktsu.ru/131/lab4_sort.git
|
||
|
||
Весь нужный код находится в файле sort.c
|
||
Функция main вызвает функцию test_all, которая тестирует различные реализации
|
||
алгоритмов сортировки.
|
||
|
||
* Написать сортировку вставками (постараться не подглядывать в интернеты и не пользоваться чатботами!)
|
||
реализовав функцию insert_sort
|
||
|
||
* разобраться в работе функции merge_sort, которая
|
||
сортирует массив методом слияния.
|
||
|
||
* Написать реализацию функции _merge для совмещения двух кусочков массива в один
|