Algorithms_in_C++ 1.0.0
Set of algorithms implemented in C++.
Loading...
Searching...
No Matches
radix_sort2.cpp File Reference

Algorithm of Radix sort More...

#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>
Include dependency graph for radix_sort2.cpp:

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.

Function Documentation

◆ main()

int main ( void )

Main function.

Returns
0 on exit
117 {
118 tests(); // execute the tests
119 return 0;
120}
static void tests()
Function to test the above algorithm.
Definition radix_sort2.cpp:102
Here is the call graph for this function:

◆ 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
80 {
81 uint64_t max_ele =
82 *max_element(ar.begin(), ar.end()); // returns the max element.
83 std::vector<uint64_t> temp = ar;
84 for (int i = 1; max_ele / i > 0;
85 i *= 10) { // loop breaks when i > max_ele because no further digits
86 // left to makes changes in aray.
87 temp = step_ith(i, temp);
88 }
89 for (uint64_t i : temp) {
90 std::cout << i << " ";
91 }
92 std::cout << "\n";
93 return temp;
94}
T begin(T... args)
T end(T... args)
T max_element(T... args)
std::vector< uint64_t > step_ith(uint16_t cur_digit, const std::vector< uint64_t > &ar)
Function to sort vector according to current digit using stable sorting.
Definition radix_sort2.cpp:49
Here is the call graph for this function:

◆ 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
51 { // sorting according to current digit.
52 int n = ar.size();
53 std::vector<uint32_t> position(10, 0);
54 for (int i = 0; i < n; ++i) {
55 position[(ar[i] / cur_digit) %
56 10]++; // counting frequency of 0-9 at cur_digit.
57 }
58 int cur = 0;
59 for (int i = 0; i < 10; ++i) {
60 int a = position[i];
61 position[i] = cur; // assingning starting position of 0-9.
62 cur += a;
63 }
65 for (int i = 0; i < n; ++i) {
66 temp[position[(ar[i] / cur_digit) % 10]] =
67 ar[i]; // storing ar[i] in ar[i]'s cur_digit expected position of
68 // this step.
69 position[(ar[i] / cur_digit) %
70 10]++; // incrementing ar[i]'s cur_digit position by 1, as
71 // current place used by ar[i].
72 }
73 return temp;
74}
T size(T... args)
Here is the call graph for this function:

◆ tests()

static void tests ( )
static

Function to test the above algorithm.

Returns
none

Test 1

Test 2

102 {
103 /// Test 1
104 std::vector<uint64_t> ar1 = {432, 234, 143, 332, 123};
106 assert(std::is_sorted(ar1.begin(), ar1.end()));
107 /// Test 2
108 std::vector<uint64_t> ar2 = {213, 3214, 123, 111, 112, 142,
109 133, 132, 32, 12, 113};
111 assert(std::is_sorted(ar2.begin(), ar2.end()));
112}
T is_sorted(T... args)
std::vector< uint64_t > radix(const std::vector< uint64_t > &ar)
Function to sort vector digit by digit.
Definition radix_sort2.cpp:80
Here is the call graph for this function: