Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

Sort isometric strings lexicographically using radix sort LSD method

0 x00 preface

We all know that there are many ways to sort a string lexicographically, so today we’re going to talk about sorting using a method called radix sort.

Radix sort, like counting sort, is a kind of bucket sort, but counting sort is not very suitable for alphabetic sorting, so we use radix sort here.

Radix sort simply means that the letters are divided into parts, and each part is sorted, either from the back or from the back. In this article, we focus on the back to front case.

0x01 Unmasking logic

Read the code, and then we’ll talk about it in detail.

char str[10][6]; void card_sort( void ){ char result_array[10][6]; for(int i = 4; i>=0; i--){ int count_array[26]={0}; for(int j=0; j<10; j++){ int num = str[j][i]-'a'; count_array[num]++; } for(int j=1; j<26; j++){ count_array[j] = count_array[j] + count_array[j-1]; } for(int j=0; j<10; j++){ int num = str[j][i]-'a'; strcpy(result_array[--count_array[num]],str[j]); } for(int j=0; j<10; j++){ strcpy(str[j],result_array[j]); }}}Copy the code

The purpose of this code is to place 10 English words of length 5 in lexicographical order.

Set the STR character array to store the 10 words of length 5.

We set up a for loop from 4 to 0 to distinguish bits of a word of length 5.

We then initialize the count_array array.

The next two steps are to put the frequency into count_array and convert it to an index.

The next step, which I think is the most important, is to index the elements into categories, where we use a temporary array called result_array to temporarily store the data.

Each time the loop completes, one digit of the letter is arranged.

Here is the result of the first round of sorting:

appla bbbbb applb ccccc applc ddddd appld apple qqqqq zzzzz
Copy the code

We decrement count_array to fill in the same data that could have been filled in the last void. You add them by frequency and then you convert them to index and subtraction is the essence of this algorithm.

Finally, the data in the temporary array is handed to the array to be sorted, indicating that the bit has been sorted successfully.

0x02 Consider the limitations of this approach

Move your little brain. What are the limitations of this approach?

Yeah, from back to front, what if the string is unequal?

This is problematic, so the standard LSD method of radix sort can only deal with strings of equal length. If the lengths are not necessarily equal, we use MSD method of radix sort.

If this article is well received, we will continue to sort strings using MSD method of radix sort.