2
\$\begingroup\$

I seek critique on a sorting implementation for a dynamic array data-structure.

Design decisions

  • Uses the quicksort algorithm.
  • Uses an optimized XOR swap for swapping the elements. XOR swap doesn't need extra memory and is optimized to do the swapping in up to 512 bit chunks.
  • Takes the comparison method as a function pointer.

Request input regarding

  • What to comapre it to speedwise?
  • Should I implement several other sorting strategies depending on the size of the input? What methods could be better for different sizes?
  • Any bugs?

Test script

This bash script creates a folder test_arr_sort in the home folder, clones the relevant library, makes the library, compiles the test and runs the tests. Includes a simple test for correctness and then a several speed tests against library qsort. All relevant tests will be downloaded and compiled by the script.

#!/bin/bash

mkdir ~/test_arr_sort
cd ~/test_arr_sort
git clone https://github.com/juliuskoskela/core.git
(cd core && make > /dev/null)
curl -OL https://gist.githubusercontent.com/juliuskoskela/cd1703a1e655fcd87503f3bac83fb2f5/raw/ddbf11af3dd64563f1c782d6f35c6898396d063e/test_arr_sort.c
gcc test_arr_sort.c core/libcore.a -o test

curl -OL https://gist.githubusercontent.com/juliuskoskela/70af0da405bc052b74535db432639e53/raw/dea293219f155bffe2fb607325ccc3abc106eae9/libc_qsort_speed.c

gcc -O3 libc_qsort_speed.c core/libcore.a -o qsort

curl -OL https://gist.githubusercontent.com/juliuskoskela/2ba865f6ecbd2a9415efbf4b75f13679/raw/06c87227f2722ea27407ea26b06bcd14af83ddd2/arr_sort_speed.c

gcc -O3 arr_sort_speed.c core/libcore.a -o asort
printf "\n\nTEST 100 RANDOM VALUES\n\n"
./test 100

printf "\n\nTEST SPEED AGAINST QSORT\n\n"

./qsort 1000 1000
printf "\n"
./asort 1000 1000

printf "***\n"

./qsort 1000 10000
printf "\n"
./asort 1000 10000

printf "***\n"

./qsort 1000 100000
printf "\n"
./asort 1000 100000

printf "***\n"

./qsort 100 1000000
printf "\n"
./asort 100 1000000



Test results

Here are tests results for the above scripted tests on my machine:

LIBC QSORT
SIZE 1000
PERMS 1000
AVERAGE TIME 0.000044

CORE ARR_SORT
SIZE 1000
PERMS 1000
AVERAGE TIME 0.000157
***
LIBC QSORT
SIZE 10000
PERMS 1000
AVERAGE TIME 0.000391

CORE ARR_SORT
SIZE 10000
PERMS 1000
AVERAGE TIME 0.002183
***
LIBC QSORT
SIZE 100000
PERMS 1000
AVERAGE TIME 0.003993

CORE ARR_SORT
SIZE 100000
PERMS 1000
AVERAGE TIME 0.026747
***
LIBC QSORT
SIZE 1000000
PERMS 100
AVERAGE TIME 0.020018

CORE ARR_SORT
SIZE 1000000
PERMS 100
AVERAGE TIME 0.320182

Relevant links

Dynamic array implementation: https://github.com/juliuskoskela/core/tree/master/core_containers/array

XOR-swap implementation: https://github.com/juliuskoskela/core/blob/master/core_standard/memory/src/mswap.c

Code

Don't mind the t_* typedefs. They are equivalent to the stdint.h types, but are there because on certain restrictions in school assignments on using external libs.

Sorting


static void arr_sort_recurse(t_array *src,
    t_ssize low,
    t_ssize high,
    t_ssize (*f)(void *, void *))
{
    t_ssize pivot;
    t_ssize a;
    t_ssize b;

    if (low >= high)
        return ;
    pivot = low;
    a = low;
    b = high;
    while (a < b)
    {
        while (a <= high && f(arr_get(src, a), arr_get(src, pivot)) <= 0)
            a++;
        while (b >= low && f(arr_get(src, b), arr_get(src, pivot)) > 0)
            b--;
        if (a < b)
            mswap(arr_get(src, a), arr_get(src, b), src->elem_size);
    }
    mswap(arr_get(src, pivot), arr_get(src, b), src->elem_size);
    arr_sort_recurse(src, low, b - 1, f);
    arr_sort_recurse(src, b + 1, high, f);
}

void    arr_sort(t_array *src, t_ssize (*f)(void *, void *))
{
    arr_sort_recurse(src, 0, src->len - 1, f);
}

Test main

Requires Core-library: https://github.com/juliuskoskela/core


#include "core/inc/core.h"
#include <time.h>

t_ssize CMP(void *a, void *b)
{
    int *ai;
    int *bi;

    ai = a;
    bi = b;
    if (*ai <= *bi)
        return (0);
    return (1);
}

t_ssize PRINT(void *data, t_size i)
{
    int *ptr = data;
    print("%d ", *ptr);
    return (i);
}

static void shuffle(t_array *arr, int n)
{
    t_int64 i;
    t_int64 j;
    t_int64 *s;
    t_int64 *t;

    if (n < 1)
        return ;
    srand(time(NULL));
    i = 0;
    while (i < n - 1)
    {
        j = i + rand() / (RAND_MAX / (n - i) + 1);
        s = arr_get(arr, i);
        t = arr_get(arr, j);
        mswap(s, t, sizeof(t_int64));
        i++;
    }
}

t_array generate(int size)
{
    t_array out;
    t_size  i;

    out = arr_new(size, sizeof(t_int64));
    i = 0;
    while (i < size)
    {
        arr_add_last(&out, &i);
        i++;
    }
    shuffle(&out, size);
    return (out);
}

int main(int argc, char **argv)
{
    t_array a1;
    
    a1 = generate(s_toi(argv[1]));
    arr_iter(&a1, PRINT);
    print("\nlist size = %d\n", a1.len);
    arr_sort(&a1, CMP);
    arr_iter(&a1, PRINT);
}

\$\endgroup\$
8
  • \$\begingroup\$ Unable to compile and test without 3rd party sites. \$\endgroup\$ Jun 14 at 18:26
  • \$\begingroup\$ There's quite a lot of complexity in the array implementation to put in the post, but I added a bash script to automate the whole process of running a simple test in the post. \$\endgroup\$
    – jkoskela
    Jun 14 at 19:17
  • \$\begingroup\$ Have you somehow misspelt ssize_t and int64_t throughout? \$\endgroup\$ Jun 14 at 20:05
  • \$\begingroup\$ No. The library provides the typedefs. It has to do with school restrictions on using certain external libraries. \$\endgroup\$
    – jkoskela
    Jun 14 at 20:08
  • \$\begingroup\$ Added speed tests to the tests script and results in the post. \$\endgroup\$
    – jkoskela
    Jun 14 at 21:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.