#Day11 #100DaysOfCode
sort the array based on digits.
use counting sort as a subroutine.
works with integer type number only.
if want to do with negative number, separate the negatives, remove the sign, radix sort them, and concatenate back with the positive. Other than that, turning sign bit on and off like in stackoverflow.
time complexity: O(d*(n+b)) where d is the number of digits, which is the number of loops the sort goes through. b is the base for representing numbers i.e: decimal system, b is 10.
counting sort sorts numbers in linear time, where k is not very large. O(n+k).
if k is n square, it fails (takes more time than comparison based algorithm). therefore have to use radix sort.
radix sort is useful for number of wide range (i.e: very large digit number) or bases like 32 or 64 bits. However, because it uses counting sort as a subroutine, which requires extra storage and takes large space. Therefore, it is not used so frequent.
to get the digits at every iteration, you need an exp variable. it gets multiplied by 10 every time till the largest no of digits. i.e: to get the 2 in 123, exp is 10, (123/10)%10.
sort the array based on digits.
use counting sort as a subroutine.
works with integer type number only.
if want to do with negative number, separate the negatives, remove the sign, radix sort them, and concatenate back with the positive. Other than that, turning sign bit on and off like in stackoverflow.
time complexity: O(d*(n+b)) where d is the number of digits, which is the number of loops the sort goes through. b is the base for representing numbers i.e: decimal system, b is 10.
counting sort sorts numbers in linear time, where k is not very large. O(n+k).
if k is n square, it fails (takes more time than comparison based algorithm). therefore have to use radix sort.
radix sort is useful for number of wide range (i.e: very large digit number) or bases like 32 or 64 bits. However, because it uses counting sort as a subroutine, which requires extra storage and takes large space. Therefore, it is not used so frequent.
to get the digits at every iteration, you need an exp variable. it gets multiplied by 10 every time till the largest no of digits. i.e: to get the 2 in 123, exp is 10, (123/10)%10.
