1
\$\begingroup\$

Memory:O(log(max)base(mod)*mod)
Speed:O(log(max)base(mod)*n)

I did a radix sort in place to not get a auxliar array. In the process i discorver a few things.

  • Is imposible to do LSD radix sort in place with out sacrifice speed, belive me if i say i try. THIS WILL BE NOT EXPLAING

  • counting sort, you can do it for in place(with O(n) and object/pointer oriented), BUT is UNSTABLE. this will be explain here.

  • mod (num%mod) use idiv/div if the value(mod) is not determined in compilation time.

​​Memory

The algorim use O(( N~excess(log(max)base(mod)) +2)*mod)

this is the part of the code:

        size_t max = get_max(arr, size);
        const size_t num_count = logb_pow2(max, mod_pow2);

        size_t* count_control = new size_t[1 << mod_pow2];
        for (size_t i = 0; i < 1 << mod_pow2; i++)
            count_control[i] = 0;
        //------------------
        size_t** counts = new size_t * [num_count];
        for (size_t i = 0; i < num_count; i++) {
            counts[i] = new size_t[1 << mod_pow2];
        }

Algorithm

I will explain this with points so is more easy for me:

  • As you see up there we are using count_control i use this for 2 resons:

    1. So we can do sort with out modify counts, because we will use this as pointers
    2. will be no aditional caculations.

  • the algorithm is recursive, like a quick sort, using counts as pivots

  • the i am using UNSTABLE sort and i will explain how with a table:

text
(source: i.ibb.co)

Code

  • I made custom get_max and log base 2, so i can forget adding more libs.

  • also i made a custom mod so one can chose, how large is memory in use, base on previous calculations. With out the compiler use idiv or div intruccions.

  • also i made a object oriented and pointer object oriented code.

the code

#pragma once
namespace leixor {
    //we write the mod pow 2 to avoid idv instruccion of the compiler
    static constexpr size_t modpow2(size_t& num, size_t& mod_pow2) {
        return num - (num >> mod_pow2 << mod_pow2);
    }
    static constexpr size_t modpow2(size_t& num, size_t mod_pow2) {
        return num - (num >> mod_pow2 << mod_pow2);
    }
    static constexpr size_t modpow2(size_t num, size_t mod_pow2) {
        return num - (num >> mod_pow2 << mod_pow2);
    }
    //fast log in power of 2
    static size_t& logb_pow2(size_t num, const size_t& base_pow2) {
        size_t aux = 1;
        if (base_pow2 == 0) return aux = -1;
        while (0 < (num >>= base_pow2))
            aux++;
        return aux;
    }
    //------------------------obj version---------------------------
    //custom get_max because i don't wanna add lib,and normaly we will use this in a custom class
    template<class obj_arr>
    static size_t& get_max(obj_arr*& arr, const size_t& size) {

        size_t i = modpow2(size, 1), aux = arr[0].get_size_t(), aux2;
        for (; i < size; i += 2) {
            aux2 = arr[i].get_size_t();
            aux = aux2 * (aux < aux2) + aux * (aux >= aux2);
            aux2 = arr[i + 1].get_size_t();
            aux = aux2 * (aux < aux2) + aux * (aux >= aux2);
        }
        return aux;
    }


    
    template<class obj_arr>
    void countrad(
        size_t depth,
        obj_arr*& arr,
        size_t*& count_control, size_t**& counts, size_t& mod_pow2,
        size_t start, size_t finish
    ) {
        size_t i;
        static size_t move;
        static obj_arr auxiliar;
        depth--;
        for (i = start; i < finish; i++) {
            count_control[modpow2(arr[i].get_size_t() >> (depth * mod_pow2), mod_pow2)]++;
        }
        counts[depth][0] = start;
        for (i = 1; i < 1 << mod_pow2; i++) {
            counts[depth][i] = counts[depth][i - 1] + count_control[i - 1];
        }

        for (i = 0; i < 1 << mod_pow2; i++) {
            while (count_control[i] > 0) {
                auxiliar = arr[counts[depth][i] + count_control[i] - 1];
                move = modpow2(auxiliar.get_size_t() >> (depth * mod_pow2), mod_pow2);
                arr[counts[depth][i] + count_control[i] - 1] = arr[counts[depth][move] + count_control[move] - 1];
                arr[counts[depth][move] + count_control[move] - 1] = auxiliar;
                count_control[move]--;
            }
        }

        if (depth > 0) {
            start = counts[depth][(1 << mod_pow2) - 1];
            countrad(depth, arr, count_control, counts, mod_pow2, start, finish);
            for (i = 0; i < (1 << mod_pow2) - 1; i++) {
                start = counts[depth][i];
                finish = counts[depth][i + 1];
                countrad(depth, arr, count_control, counts, mod_pow2, start, finish);
            }
        }

    }

    template<class obj_arr>
    bool radix_sort_ftl(obj_arr* arr, size_t size, size_t mod_pow2 = 4) {
        if (mod_pow2 == 0 || size < 2)
            return false;
        size_t max = get_max(arr, size), start = 0, finish = size;
        const size_t num_count = logb_pow2(max, mod_pow2);
        //we use count_control so we don't need a axiliar memory the same size as arr
        size_t* count_control = new size_t[1 << mod_pow2];
        for (size_t i = 0; i < 1 << mod_pow2; i++)
            count_control[i] = 0;
        //------------------
        size_t** counts = new size_t * [num_count];
        for (size_t i = 0; i < num_count; i++) {
            counts[i] = new size_t[1 << mod_pow2];
        }

        countrad(num_count, arr, count_control, counts, mod_pow2, start, finish);

        delete[] count_control;

        for (size_t i = 0; i < num_count; i++)
            delete[] counts[i];
        delete[]counts;

        return true;
    }
    //----------------------------pointer obj version---------------------
    template<class obj_arr>
    static size_t& get_max(obj_arr**& arr, const size_t& size) {

        size_t i = modpow2(size, 1), aux = arr[0]->get_size_t(), aux2;
        for (; i < size; i += 2) {
            aux2 = arr[i]->get_size_t();
            aux = aux2 * (aux < aux2) + aux * (aux >= aux2);
            aux2 = arr[i + 1]->get_size_t();
            aux = aux2 * (aux < aux2) + aux * (aux >= aux2);
        }
        return aux;
    }



    template<class obj_arr>
    void countrad(
        size_t depth,
        obj_arr**& arr,
        size_t*& count_control, size_t**& counts, size_t& mod_pow2,
        size_t start, size_t finish
    ) {
        size_t i;
        static size_t move;
        static obj_arr* auxiliar;
        depth--;
        for (i = start; i < finish; i++) {
            count_control[modpow2(arr[i]->get_size_t() >> (depth * mod_pow2), mod_pow2)]++;
        }
        counts[depth][0] = start;
        for (i = 1; i < 1 << mod_pow2; i++) {
            counts[depth][i] = counts[depth][i - 1] + count_control[i - 1];
        }

        for (i = 0; i < 1 << mod_pow2; i++) {
            while (count_control[i] > 0) {
                auxiliar = arr[counts[depth][i] + count_control[i] - 1];
                move = modpow2(auxiliar->get_size_t() >> (depth * mod_pow2), mod_pow2);
                arr[counts[depth][i] + count_control[i] - 1] = arr[counts[depth][move] + count_control[move] - 1];
                arr[counts[depth][move] + count_control[move] - 1] = auxiliar;
                count_control[move]--;
            }
        }

        if (depth > 0) {
            start = counts[depth][(1 << mod_pow2) - 1];
            countrad(depth, arr, count_control, counts, mod_pow2, start, finish);
            for (i = 0; i < (1 << mod_pow2) - 1; i++) {
                start = counts[depth][i];
                finish = counts[depth][i + 1];
                countrad(depth, arr, count_control, counts, mod_pow2, start, finish);
            }
        }

    }

    template<class obj_arr>
    bool radix_sort_ftl(obj_arr** arr, size_t size, size_t mod_pow2 = 4) {
        if (mod_pow2 == 0 || size < 2)
            return false;
        size_t max = get_max(arr, size), start = 0, finish = size;
        const size_t num_count = logb_pow2(max, mod_pow2);
        //we use count_control so we don't need a axiliar memory the same size as arr
        size_t* count_control = new size_t[1 << mod_pow2];
        for (size_t i = 0; i < 1 << mod_pow2; i++)
            count_control[i] = 0;
        //------------------
        size_t** counts = new size_t * [num_count];
        for (size_t i = 0; i < num_count; i++) {
            counts[i] = new size_t[1 << mod_pow2];
        }

        countrad(num_count, arr, count_control, counts, mod_pow2, start, finish);

        delete[] count_control;

        for (size_t i = 0; i < num_count; i++)
            delete[] counts[i];
        delete[]counts;

        return true;
    }

}

Run Times

the time of the runtime is O(log(max)base(mod)*n)

the tables are in milliseconds

BTW, my cpu is from 2014, and i got very limited ram so yeah

/*

      --------------------------------------------------
      ----------------object oriented version-----------
      --------------------------------------------------


      ------------------size mod of 4 ------------------
      ---------------------size pow 10------------------
      --------------------------------------------------
      |  1   | 2    |    3 |    4 |    5 |    6 |    7 |
      --------------------------------------------------
max|2 |0.0076|0.0236|0.2069|2.4733|26.9838|255.068|2309.22
      --------------------------------------------------
num|3 |0.0167|0.0419|0.3858|4.1228|44.7138|433.727|4314.11
      --------------------------------------------------
pow|4 |0.0101|0.0432|0.4358|4.5905|42.4533|429.153|4314.23
      --------------------------------------------------
   |5 |0.0143|0.0713|0.6083|6.1008|62.0323|630.773|6315.29
      --------------------------------------------------
2  |6 |0.0163|0.0621|0.6158|7.3441|62.1267|628.958|6304.4
      --------------------------------------------------

      ------------------size mod of 8 ------------------
      ---------------------size pow 10------------------
      --------------------------------------------------
      |  1   | 2    |    3 |    4 |    5 |    6 |    7 |
      --------------------------------------------------
max|2 |0.1094|0.0263|0.2302|2.1466|22.7497|228.865|2303.3
      --------------------------------------------------
num|3 |0.0093|0.0242|0.2205|2.2055|22.8613|226.658|2314.24
      --------------------------------------------------
pow|4 |0.0117|0.0447|0.5455|4.4147|43.9577|432.973|4406.73
      --------------------------------------------------
   |5 |0.0124|0.0445|0.4058|4.055|41.8984|430.084|4326.23
      --------------------------------------------------
2  |6 |0.0117|0.0433|0.4014|4.6221|42.2156|433.02|4341.24
      --------------------------------------------------

      ------------------size mod of 16 ------------------
      ---------------------size pow 10------------------
      --------------------------------------------------
      |  1   | 2    |    3 |    4 |    5 |    6 |    7 |
      --------------------------------------------------
max|2 |0.0191|0.0243|0.2243|2.1877|23.1079|230.527|2293.82
      --------------------------------------------------
num|3 |0.0093|0.0238|0.214|2.1241|22.3461|235.777|2295.13
      --------------------------------------------------
pow|4 |0.0086|0.0272|0.2134|2.224|23.807|228.782|2297.63
      --------------------------------------------------
   |5 |0.0145|0.0466|0.473|4.7459|43.1028|430.736|4299.26
      --------------------------------------------------
2  |6 |0.0215|0.0464|0.4031|4.2045|41.8412|429.463|4291.11
      --------------------------------------------------

      ------------------size mod of 32 ------------------
      ---------------------size pow 10------------------
      --------------------------------------------------
      |  1   | 2    |    3 |    4 |    5 |    6 |    7 |
      --------------------------------------------------
max|2 |0.0102|0.0281|0.2348|2.2269|23.0951|233.078|2282.3
      --------------------------------------------------
num|3 |0.0195|0.0281|0.2142|2.2431|22.5763|231.902|2284.49
      --------------------------------------------------
pow|4 |0.0134|0.0274|0.2268|2.2565|22.737|231.406|2293.99
      --------------------------------------------------
   |5 |0.0147|0.0282|0.343|2.1646|24.4202|236.879|2325.05
      --------------------------------------------------
2  |6 |0.0325|0.0547|0.4244|4.1533|43.6177|433.502|4326.64
      --------------------------------------------------

      --------------------------------------------------
      ----------------pointer oriented version-----------
      --------------------------------------------------


      ------------------size mod of 4 ------------------
      ---------------------size pow 10------------------
      --------------------------------------------------
      |  1   | 2    |    3 |    4 |    5 |    6 |    7 |
      --------------------------------------------------
max|2 |0.0056|0.0165|0.1427|1.507|17.7379|182.47|1823.31
      --------------------------------------------------
num|3 |0.0092|0.03|0.2664|2.832|32.4554|348.994|3535.21
      --------------------------------------------------
pow|4 |0.009|0.0288|0.2794|2.6144|35.1367|401.047|4058.5
      --------------------------------------------------
   |5 |0.012|0.0447|0.4567|3.8103|49.5403|607.592|6154.31
      --------------------------------------------------
2  |6 |0.0125|0.0424|0.3702|4.8526|51.0433|668.851|6713.33
      --------------------------------------------------

      ------------------size mod of 8 ------------------
      ---------------------size pow 10------------------
      --------------------------------------------------
      |  1   | 2    |    3 |    4 |    5 |    6 |    7 |
      --------------------------------------------------
max|2 |0.0066|0.0186|0.1465|1.5798|17.796|194.092|1815.05
      --------------------------------------------------
num|3 |0.017|0.0174|0.1431|1.5255|16.8148|181.812|1834.28
      --------------------------------------------------
pow|4 |0.0107|0.0289|0.2762|3.2135|36.3079|360.955|3615.19
      --------------------------------------------------
   |5 |0.01|0.0303|0.2602|2.8911|35.5301|412.652|4225.77
      --------------------------------------------------
2  |6 |0.019|0.0304|0.2881|3.3176|42.6521|459.499|4506.64
      --------------------------------------------------

      ------------------size mod of 16 ------------------
      ---------------------size pow 10------------------
      --------------------------------------------------
      |  1   | 2    |    3 |    4 |    5 |    6 |    7 |
      --------------------------------------------------
max|2 |0.0084|0.0174|0.1481|1.5799|17.17|179.65|1811.61
      --------------------------------------------------
num|3 |0.0106|0.0169|0.1484|1.498|18.9011|184.272|1828.91
      --------------------------------------------------
pow|4 |0.0094|0.0169|0.1459|1.5219|22.7538|206.602|2083.07
      --------------------------------------------------
   |5 |0.0132|0.0354|0.2809|2.8347|34.8864|395.352|3955.96
      --------------------------------------------------
2  |6 |0.0188|0.0334|0.2755|2.9177|33.8708|418.193|4198.72
      --------------------------------------------------

      ------------------size mod of 32 ------------------
      ---------------------size pow 10------------------
      --------------------------------------------------
      |  1   | 2    |    3 |    4 |    5 |    6 |    7 |
      --------------------------------------------------
max|2 |0.0084|0.0189|0.149|1.9447|18.7979|180.437|1806.58
      --------------------------------------------------
num|3 |0.0093|0.0166|0.5307|1.4293|19.0638|182.021|1846.18
      --------------------------------------------------
pow|4 |0.0124|0.0191|0.1559|1.4994|19.8116|210.089|2111.82
      --------------------------------------------------
   |5 |0.0092|0.0179|0.1669|1.5301|20.5126|231.144|2303.58
      --------------------------------------------------
2  |6 |0.0304|0.1304|0.3452|2.7494|36.1319|398.604|4132.56
      --------------------------------------------------


*/

The Runtime code

#include "radix_sort_ftl.h"
#include <stdlib.h>     /* srand, rand */
#include <time.h>   
#include <iostream>
#include <chrono>
#include<string>
#include <array>
#include <math.h>
class data
{
public:
    data() {};
    size_t& get_size_t() { return m; };
    void operator = (data& T) { m = T.m; };
    size_t m;
};
void object_version(const size_t pow10,const size_t pow2,const size_t mod_pow2) {
    size_t size = pow(10,pow10);
    data* arr = new data[size];
    size_t mod = 1 << (2+pow2);

    for (size_t i = 0; i < size; i++) {

        arr[i].m = rand() % mod;
    }


    auto started = std::chrono::high_resolution_clock::now();
    leixor::radix_sort_ftl(arr, size,mod_pow2);
    auto done = std::chrono::high_resolution_clock::now();

    std::cout<<"|" << float(std::chrono::duration_cast<std::chrono::nanoseconds>(done - started).count()) / float(1000000);

    delete[] arr;

};
void pointer_object_version(const size_t pow10, const size_t pow2, const size_t mod_pow2) {
    size_t size = pow(10, pow10);
    data** arr = new data*[size];
    size_t mod = 1 << (2 + pow2);

    for (size_t i = 0; i < size; i++) {
        arr[i] = new data();
        arr[i]->m = rand() % mod;
    }


    auto started = std::chrono::high_resolution_clock::now();
    leixor::radix_sort_ftl(arr, size, mod_pow2);
    auto done = std::chrono::high_resolution_clock::now();

    std::cout << "|" << float(std::chrono::duration_cast<std::chrono::nanoseconds>(done - started).count()) / float(1000000);

    for (size_t i = 0; i < size; i++) {
        delete arr[i];
    }

    delete[] arr;

};
int main() {
    srand(time(NULL));
    std::cout << 
        "\n      --------------------------------------------------"<<
        "\n      ----------------object oriented version-----------"<<
        "\n      --------------------------------------------------\n\n";
    std::array<std::string, 5> alfa = { "\nmax|2 ","\nnum|3 ","\npow|4 ","\n   |5 ","\n2  |6 " };
    for (size_t mod_pow2 = 2; mod_pow2 < 6; mod_pow2++){
        std::cout << 
            "\n      ------------------size mod of "<< size_t(1<<mod_pow2)<<" ------------------";
    
        std::cout <<
            "\n      ---------------------size pow 10------------------" <<
            "\n      --------------------------------------------------" <<
            "\n      |  1   | 2    |    3 |    4 |    5 |    6 |    7 |";

        for (size_t z = 0; z < 5; z++) {
            std::cout << "\n      --------------------------------------------------"<<
                alfa[z];

            for (size_t i = 1; i < 8; i++){
                object_version(i,z,mod_pow2);
            }
        }
        std::cout << "\n      --------------------------------------------------\n";
    }
    std::cout <<
        "\n      --------------------------------------------------" <<
        "\n      ----------------pointer oriented version-----------" <<
        "\n      --------------------------------------------------\n\n";
    for (size_t mod_pow2 = 2; mod_pow2 < 6; mod_pow2++) {
        std::cout <<
            "\n      ------------------size mod of " << size_t(1 << mod_pow2) << " ------------------";

        std::cout <<
            "\n      ---------------------size pow 10------------------" <<
            "\n      --------------------------------------------------" <<
            "\n      |  1   | 2    |    3 |    4 |    5 |    6 |    7 |";

        for (size_t z = 0; z < 5; z++) {
            std::cout << "\n      --------------------------------------------------" <<
                alfa[z];

            for (size_t i = 1; i < 8; i++) {
                pointer_object_version(i, z, mod_pow2);
            }
        }
        std::cout << "\n      --------------------------------------------------\n";
    }

}

So tell me, how does it look?

Improve this question
\$\endgroup\$
1
  • \$\begingroup\$ BTW, ftl is just faster than light, i just wanted to do some reference \$\endgroup\$
    – bigotes0invisibles
    Jan 31, 2021 at 20:30

1 Answer 1

Reset to default
1
\$\begingroup\$

Note: I wrote this answer in response to your other post, which was deleted just before I posted. However, it nearly all applies to this code too, so here it is:

size_t& logb2(size_t num)
static size_t& get_max(obj_arr*& arr, const size_t& size)
static size_t& get_max(obj_arr**& arr, const size_t& size)

bug: These all return references to local objects (i.e. undefined behavior that may crash the program or cause incorrect results).

static size_t& logb2(size_t num) {
    size_t aux = 1;
    while (0 < (num >>= 1))
        aux++;
    return aux;
}

Besides returning a reference to a local variable, this function is incorrect:

  • log2(1) is 0, but this function returns 1.
  • log2(2) is 1, but this function returns 2
  • log2(0) is an invalid operation, but this function returns 1, which seems rather dangerous. We should probably assert that num isn't zero.

In C++20, we can use std::bit_width(num) - 1 (after checking for zero input).

template<class obj_arr>
static size_t& get_max(obj_arr*& arr, const size_t& size) {

    size_t i = size%2, aux = arr[0].get_size_t(), aux2;
    for (; i < size; i += 2) {
        aux2 = arr[i].get_size_t();
        aux = aux2 * (aux < aux2) + aux * (aux >= aux2);
        aux2 = arr[i + 1].get_size_t();
        aux = aux2 * (aux < aux2) + aux * (aux >= aux2);
    }
    return aux;
}

What if the array size is zero?

If we have somehow ensured that the array size is not zero somewhere else, we should assert that in this function (and probably document it too).

I'd be surprised if the aux = aux2 * (aux < aux2) + aux * (aux >= aux2); hack is faster than simply: aux = (aux < aux2 ? aux2 : aux);, or if looping over two objects at a time is beneficial.

[note: code from the other deleted post, but most of the advice below applies to this one]

template<class obj_arr>
void two_rad(obj_arr*& arr, size_t start, size_t finish, size_t depth) {
    depth--;
    static size_t alfa, s, f, move, size;
    static bool mod_cal;
    static obj_arr auxiliar;
    size_t mid;
    size = (f = finish) - (s = start);
    for (alfa = 1; size > alfa; alfa++) {
        auxiliar = arr[s];
        mod_cal = (auxiliar.get_size_t() >> depth) % 2;
        move = (f -= mod_cal) * mod_cal + s * !mod_cal;
        arr[s] = arr[move];
        arr[move] = auxiliar;
        s += !mod_cal;
    }
    mid = s+!(arr[s].get_size_t() >> depth)%2;

    if (depth>0) {
        if (mid - start > 2)
            two_rad(arr, start, mid, depth);
        else if (mid - start > 1) {
            mod_cal=arr[start].get_size_t() > arr[start + 1].get_size_t();
            auxiliar = arr[start];
            arr[start] = arr[start + mod_cal];
            arr[start + mod_cal] = auxiliar;
        }
        if (finish - mid > 2)
            two_rad(arr, mid, finish, depth);
        else if (finish - mid > 1 ) {
            mod_cal = arr[mid].get_size_t() > arr[mid + 1].get_size_t();
            auxiliar = arr[mid];
            arr[mid] = arr[mid + mod_cal];
            arr[mid + mod_cal] = auxiliar;
        }
    }

}

There's no state here that we want to be static (i.e. persist between calls to this function).

We should use local variables, which should be declared one at a time as close to the point of use as possible. So no size = (f = finish) - (s = start);. alfa should be declared where it is set in the for loop. auxiliar, mod_cal, move should all be inside the for loop. mid should be declared where it is set after the for loop.

We should also not reuse variables when we don't need to. Especially for simple POD types, we can let the compiler worry about optimization.

Note that std::swap exists, so we can do for example: std::swap(arr[s], arr[move]), which is much clearer.

It's unnecessary to force people to use the data class, or implement a type with a size_t& get_size_t() { return m; };. We should also allow sorting types other than size_t.

We can do this by accepting a pointer range, e.g.:

template<class It>
bool quick_radix_sort(It begin, It end) {
    size_t size = (end - begin);
    ...
}
Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ thx, but for that i temporaly i delete the code because of a "last sort"; i am repairing the code; your recomendations will be add onn; \$\endgroup\$
    – bigotes0invisibles
    Feb 5, 2021 at 5:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.