Question

1. Which sorting algorithms is most efficient to sort string consisting of ASCII characters? Heap sort, Merge sort, insertion sort, bubble sort, selection sort or quick sort?

Answer 1

Counting sort algorithm is efficient when range of data to be sorted is fixed. I the range is from 0 to 255(ASCII range). Counting sort uses an extra constant space proportional to range of data.

Given a string, we have to sort characters of the string in alphabetical order. We will sort the characters of string on the basis of ASCII value of characters.

For Example
If input string is "TECHCRASHCOURSE"
Output string should be "ACCCEEHHORRSSTU"

Sorting strings by comparisons (e.g. standard QuickSort + strcmp-like function) may be a bit slow, especially for long strings sharing a common prefix (the comparison function takes O(s) time, where s is the length of string), thus a standard solution has the complexity of O(s * nlog n).

EXAMPLE USING COUNTING SORT:

In this program, we are going to use counting sort algorithm which sorts numbers in given range in linear time. This algorithm uses an extra array to count the frequency of each character of string. We first take a string as input from user using gets function. Then it calls a user defined function 'sortString' that takes input and output array as input and stores the sorted array in output array. Function sortString count the frequency of characters and store it in counterArray integer array. We populate the outputArray in alphabetical order based on the character's frequency in counterArray. At last we add a null character at the end of outputArray.

It is not a comparison based sorting. It running time complexity is O(n) with space proportional to the range of data.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

/* * C Program to sort characters of a string */ #include <stdio.h> #include <conio.h> #include <string.h> void sortString(char* inputString, char* outputArray); int main(){     char inputString[100], outputArray[100];     printf("Enter a String \n");     gets(inputString);     sortString(inputString, outputArray);     printf("Sorted string \n%s", outputArray);     getch();     return 0; } /* * Function to sort characters of a string */ void sortString(char* inputString, char* outputArray){     /* initialize counterArray to 0 */     int counterArray[256] ={0}, length, counter, index;     length = strlen(inputString);     /* Count frequency of characters in input array*/     for(counter = 0; counter < length; counter++){         counterArray[inputString[counter]]++;     }     /* Populate output array */     for(counter = 0, index = 0; counter < 256; counter++){         if(counterArray[counter] != 0){             while(counterArray[counter] > 0){                 outputArray[index++] = counter;                 counterArray[counter]--;             }         }     }     outputArray[index] = '\0'; }

Program Output

Enter a String
TECHCRASHCOURSE
Sorted string
ACCCEEHHORRSSTU

Enter a String
london
Sorted string
dlnnoo