FOR FREE YEAR SOLVED
Sorting an Array
Back to ProgrammingDescription
The program is written here to take a number as input and print the digits of the number in sorted order. First the digits are stored separately in an array. Now, each element of the array represents each digit of the number. The array is sorted using bubble sort technique, which makes all the digits of the number sorted. Then the elements of the sorted array are printed.
For example, if a given number is 873421, then array after separating the digits will be:
8 | 7 | 3 | 4 | 2 | 1 |
0 1 2 3 4 5
Now, these array elements will be sorted. After sorting the sorted array will be:
1 | 2 | 3 | 4 | 7 | 8 |
0 1 2 3 4 5
So, the ordered digits of the number is: 123478
Algorithm
INPUT: A number
OUTPUT: Ordered number of the given number
PROCESS:
Step 1: [Taking the input]
Read n
Step 2: [Finding the ordered number]
Set t<-n
Set i<-0
[Storing the digits in an array]
While t>0 repeat
Set a[i]<-t mod 10
Set i<-i+1
Set t<-t/10
[End of ‘while’ loop]
[Storing the length of the number]
Set l<-i
[Sorting the digits]
For i=0 to l-1 repeat
For j=0 to l-i-2 repeat
If a[j]>a[j+1] then
Set t<-a[j]
Set a[j]<-a[j+1]
Set a[j+1]<-t
[End of ‘if’]
[End of ‘for’ loop]
[End of ‘for’ loop]
[Printing the ordered number]
Print "The ordered digits are: "
For i=0 to l-1 repeat
Print a[i]
[End of ‘for’ loop]
Step 3: Stop.
Code
TIME COMPLEXITY:
while(t>0)------------------------------------------O(log10n)
{
a[i++]=t%10;
t=t/10;
}
//storing the length of the number
l=i;
//sorting the digits
for(i=0;i<l;i++)--------------------------------O(l)
{
for(j=0;j<l-i-1;j++)---------------O(l)
{
if(a[j]>a[j+1])----------O(1)
{
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
}
}
//printing the ordered number
printf("The ordered digits are: ");
for(i=0;i<l;i++)----------------------------O(l)
printf("%d",a[i]);
The time complexity of this program is O(log10n+l2+l) where, ‘n’ is the given input, ‘l’ is the number of digits of the number.
SPACE COMPLEXITY:
The time complexity of this program is O(l) where ‘l’ is the number of digits of the given number.
