radix_sort2.cpp File Reference

Algorithm of Radix sort More...

#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iostream>
#include <vector>

Include dependency graph for radix_sort2.cpp:

Go to the source code of this file.

Namespaces
namespace	sorting
	for working with vectors
namespace	radix_sort
	Functions for Radix sort algorithm.

Functions
std::vector< uint64_t >	sorting::radix_sort::step_ith (uint16_t cur_digit, const std::vector< uint64_t > &ar)
	Function to sort vector according to current digit using stable sorting.
std::vector< uint64_t >	sorting::radix_sort::radix (const std::vector< uint64_t > &ar)
	Function to sort vector digit by digit.
static void	tests ()
	Function to test the above algorithm.
int	main ()
	Main function.

Detailed Description

Algorithm of Radix sort

Author

Suyash Jaiswal

Sort the vector of unsigned integers using radix sort i.e. sorting digit by digit using Counting Sort as subroutine. Running time of radix sort is O(d*(n+b)) where b is the base for representing numbers and d in the max digits in input integers and n is number of unsigned integers. consider example for n = 5, aray elements = 432,234,143,332,123 sorting digit by digit sorting according to 1) 1st digit place => 432, 332, 143, 123, 234

2) 2nd digit place => 123, 432, 332, 234, 143

3) 3rd digit place => 123, 143, 234, 332, 432

using count sort at each step, which is stable. stable => already sorted according to previous digits.

Definition in file radix_sort2.cpp.

Function Documentation

main()

int main

(

void

)

Main function.

Returns

0 on exit

Definition at line 119 of file radix_sort2.cpp.

           {
    tests();  // execute the tests
    return 0;
}

radix()

std::vector< uint64_t > sorting::radix_sort::radix

(

const std::vector< uint64_t > &

ar

)

Function to sort vector digit by digit.

Parameters

ar	- vector to be sorted

Returns

sorted vector

Definition at line 82 of file radix_sort2.cpp.

                                                         {
    uint64_t max_ele =
        *max_element(ar.begin(), ar.end());  // returns the max element.
    std::vector<uint64_t> temp = ar;
    for (int i = 1; max_ele / i > 0;
         i *= 10) {  // loop breaks when i > max_ele because no further digits
                     // left to makes changes in aray.
        temp = step_ith(i, temp);
    }
    for (uint64_t i : temp) {
        std::cout << i << " ";
    }
    std::cout << "\n";
    return temp;
}

step_ith()

std::vector< uint64_t > sorting::radix_sort::step_ith	(	uint16_t	cur_digit,
		const std::vector< uint64_t > &	ar )

Function to sort vector according to current digit using stable sorting.

Parameters

cur_digit	- sort according to the cur_digit
ar	- vector to be sorted

Returns

std::vector sorted till ith digit

Definition at line 51 of file radix_sort2.cpp.

                                   {  // sorting according to current digit.
    int n = ar.size();
    std::vector<uint32_t> position(10, 0);
    for (int i = 0; i < n; ++i) {
        position[(ar[i] / cur_digit) %
                 10]++;  // counting frequency of 0-9 at cur_digit.
    }
    int cur = 0;
    for (int i = 0; i < 10; ++i) {
        int a = position[i];
        position[i] = cur;  // assingning starting position of 0-9.
        cur += a;
    }
    std::vector<uint64_t> temp(n);
    for (int i = 0; i < n; ++i) {
        temp[position[(ar[i] / cur_digit) % 10]] =
            ar[i];  // storing ar[i] in ar[i]'s cur_digit expected position of
                    // this step.
        position[(ar[i] / cur_digit) %
                 10]++;  // incrementing ar[i]'s cur_digit position by 1, as
                         // current place used by ar[i].
    }
    return temp;
}

tests()

void tests ( )

static

Function to test the above algorithm.

Returns

none

Test 1

Test 2

Definition at line 104 of file radix_sort2.cpp.

                    {
    std::vector<uint64_t> ar1 = {432, 234, 143, 332, 123};
    ar1 = sorting::radix_sort::radix(ar1);
    assert(std::is_sorted(ar1.begin(), ar1.end()));
    std::vector<uint64_t> ar2 = {213, 3214, 123, 111, 112, 142,
                                 133, 132,  32,  12,  113};
    ar2 = sorting::radix_sort::radix(ar2);
    assert(std::is_sorted(ar2.begin(), ar2.end()));
}