Which algorithm to use for alphabetical sort?

Question

A lot of sorting algorithms are based on comparisons of numbers. If I correctly understand, when we are using comparison algorithms for alphabetical sort, we compare char codes(their integer presentation) and sort depending on their values. (That's why at ASCII table letter B has a bigger code then A). But during this comparing we sort only by the first letter and not the whole word. When we use db query with ORDER BY we are getting sorting for the whole words. (As I understand the reason of it is db background mechanisms like indexes etc.). Also I heard about Radix sort (sorry, but never used it before) and as I can see it can help with alphabetical sort(maybe I'm wrong).

What algorithm is better to use for sorting by the whole words?

Not correct:

Adam
Aaron
Antony

Correct:

Aaron
Adam
Antony

And am I correct with my assumptions about the whole workflow?

What is the problem faced by other algorithms such as quicksort, heapsort? — doptimusprime
– doptimusprime, Commented Nov 25, 2013 at 8:50
“But during this comparing we sort only by the first letter and not the whole word” – nope … if the first letters of both words are the same, then the comparison continues with the second letter, and so on. — C3roe
– C3roe, Commented Nov 25, 2013 at 8:52

Vilx- · Accepted Answer · 2013-11-25 08:55:25Z

8

You're not quite correct with the assumption about "Compare only the first letter". The algorithm is - if the first letters are the same, compare the next letter. And the next. And the next. Until either you find some letters that are different, or one of the strings runs out.

Also note that simply comparing by ASCII codes is not always enough. Sometimes you need to do a case-insensitive comparison where you consider A to be equal to a. Sometimes you need to do accent-insensitive comparison where you consider ā to be equal to a. And sometimes you need to account for crazy language shit where ß is equal to ss or worse.

My advice is - your programming language should probably have some mechanism for comparing strings. Use that. Don't roll out your own.

After that, any sorting algorithm will work. They all use one simple assumption - that you can compare the items that you sort. Whether they are integers, strings or complex objects, is irrelevant. As long as you can take any two objects and say "this one is bigger and this one is smaller", you're good to go.

(Note also that you need to be consistent about it. If A==B and B==C, then also you need to make sure that A==C. Similarly if A < B and B < C, then you must A < C. Etc.)

answered Nov 25, 2013 at 8:55

Vilx-

107k93 gold badges294 silver badges432 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

vedi0boy Over a year ago

Not true, comparing ASCII is enough since there are separate ASCII codes for capital and small characters.

Kevin Rak Over a year ago

@vedi0boy I think their point was in ASCII A<B but a>B. So if you want it sorted [Aa]-[Zz], then just comparing ASCII values is insufficient. But if you're ok with A-Za-z, then just comparing ASCII values would work.

Vilx- Over a year ago

@KevinRak - Congratulations! You win the unofficial "necrocommenter" badge! 😁

Kevin Rak Over a year ago

@Vilx- 😂 yeah for sure. But I figured it was still worth correcting the misinformation since this came up in my Google search.

Fallen · Accepted Answer · 2013-11-25 09:27:09Z

4

No, the sorting is not based on first character or length. Alphabetical or better to put it as lexicographical ordering are done in the following way,

In C++ the comparison function would look like this,

bool operator<(const string &a, const string &b){
    int l = min(a.size(),b.size());
    for(int i = 0; i < l; i++){
        if( a[i] > b[i]) return false; // a is greater than b
        if( b[i] > a[i]) return true;  // b is greater than a
    }
    if ( a.size() > l) return false;   // a is greater than b
    return true;                       // b is greater than a
}

answered Nov 25, 2013 at 9:27

Fallen

4,5933 gold badges30 silver badges47 bronze badges

Comments

timrau · Accepted Answer · 2013-11-25 08:50:48Z

1

Every sorting algorithm works, if provided correct comparison function.

Just make sure the comparison between elements compares the whole strings instead of looking at only the 1st character when you implement your favorite sorting algorithm or call your sorting library function of choice.

answered Nov 25, 2013 at 8:50

timrau

23.2k4 gold badges55 silver badges67 bronze badges

Comments

MrSmith42 · Accepted Answer · 2013-11-25 08:53:09Z

1

As you already mentioned the only difference between sorting Strings instead of numbers is the compare method used by nearly all sorting algorithms (Radix-sort, bucket-sort are exceptions). Most times one of the fastest sorting algorithms is quick-sort.

answered Nov 25, 2013 at 8:53

MrSmith42

10.2k6 gold badges41 silver badges52 bronze badges

Comments

Saša Šijak · Accepted Answer · 2013-11-25 08:55:08Z

1

You just have to implement comparing function which any sort algorithm can use. In that compare function you will compare whole words, letter by letter, as you need it.

answered Nov 25, 2013 at 8:55

Saša Šijak

9,4775 gold badges52 silver badges85 bronze badges

1 Comment

Christopher Creutzig Over a year ago

Implementing a comparison for strings is not something I’d recommend. Except to very detail-oriented people that need a hobby for the upcoming years. Use the ones your runtime already has – Vilx has listed some of the gotchas, and not even started to talk about locale-dependencies that may or may not be important for your application.

Collectives™ on Stack Overflow

Which algorithm to use for alphabetical sort?

5 Answers 5

4 Comments

Comments

Comments

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

4 Comments

Comments

Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related