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

The problem

Please sort 10 English words of length 5 in lexicographical order by asking the user to enter 10 English words of length 5 and then calling card_sort.

char str[10][6];
void card_sort( void )
Copy the code

To solve

1. Concept of algorithm

Radix sort is also called bucket sort. The basic idea for sorting strings is to create buckets that are ordered. We continuously split the string from left to right and put it into the corresponding bucket, loop a number of string lengths, and then take the data out of the bucket for the last time. The string sequence is an ordered sequence.

Of course, this kind of explanation might be of no use to anyone who hasn’t studied radix sorting.

2. Examples

So let’s start with a simple example.

Suppose we sort the cardinality of four numeric strings: 355,223,227,139.

At this point we’re going to set up some buckets that are labeled 1,2,3,5,7,9. (i.e., the number of occurrences)

At this point, we begin the first round of placing operations:

Let’s start with the first number on the right. It..)

Take the last digit of each string: 5,3,7,9

We put the corresponding number string into the corresponding bucket.

3:223

5:355

7:227

9:139

The thing to notice here is that buckets are ordered, so we need to put the numbers in the order of the buckets.

When we put all the strings in, we take them all out, and then we get a new array of strings.

223355227139

We do a second round of putting in the newly obtained sequence of numbers

This time we start with the second number on the right

Take the last digit of each string: 2,5,2,3

We put the corresponding number string into the corresponding bucket.

2:223227

3:139

5:355

Here we find that there are two strings of numbers labeled 2, so we follow the first-come-first rule, that is, 223 is before 227 in the original sequence, so it is still the same in the bucket.

Again, after we put all the strings in, we take them all out again, and we get a new sequence of strings.

223227139355

There’s only one digit left in the string, so we’re going to put it in one last time

Take the first: 2,2,1,3

In the bucket:

1:139

2:223227

3:355

Extract the sequence from the numeric string:

139223227355

At this point we can see that the sequence has become an ordered sequence.

My idea about why we start at the far right is, because the determinate level is different, the determinate level is my own word, which basically means that whatever your current size is, it’s always the previous digit that determines your final position, and the current determinate level comparison works for the comparison used for the previous digit equal.

The same is true for string comparisons.