StackStalk
  • Home
  • Java
    • Java Collection
    • Spring Boot Collection
  • Python
    • Python Collection
  • C++
    • C++ Collection
    • Progamming Problems
    • Algorithms
    • Data Structures
    • Design Patterns
  • General
    • Tips and Tricks

Thursday, February 28, 2013

C++ Radix Sort

 February 28, 2013     Algorithms     No comments   

Radix sort is a non-comparative sorting algorithm. Radix sort works by looking at the individual digits which share the same position and value. This article explains the radix sort with an implementation in C++.

Radix sort Introduction

Radix sort orders the contents position by position. For ease of understanding here we restrict for numbers, but it should work with floats, strings, etc. It is a non-comparitive sort unlike many others which need comparison. The idea is: position by position, either starting from LSB or MSB, group the numbers into buckets. When you move to next position again re-order them for that position, while keeping the order of the previous position re-orders. Once all the positions are done, the whole list should be ordered. See, below example output on how the numbers get re-ordered at each pass of position ordering.
  1. Worst case performance is O(kN), k is count of decimal places and N is the input size. Note that we don't take out k.
  2. In the below example implementation, for re-order of the numbers for each decimal places, instead of doing lots of swaps, we have taken a simple approach. We do two level counting, first occurrence of numbers for each of the possibilities (0, 1,2 ..9) and then second we use that information to find the appropriate positions for placing all the numbers. A temporary buffer is used to place first and then we copy back to original buffer for next level processing.

Implementation for Radix sort

#include <iostream>

using namespace std;

void print(int *input, int n)
{
 for (int i = 0; i < n; i++)
      cout << input[i] << "\t";
}

void radixsort(int *input, int n)
{
  int i;

  // find the max number in the given list.
  // to be used in loop termination part.
  int maxNumber = input[0];
  for (i = 1; i < n; i++)
  {
    if (input[i] > maxNumber)
      maxNumber = input[i];
  }

  // run the loop for each of the decimal places
  int exp = 1;
  int *tmpBuffer = new int[n];
  while (maxNumber / exp > 0)
  {
    int decimalBucket[10] = {  0 };
    // count the occurences in this decimal digit.
    for (i = 0; i < n; i++)
      decimalBucket[input[i] / exp % 10]++;

    // Prepare the position counters to be used for re-ordering the numbers
    // for this decimal place.
    for (i = 1; i < 10; i++)
      decimalBucket[i] += decimalBucket[i - 1];

    // Re order the numbers in the tmpbuffer and later copy back to original buffer.
    for (i = n - 1; i >= 0; i--)
      tmpBuffer[--decimalBucket[input[i] / exp % 10]] = input[i];
    for (i = 0; i < n; i++)
      input[i] = tmpBuffer[i];

    // Move to next decimal place.
    exp *= 10;

    cout << "PASS   : ";
    print(input, n);
  }
}

const int INPUT_SIZE = 10;

int main()
{
  int input[INPUT_SIZE] = {143, 123, 222, 186, 235, 9, 905, 428, 543, 373};
  cout << "Input: ";
  print(input, INPUT_SIZE);
  radixsort(input,INPUT_SIZE);
  cout << "
Output: ";
  print(input, INPUT_SIZE);
  cout << "
";
  return 0;
}
Output:-
Input: 143      123     222     186     235     9       905     428     543     373 
PASS   : 222    143     123     543     373     235     905     186     428     9   
PASS   : 905    9       222     123     428     235     143     543     373     186 
PASS   : 9      123     143     186     222     235     373     428     543     905 
Output: 9       123     143     186     222     235     373     428     543     905 
  • Share This:  
Newer Post Older Post Home

0 comments:

Post a Comment

Follow @StackStalk
Get new posts by email:
Powered by follow.it

Popular Posts

  • Avro Producer and Consumer with Python using Confluent Kafka
    In this article, we will understand Avro a popular data serialization format in streaming data applications and develop a simple Avro Produc...
  • Monitor Spring Boot App with Micrometer and Prometheus
    Modern distributed applications typically have multiple microservices working together. Ability to monitor and manage aspects like health, m...
  • Server-Sent Events with Spring WebFlux
    In this article we will review the concepts of server-sent events and work on an example using WebFlux. Before getting into this article it ...
  • Implement caching in a Spring Boot microservice using Redis
    In this article we will explore how to use Redis as a data cache for a Spring Boot microservice using PostgreSQL as the database. Idea is to...
  • Python FastAPI microservice with Okta and OPA
    Authentication (AuthN) and Authorization (AuthZ) is a common challenge when developing microservices. In this article, we will explore how t...
  • Spring Boot with Okta and OPA
    Authentication (AuthN) and Authorization (AuthZ) is a common challenge when developing microservices. In this article, we will explore how t...
  • Getting started with Kafka in Python
    This article will provide an overview of Kafka and how to get started with Kafka in Python with a simple example. What is Kafka? ...
  • Getting started in GraphQL with Spring Boot
    In this article we will explore basic concepts on GraphQL and look at how to develop a microservice in Spring Boot with GraphQL support. ...

Copyright © StackStalk