// Subtract Sort
#include<stdio.h>
int print_arr(int arr[], int n)
{
int z;
for(z=0 ; z<n ; z++)
{
printf("%d ", arr[z]);
}
}
void subtract_sort(int arr[], int arr_size)
{
int operations=0;
int j=0;
int val=1;
int all_zero=0;
while(!all_zero)
{
int m;
all_zero=1;
int i;
for(i=j ; i<arr_size ; i++)
{
arr[i]--;
if(arr[i]==0)
{
arr[i]=arr[j];
arr[j]=val;
j++;
}
all_zero=0;
operations++;
}
val++;
}
printf("Number of times algorithm passed through for-loop is %d\n", operations);
printf("Calculated number of times algorithm passes for-loop in worst-case scenario is k*n = %d * %d = %d\n", val-2, arr_size, (val-2)*arr_size);
if(operations<=(val-2)*arr_size)
{
printf("The time-complexity in worst-case scenario \"O(kn)\" holds.\n");
}
}
int main()
{
int arr[9]={10,10,10,10,10,10,10,10,10};
int size=9;
subtract_sort(arr, size);
printf("\n--------------------------\n");
print_arr(arr, size);
return 0;
}
