Skip to main content

Radix sort example

Radix sort is a non-comparative sorting algorithm that sorts data by grouping it based on the individual digits that make up the elements. It is a linear time sorting algorithm that is particularly useful for sorting large quantities of data.

The algorithm works by first sorting the data based on the least significant digit, then the next least significant digit, and so on, until all the digits have been sorted. This is called a "stable sort" because the order of elements with equal keys is preserved.

Radix sort can be performed in two ways: least significant digit (LSD) radix sort and most significant digit (MSD) radix sort. LSD radix sort starts by sorting the least significant digit, while MSD radix sort starts by sorting the most significant digit. Both methods have their own advantages and disadvantages, and which one is used depends on the data being sorted and the specific requirements of the sorting task.

One of the main advantages of radix sort is that it is a stable sort and has a linear time complexity of O(nk), where n is the number of elements being sorted and k is the maximum number of digits in any element. This makes it faster than other sorting algorithms like quicksort or mergesort in certain cases, especially when the data being sorted has a relatively small number of digits.

However, radix sort has some limitations. It can only be used to sort data that can be represented as integers or fixed-length strings, and it can be less efficient than other sorting algorithms when the data being sorted has a large number of digits or when the range of possible values is large.

Here given code implementation process.

//C Program
//Radix sort example
#include <stdio.h>
#include <stdlib.h>

//Return maximum element in given array
int maximum_element(int arr[],int size)
{

  int max_value=arr[0],min_value=arr[0];

  for (int i = 1; i < size; ++i)
  {
    if(max_value<arr[i])
    {
      max_value=arr[i];
    }
    if(min_value>arr[i])
    {
      min_value=arr[i];
    }

  }
  if(min_value<0 && -min_value > max_value)
  {
    max_value=-min_value;
  }

  return max_value;
}
//Display array elements
void display(int arr[],int size)
{
  for (int i = 0; i < size; ++i)
  {
    //Print array value of i location
    printf("  %d",arr[i] );
  }
  printf("\n");
}
void run_sort(int arr[],int slot[],int auxiliary[], int size,int mod)
{
  //set initial slot values
  for (int i = 0; i < 10; ++i)
  {
    slot[i]=0;
  }

  for (int i = 0; i < size; ++i)
  {
    if(arr[i]<0)
    {
      printf("\nThis Algorithm are not capable to work to negative numbers\n");
      return;
    }
    //set slot element
    slot[(arr[i]/mod)%10]++;
  }
  //update slot
  for (int i = 1; i < 10; ++i)
  {

    slot[i]+=slot[i-1];

  }
  for (int i = size-1; i >=0 ; --i)
  {
    
    auxiliary[ slot[ ( arr[i] / mod) %10 ]-1 ] = arr[i];
    slot[(arr[i] / mod)%10]--;
  }
  //Assign value of actual array
  for (int i = 0; i < size; ++i)
  {
    arr[i]=auxiliary[i];
  }

}
void radix_sort(int arr[],int size)
{
  //Get the maximum element of array
  int max_value=maximum_element(arr,size);


  int mod = 1;
  //allocated slot of 0 - 9 for positive number 
  int slot[10];

  //Allocate auxiliary space to perform radix sort
  int auxiliary[size];
 
  while(max_value!=0)
  {
   
    run_sort(arr,slot,auxiliary,size,mod);

    mod = mod*10;

    //remove last digit
    max_value /= 10;

  }

}
int main()
{
 
  //Define array elements
  int arr[]= {8,2,3,8,1,3,73,121,54,23,84,13,67,23,52};
  
  //Get the size of array elements
  int size=sizeof(arr)/sizeof(arr[0]);

  printf("Before Sort : \n");
  display(arr,size);
  radix_sort(arr,size);

  printf("After Sort : \n");
  display(arr,size);

 
  return 0;
}

Output

Before Sort :
  8  2  3  8  1  3  73  121  54  23  84  13  67  23  52
After Sort :
  1  2  3  3  8  8  13  23  23  52  54  67  73  84  121
/*
  C++ Program
  Radix sort example
*/
#include<iostream>

using namespace std;

class MySort {
	public:

		//Return maximum element in given array
		int maximum_element(int arr[], int size) {
			int max_value = arr[0], min_value = arr[0];
			for (int i = 1; i < size; ++i) {
				if (max_value < arr[i]) {
					max_value = arr[i];
				}
				if (min_value > arr[i]) {
					min_value = arr[i];
				}
			}
			if (min_value < 0 && -min_value > max_value) {
				max_value = -min_value;
			}
			return max_value;
		}
	//Display array elements
	void display(int arr[], int size) {
		for (int i = 0; i < size; ++i) {
			cout << " " << arr[i];
		}
		cout << "\n";
	}
	void run_sort(int arr[], int slot[], int auxiliary[], int size, int mod) {
		//set initial slot values

		for (int i = 0; i < 10; ++i) {
			slot[i] = 0;
		}
		for (int i = 0; i < size; ++i) {
			if (arr[i] < 0) {
				cout << "\nThis Algorithm are not capable to work to negative numbers\n";
				return;
			}
			//set slot element
			slot[(arr[i] / mod) % 10]++;
		}
		//update slot

		for (int i = 1; i < 10; ++i) {
			slot[i] += slot[i - 1];
		}
		for (int i = size - 1; i >= 0; --i) {
			auxiliary[slot[(arr[i] / mod) % 10] - 1] = arr[i];
			slot[(arr[i] / mod) % 10]--;
		}
		//Assign value of actual array

		for (int i = 0; i < size; ++i) {
			arr[i] = auxiliary[i];
		}
	}
	void radix_sort(int arr[], int size) {
		//Get the maximum element of array
		int max_value = this->maximum_element(arr, size);
		int mod = 1;
		int slot[10];
		int auxiliary[size];
		while (max_value != 0) {
			this->run_sort(arr, slot, auxiliary, size, mod);
			mod = mod *10;
			//remove last digit
			max_value /= 10;
		}
	}
};
int main() {
	MySort obj ;
	int arr[] = {
		8,
		2,
		3,
		8,
		1,
		3,
		73,
		121,
		54,
		23,
		84,
		13,
		67,
		23,
		52
	};
	//Get the size of array
	int size = sizeof(arr) / sizeof(arr[0]);
	cout << "Before Sort : \n";
	obj.display(arr, size);
	obj.radix_sort(arr, size);
	cout << "After Sort : \n";
	obj.display(arr, size);
	return 0;
}

Output

Before Sort :
 8 2 3 8 1 3 73 121 54 23 84 13 67 23 52
After Sort :
 1 2 3 3 8 8 13 23 23 52 54 67 73 84 121
/*
  Java Program
  Radix sort example
*/
public class MySort {


  //Return maximum element in given array
  public int maximum_element(int []arr,int size)
  {

    int max_value=arr[0],min_value=arr[0];

    for (int i = 1; i < size; ++i)
    {
      if(max_value<arr[i])
      {
        max_value=arr[i];
      }
      if(min_value>arr[i])
      {
        min_value=arr[i];
      }

    }
    if(min_value<0 && -min_value > max_value)
    {
      max_value=-min_value;
    }

    return max_value;
  }
  //Display array elements
  public void display(int []arr, int size)
  {
    for (int i = 0; i < size; ++i)
    {
      System.out.print("  "+arr[i] );
    }
    System.out.print("\n");
  }
  public void run_sort(int []arr,int []slot,int []auxiliary, int size,int mod)
  {
    //set initial slot values
    for (int i = 0; i < 10; ++i)
    {
      slot[i]=0;
    }

    for (int i = 0; i < size; ++i)
    {
      if(arr[i]<0)
      {
        System.out.print("\nThis Algorithm are not capable to work to negative numbers\n");
        return;
      }
      //set slot element
      slot[(arr[i]/mod)%10]++;
    }
    //update slot
    for (int i = 1; i < 10; ++i)
    {

      slot[i]+=slot[i-1];

    }
    for (int i = size-1; i >=0 ; --i)
    {
      
      auxiliary[ slot[ ( arr[i] / mod) %10 ]-1 ] = arr[i];
      slot[(arr[i] / mod)%10]--;
    }
    //Assign value of actual array
    for (int i = 0; i < size; ++i)
    {
      arr[i]=auxiliary[i];
    }

  }
  public void radix_sort(int []arr,int size)
  {
    //Get the maximum element of array
    int max_value=maximum_element(arr,size);


    int mod = 1;
    //allocated slot of 0 - 9 for positive number 
    int []slot= new int[10];

    //Allocate auxiliary space to perform radix sort
    int []auxiliary = new int[size];
   
    while(max_value!=0)
    {
     
      run_sort(arr,slot,auxiliary,size,mod);

      mod = mod*10;

      //remove last digit
      max_value /= 10;

    }

  }
  public static void main(String[] args) 
  {
  

    MySort obj = new MySort();
    //Define array elements
    int []arr= {8,2,3,8,1,3,73,121,54,23,84,13,67,23,52};
    //Get the size of array
    int size = arr.length;
    System.out.print("Before Sort : \n");
    obj.display(arr,size);

    obj.radix_sort(arr,size);
    System.out.print("After Sort : \n");
    obj.display(arr,size);

  }
}

Output

Before Sort :
 8 2 3 8 1 3 73 121 54 23 84 13 67 23 52
After Sort :
 1 2 3 3 8 8 13 23 23 52 54 67 73 84 121
/*
  C# Program
  Radix sort example
*/
using System;
public class MySort {
	//Return maximum element in given array
	public int maximum_element(int[] arr, int size) {
		int max_value = arr[0], min_value = arr[0];
		for (int i = 1; i < size; ++i) {
			if (max_value < arr[i]) {
				max_value = arr[i];
			}
			if (min_value > arr[i]) {
				min_value = arr[i];
			}
		}
		if (min_value < 0 && -min_value > max_value) {
			max_value = -min_value;
		}
		return max_value;
	}
	//Display array elements
	public void display(int[] arr, int size) {
		for (int i = 0; i < size; ++i) {
			Console.Write(" " + arr[i]);
		}
		Console.Write("\n");
	}
	public void run_sort(int[] arr, int[] slot, int[] auxiliary, int size, int mod) {
		//set initial slot values

		for (int i = 0; i < 10; ++i) {
			slot[i] = 0;
		}
		for (int i = 0; i < size; ++i) {
			if (arr[i] < 0) {
				Console.Write("\nThis Algorithm are not capable to work to negative numbers\n");
				return;
			}
			//set slot element
			slot[(arr[i] / mod) % 10]++;
		}
		//update slot

		for (int i = 1; i < 10; ++i) {
			slot[i] += slot[i - 1];
		}
		for (int i = size - 1; i >= 0; --i) {
			auxiliary[slot[(arr[i] / mod) % 10] - 1] = arr[i];
			slot[(arr[i] / mod) % 10]--;
		}
		//Assign value of actual array

		for (int i = 0; i < size; ++i) {
			arr[i] = auxiliary[i];
		}
	}
	public void radix_sort(int[] arr, int size) {
		//Get the maximum element of array
		int max_value = maximum_element(arr, size);
		int mod = 1;
      	//allocated slot of 0 - 9 for positive number 
		int[] slot = new int[10];
      	//Allocate auxiliary space to perform radix sort
		int[] auxiliary = new int[size];
		while (max_value != 0) {
			run_sort(arr, slot, auxiliary, size, mod);
			mod = mod * 10;
			//remove last digit
			max_value /= 10;
		}
	}
	public static void Main(String[] args) {
		MySort obj = new MySort();
		int[]
		//Define array elements
		arr = {
			8,
			2,
			3,
			8,
			1,
			3,
			73,
			121,
			54,
			23,
			84,
			13,
			67,
			23,
			52
		};
		//Get the size of array
		int size = arr.Length;
		Console.Write("Before Sort : \n");
		obj.display(arr, size);
		obj.radix_sort(arr, size);
		Console.Write("After Sort : \n");
		obj.display(arr, size);
	}
}

Output

Before Sort :
 8 2 3 8 1 3 73 121 54 23 84 13 67 23 52
After Sort :
 1 2 3 3 8 8 13 23 23 52 54 67 73 84 121
<?php
/*
  Php Program
  Radix sort example
*/
class MySort {
	//Return maximum element in given array

	public 	function maximum_element($arr, $size) {
		$max_value = $arr[0];
		$min_value = $arr[0];
		for ($i = 1; $i < $size; ++$i) {
			if ($max_value < $arr[$i]) {
				$max_value = $arr[$i];
			}
			if ($min_value > $arr[$i]) {
				$min_value = $arr[$i];
			}
		}
		if ($min_value < 0 && -$min_value > $max_value) {
			$max_value = -$min_value;
		}
		return $max_value;
	}
	//Display array elements

	public 	function display($arr, $size) {
		for ($i = 0; $i < $size; ++$i) {
			echo(" ". $arr[$i]);
		}
		echo("\n");
	}
	public 	function run_sort(&$arr, $slot, $auxiliary, $size, $mod) {
		//set initial slot values

		for ($i = 0; $i < 10; ++$i) {
			$slot[$i] = 0;
		}
		for ($i = 0; $i < $size; ++$i) {
			if ($arr[$i] < 0) {
				echo("\nThis Algorithm are not capable to work to negative numbers\n");
				return;
			}
			//set slot element
			$slot[(intval($arr[$i] / $mod)) % 10]++;
		}
		//update slot

		for ($i = 1; $i < 10; ++$i) {
			$slot[$i] += $slot[$i - 1];
		}
		for ($i = $size - 1; $i >= 0; --$i) {
			$auxiliary[$slot[(intval($arr[$i] / $mod)) % 10] - 1] = $arr[$i];
			$slot[(intval($arr[$i] / $mod)) % 10]--;
		}
		//Assign value of actual array

		for ($i = 0; $i < $size; ++$i) {
			$arr[$i] = $auxiliary[$i];
		}
	}
	public 	function radix_sort(&$arr, $size) {
		//Get the maximum element of array
		$max_value = $this->maximum_element($arr, $size);
		$mod = 1;
		//allocated slot of 0 - 9 for positive number 
		$slot = array_fill(0, 10, 0);
		//Allocate auxiliary space to perform radix sort
		$auxiliary = array_fill(0, $size, 0);
		while ($max_value != 0) {
			$this->run_sort($arr, $slot, $auxiliary, $size, $mod);
			$mod = $mod *10;
          	//remove last digit
			$max_value = intval($max_value / 10);
		}
	}
}

function main() {
	$obj = new MySort();
	//Define array elements
	$arr = array(8, 2, 3, 8, 1, 3, 73, 121, 54, 23, 84, 13, 67, 23, 52);
	//Get the size of array
	$size = count($arr);
	echo("Before Sort : \n");
	$obj->display($arr, $size);
	$obj->radix_sort($arr, $size);
	echo("After Sort : \n");
	$obj->display($arr, $size);

}
main();

Output

Before Sort :
 8 2 3 8 1 3 73 121 54 23 84 13 67 23 52
After Sort :
 1 2 3 3 8 8 13 23 23 52 54 67 73 84 121
/*
  Node Js Program
  Radix sort example
*/
class MySort {
	//Return maximum element in given array
	maximum_element(arr, size) {
		var max_value = arr[0];
		var min_value = arr[0];
		for (var i = 1; i < size; ++i) {
			if (max_value < arr[i]) {
				max_value = arr[i];
			}

			if (min_value > arr[i]) {
				min_value = arr[i];
			}
		}

		if (min_value < 0 && -min_value > max_value) {
			max_value = -min_value;
		}

		return max_value;
	}

	//Display array elements
	display(arr, size) {
		for (var i = 0; i < size; ++i) {
			process.stdout.write(" " + arr[i]);
		}

		process.stdout.write("\n");
	}
	run_sort(arr, slot, auxiliary, size, mod) {
		//set initial slot values

		for (var i = 0; i < 10; ++i) {
			slot[i] = 0;
		}

		for (var i = 0; i < size; ++i) {
			if (arr[i] < 0) {
				process.stdout.write("\nThis Algorithm are not capable to work to negative numbers\n");
				return;
			}

			//set slot element
			slot[(parseInt(arr[i] / mod)) % 10]++;
		}

		//update slot

		for (var i = 1; i < 10; ++i) {
			slot[i] += slot[i - 1];
		}

		for (var i = size - 1; i >= 0; --i) {
			auxiliary[slot[(parseInt(arr[i] / mod)) % 10] - 1] = arr[i];
			slot[(parseInt(arr[i] / mod)) % 10]--;
		}

		//Assign value of actual array

		for (var i = 0; i < size; ++i) {
			arr[i] = auxiliary[i];
		}
	}
	radix_sort(arr, size) {
		//Get the maximum element of array
		var max_value = this.maximum_element(arr, size);
		var mod = 1;
		//allocated slot of 0 - 9 for positive number 
		var slot = Array(10).fill(0);
		//Allocate auxiliary space to perform radix sort
		var auxiliary = Array(size).fill(0);
		while (max_value != 0) {
			this.run_sort(arr, slot, auxiliary, size, mod);
			mod = mod *10;
          	//remove last digit
			max_value = parseInt(max_value / 10);
		}
	}
}

function main(args) {
	var obj = new MySort();
	//Define array elements
	var arr = [8, 2, 3, 8, 1, 3, 73, 121, 54, 23, 84, 13, 67, 23, 52];
	//Get the size of array
	var size = arr.length;
	process.stdout.write("Before Sort : \n");
	obj.display(arr, size);
	obj.radix_sort(arr, size);
	process.stdout.write("After Sort : \n");
	obj.display(arr, size);
}

main();

Output

Before Sort :
 8 2 3 8 1 3 73 121 54 23 84 13 67 23 52
After Sort :
 1 2 3 3 8 8 13 23 23 52 54 67 73 84 121
# Python 3 Program
# Radix sort example
class MySort :
	# Return maximum element in given array
	def maximum_element(self, arr, size) :
		max_value = arr[0]
		min_value = arr[0]
		i = 1
		while (i < size) :
			if (max_value < arr[i]) :
				max_value = arr[i]
			
			if (min_value > arr[i]) :
				min_value = arr[i]
			
			i += 1
		
		if (min_value < 0 and - min_value > max_value) :
			max_value = -min_value
		
		return max_value
	
	# Display array elements
	def display(self, arr, size) :
		i = 0
		while (i < size) :
			print(" ", arr[i], end = "")
			i += 1
		
		print("\n", end = "")
	
	def run_sort(self, arr, slot, auxiliary, size, mod) :
		# set initial slot values
		i = 0
		while (i < 10) :
			slot[i] = 0
			i += 1
		
		i = 0
		while (i < size) :
			if (arr[i] < 0) :
				print("\nThis Algorithm are not capable to work to negative numbers\n", end = "")
				return
			
			# set slot element
			slot[(int(arr[i] / mod)) % 10] += 1
			i += 1
		
		# update slot
		i = 1
		while (i < 10) :
			slot[i] += slot[i - 1]
			i += 1
		
		i = size - 1
		while (i >= 0) :
			auxiliary[slot[(int(arr[i] / mod)) % 10] - 1] = arr[i]
			slot[(int(arr[i] / mod)) % 10] -= 1
			i -= 1
		
		# Assign value of actual array
		i = 0
		while (i < size) :
			arr[i] = auxiliary[i]
			i += 1
		
	
	def radix_sort(self, arr, size) :
		max_value = self.maximum_element(arr, size)
		mod = 1
		slot = [0] * 10
		auxiliary = [0] * size
		while (max_value != 0) :
			self.run_sort(arr, slot, auxiliary, size, mod)
			mod = mod * 10
			# remove last digit
			max_value = int(max_value / 10)
		
	

def main() :
	obj = MySort()
	arr = [8, 2, 3, 8, 1, 3, 73, 121, 54, 23, 84, 13, 67, 23, 52]
	size = len(arr)
	print("Before Sort : \n", end = "")
	obj.display(arr, size)
	obj.radix_sort(arr, size)
	print("After Sort : \n", end = "")
	obj.display(arr, size)


if __name__ == "__main__":
	main()

Output

Before Sort :
  8  2  3  8  1  3  73  121  54  23  84  13  67  23  52
After Sort :
  1  2  3  3  8  8  13  23  23  52  54  67  73  84  121
#   Ruby Program
#   Radix sort example
class MySort 
	# Return maximum element in given array
	def maximum_element(arr, size) 
		max_value = arr[0]
		min_value = arr[0]
		i = 1
		while (i < size) 
			if (max_value < arr[i]) 
				max_value = arr[i]
			end
			if (min_value > arr[i]) 
				min_value = arr[i]
			end
			i += 1
		end
		if (min_value < 0 && -min_value > max_value) 
			max_value = -min_value
		end
		return max_value
	end
	# Display array elements
	def display(arr, size) 
		i = 0
		while (i < size) 
			print(" ", arr[i])
			i += 1
		end
		print("\n")
	end
	def run_sort(arr, slot, auxiliary, size, mod) 
		# set initial slot values
		i = 0
		while (i < 10) 
			slot[i] = 0
			i += 1
		end
		i = 0
		while (i < size) 
			if (arr[i] < 0) 
				print("\nThis Algorithm are not capable to work to negative numbers\n")
				return
			end
			# set slot element
			slot[(arr[i] / mod) % 10] += 1
			i += 1
		end
		# update slot
		i = 1
		while (i < 10) 
			slot[i] += slot[i - 1]
			i += 1
		end
		i = size - 1
		while (i >= 0) 
			auxiliary[slot[(arr[i] / mod) % 10] - 1] = arr[i]
			slot[(arr[i] / mod) % 10] -= 1
			i -= 1
		end
		# Assign value of actual array
		i = 0
		while (i < size) 
			arr[i] = auxiliary[i]
			i += 1
		end
	end
	def radix_sort(arr, size) 
		max_value = self.maximum_element(arr, size)
		mod = 1
		slot = Array.new(10, 0)
		auxiliary = Array.new(size, 0)
		while (max_value != 0) 
			self.run_sort(arr, slot, auxiliary, size, mod)
			mod = mod * 10
			# remove last digit
			max_value /= 10
		end
	end
end
def main() 
	obj = MySort.new()
	arr = [8, 2, 3, 8, 1, 3, 73, 121, 54, 23, 84, 13, 67, 23, 52]
	size = arr.length
	print("Before Sort  :\n")
	obj.display(arr, size)
	obj.radix_sort(arr, size)
	print("After Sort  :\n")
	obj.display(arr, size)
end
main()

Output

Before Sort  :
 8 2 3 8 1 3 73 121 54 23 84 13 67 23 52
After Sort  :
 1 2 3 3 8 8 13 23 23 52 54 67 73 84 121
/*
  Scala Program
  Radix sort example
*/
class MySort {
	//Return maximum element in given array
	def maximum_element(arr: Array[Int], size: Int): Int = {
		var max_value: Int = arr(0);
		var min_value: Int = arr(0);
		var i: Int = 1;
		while (i < size) {
			if (max_value < arr(i)) {
				max_value = arr(i);
			}
			if (min_value > arr(i)) {
				min_value = arr(i);
			}
			i += 1;
		}
		if (min_value < 0 && -min_value > max_value) {
			max_value = -min_value;
		}
		return max_value;
	}
	//Display array elements
	def display(arr: Array[Int], size: Int): Unit = {
		var i: Int = 0;
		while (i < size) {
			print(" " + arr(i));
			i += 1;
		}
		print("\n");
	}
	def run_sort(arr: Array[Int], slot: Array[Int], auxiliary: Array[Int], size: Int, mod: Int): Unit = {
		//set initial slot values
		var i: Int = 0;
		while (i < 10) {
			slot(i) = 0;
			i += 1;
		}
		i = 0;
		while (i < size) {
			if (arr(i) < 0) {
				print("\nThis Algorithm are not capable to work to negative numbers\n");

				return;
			}
			//set slot element
			slot(((arr(i) / mod).toInt) % 10) += 1;
			i += 1;
		}
		//update slot
		i = 1;
		while (i < 10) {
			slot(i) += slot(i - 1);
			i += 1;
		}
		i = size - 1;
		while (i >= 0) {
			auxiliary(slot(((arr(i) / mod).toInt) % 10) - 1) = arr(i);
			slot(((arr(i) / mod).toInt) % 10) -= 1;
			i -= 1;
		}
		//Assign value of actual array
		i = 0;
		while (i < size) {
			arr(i) = auxiliary(i);
			i += 1;
		}
	}
	def radix_sort(arr: Array[Int], size: Int): Unit = {
		var max_value: Int = this.maximum_element(arr, size);
		var mod: Int = 1;
		val slot: Array[Int] = Array.fill[Int](10)(0);
		val auxiliary: Array[Int] = Array.fill[Int](size)(0);
        while (max_value != 0) {
            this.run_sort(arr, slot, auxiliary, size, mod);
            mod = mod * 10;
          //remove last digit
            max_value = (max_value / 10).toInt;
        }
    }
}
object Main {
	def main(args: Array[String]): Unit = {
		val obj: MySort = new MySort();
		var arr: Array[Int] = Array(8, 2, 3, 8, 1, 3, 73, 121, 54, 23, 84, 13, 67, 23, 52);
		val size: Int = arr.length;
		print("Before Sort : \n");
		obj.display(arr, size);
		obj.radix_sort(arr, size);
		print("After Sort : \n");
		obj.display(arr, size);
	}
}

Output

Before Sort :
 8 2 3 8 1 3 73 121 54 23 84 13 67 23 52
After Sort :
 1 2 3 3 8 8 13 23 23 52 54 67 73 84 121
/*
  Swift Program
  Radix sort example
*/
class MySort {
	//Return maximum element in given array
	func maximum_element(_ arr: [Int], _ size: Int) -> Int {
		var max_value: Int = arr[0];
		var min_value: Int = arr[0];
		var i: Int = 1;
		while (i < size) {
			if (max_value < arr[i]) {
				max_value = arr[i];
			}
			if (min_value > arr[i]) {
				min_value = arr[i];
			}
			i += 1;
		}
		if (min_value < 0 && -min_value > max_value) {
			max_value = -min_value;
		}
		return max_value;
	}
	//Display array elements
	func display(_ arr: [Int], _ size: Int) {
		var i: Int = 0;
		while (i < size) {
			print(" ", arr[i], terminator: "");
			i += 1;
		}
		print("\n", terminator: "");
	}
	func run_sort(_ arr: inout [Int], _ slot: inout [Int], _ auxiliary: inout [Int], _ size: Int, _ mod: Int) {
		//set initial slot values
		var i: Int = 0;
		while (i < 10) {
			slot[i] = 0;
			i += 1;
		}
		i = 0;
		while (i < size) {
			if (arr[i] < 0) {
				print("\nThis Algorithm are not capable to work to negative numbers\n", terminator: "");
				return;
			}
			//set slot element
			slot[(arr[i] / mod) % 10] += 1;
			i += 1;
		}
		//update slot
		i = 1;
		while (i < 10) {
			slot[i] += slot[i - 1];
			i += 1;
		}
		i = size - 1;
		while (i >= 0) {
			auxiliary[slot[(arr[i] / mod) % 10] - 1] = arr[i];
			slot[(arr[i] / mod) % 10] -= 1;
			i -= 1;
		}
		//Assign value of actual array
		i = 0;
		while (i < size) {
			arr[i] = auxiliary[i];
			i += 1;
		}
	}
	func radix_sort(_ arr: inout [Int], _ size: Int) {
		var max_value: Int = self.maximum_element(arr, size);
		var mod: Int = 1;
		var slot: [Int] = Array(repeating: 0, count: 10);
		var auxiliary: [Int] = Array(repeating: 0, count: size);
        while (max_value != 0) {
            self.run_sort(&arr, &slot, &auxiliary, size, mod);
            mod = mod * 10;
            //remove last digit
            max_value /= 10;
        }
	}
}
func main() {
	let obj: MySort = MySort();
	var arr: [Int] = [8, 2, 3, 8, 1, 3, 73, 121, 54, 23, 84, 13, 67, 23, 52];
	let size: Int = arr.count;
	print("Before Sort : \n", terminator: "");
	obj.display(arr, size);
	obj.radix_sort(&arr, size);
	print("After Sort : \n", terminator: "");
	obj.display(arr, size);
}
main();

Output

Before Sort :
  8  2  3  8  1  3  73  121  54  23  84  13  67  23  52
After Sort :
  1  2  3  3  8  8  13  23  23  52  54  67  73  84  121




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment