Sorting Array of Strings hackerrank C step by step solution

Sorting Array of Strings hackerrank solution:

Welcome back, Guys!!
In this post, we will see Sorting Array of Strings hackerrank step by step solution.
It's one of the hard problem of hackerrank.

The problem statement is as follows: 

To sort a given array of strings into lexicographically increasing order or into an order in which the string with the lowest length appears first, a sorting function with a flag indicating the type of comparison strategy can be written. The disadvantage with doing so is having to rewrite the function for every new comparison strategy.

A better implementation would be to write a sorting function that accepts a pointer to the function that compares each pair of strings. Doing this will mean only passing a pointer to the sorting function with every new comparison strategy.

Given an array of strings, you need to implement a  function which sorts the strings according to a comparison function, i.e, you need to implement the function :

void string_sort(const char **arr,const int cnt, int (*cmp_func)(const char* a, const char* b)){

    

}

The arguments passed to this function are:

an array of strings : 

length of string array: 

pointer to the string comparison function: 

You also need to implement the following four string comparison functions:

 to sort the strings in lexicographically non-decreasing order.

 to sort the strings in lexicographically non-increasing order.

 to sort the strings in non-decreasing order of the number of distinct characters present in them. If two strings have the same number of distinct characters present in them, then the lexicographically smaller string should appear first.

 to sort the strings in non-decreasing order of their lengths. If two strings have the same length, then the lexicographically smaller string should appear first.

Input Format

You just need to complete the function string\_sort and implement the four string comparison functions.

Constraints

 No. of Strings 

 Total Length of all the strings 

You have to write your own sorting function and you cannot use the inbuilt  function

The strings consists of lower-case English Alphabets only.

Output Format

The locked code-stub will check the logic of your code. The output consists of the strings sorted according to the four comparsion functions in the order mentioned in the problem statement.

Sample Input 0

4

wkue

qoi

sbv

fekls

Sample Output 0

fekls

qoi

sbv

wkue

wkue

sbv

qoi

fekls

qoi

sbv

wkue

fekls

qoi

sbv

wkue

fekls

Sorting Array of Strings hacker rank solution :

You can use any sorting algorithm to sort strings in . Bubble sort is fast enough for the constraints in this problem. Let's look how should the bodies of the comparing functions look like.

For the lexicographical sort you should use  from the library . It does exactly what the problem wants. You should not forget to use different signs in the functions:  means  is lexicographically bigger than  vice versa.

For the  you should calculate number of distinct characters in the strings. In order to do this, declare an array  of length  with all items equal to . Go through all characters of your string and when you meet the letter with the corresponding item in  equal to  set it to  and add  to the number of distinct letters.

For the sorting by length you should use  from . It returns exactly the length of the string you wanted

#include <stdio.h> #include <stdlib.h> #include <string.h> int lexicographic_sort(const char* a, const char* b){ return strcmp(a, b); } int lexicographic_sort_reverse(const char* a, const char* b){ return strcmp(b, a); } int characters_count(const char *s){ int n = 0; int count[128] = {0}; if (NULL == s){ return -1; } while(*s != '\0'){ if (!count[*s]){ count[*s]++; n++; } s++; } return n; } int sort_by_number_of_distinct_characters(const char* a, const char* b){ int con = characters_count(a) - characters_count(b); return (con ? con : lexicographic_sort(a, b)); } int sort_by_length(const char* a, const char* b) { int len = strlen(a) - strlen(b); return (len ? len : lexicographic_sort(a, b)); } void string_sort(char** arr,const int len,int (*cmp_func)(const char* a, const char* b)){ int mid = len / 2; int con = 0; while(!con){ con = 1; for(int i = 0; i < len - 1; i++){ if(cmp_func(arr[i], arr[i + 1]) > 0) { char *temp = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = temp; con = 0; } } } } int main() { int n; scanf("%d", &n); char** arr; arr = (char**)malloc(n * sizeof(char*)); for(int i = 0; i < n; i++){ *(arr + i) = malloc(1024 * sizeof(char)); scanf("%s", *(arr + i)); *(arr + i) = realloc(*(arr + i), strlen(*(arr + i)) + 1); } string_sort(arr, n, lexicographic_sort); for(int i = 0; i < n; i++) printf("%s\n", arr[i]); printf("\n"); string_sort(arr, n, lexicographic_sort_reverse); for(int i = 0; i < n; i++) printf("%s\n", arr[i]); printf("\n"); string_sort(arr, n, sort_by_length); for(int i = 0; i < n; i++) printf("%s\n", arr[i]); printf("\n"); string_sort(arr, n, sort_by_number_of_distinct_characters); for(int i = 0; i < n; i++) printf("%s\n", arr[i]); printf("\n"); }

Feel free to share your thoughts and doubt in the comment section below.

See you next time...