Counting sort is based on keys between a specific range of i

Counting sort is based on keys between a specific range of integer numbers Modify the Counting sort algorithm such that it can also sort any combination of integer numbers or alphabetic (small and big letters).

Solution

Algorithm countingSort( A : list of sortable items )

Input: A is the set of unsorted elements

Output: B is the set of sorted elements

n length(A)

max A[0]

//Complexity: O(n)

for i 0 to n

     if(A[i]>max)

        max A[0]

      end if

end for

C[1...max] // Initialize this list to store the number of occurrence of each key

//Complexity: O(max)

for i 0 to max

   C[i] 0

end for

//Complexity: O(n)

for i 0 to n

   C[A[j]] C[A[j]]+1

end for

//Complexity: O(n)

for i 0 to n

   C[i] C[i]+C[i-1]

end for

//Complexity: O(n)

for j n-1 to 0

    B[C[A[j]]] A[j]

     C[A[j]] C[A[j]]-1

end for

return

Total Complexity: O(n) + O(max) + O(n) + O(n) + O(n) = O(n)

big={A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z}

small={a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z}

Algorithm countingSortWithAlphabetically( A : list of charactera )

Input: A is the set of unsorted characters

Output: B is the set of alphabetically sorted characters

n length(A)

T1[1.....n]

T2[1.....n]

//Complexity: O(n²)

for i 0 to n

   for j 0 to 27

     if(A[i]=big[j] or A[i]=small[j])

       T1[i] j

      end if

end for

T2 countingSort(T1)

//Complexity: O(n)

for i 0 to n

    B[i] big[T2[i]]

return

Total Complexity: O(n²) + ( O(n) + O(max) + O(n) + O(n) + O(n) ) + O(n) = O(n²)