How does string sorting work algorithmically?

Question

Suppose I was going to write my own algorithm to sort an array of strings. How would I go about making an algorithm about it?

I understand the general idea of using ascii characters to compare each character of a string.

The part where I'm stuck is to compare the whole string alphanumerically.

I thought maybe I could just get the sum of the whole string, but that's not what it means. The following is the correct order:

aaa
abccccccccccccccccc
ac

but not this regarding the sum:

aaa
ac
abcccccccccccccccc

l.sort(function (a,b) {

        let min = Math.min(a.length, b.length);
        for (let i = 0; i < min; i++) {
            let l = a[i];
            let r = b[i];
            if (l !== r) {
                return l.charCodeAt(0) - r.charCodeAt(0);
            }
        }

        return a.length - b.length;
        
});

i want to understand algorithm, not use built in sort functions — Muhammad Umer, Jul 31 '15 at 00:56
when it comes to numbers i understand, you just swap when you find bigger int, and this would work for string too, but i want to understand how computer calculates one string to be bigger or smaller than each other in alphanumeric sort — Muhammad Umer, Jul 31 '15 at 00:57
It's called [lexicographical order](https://en.wikipedia.org/wiki/Lexicographical_order). With a clarification that an "end of string" is considered a character with a lowest code value possible (typically 0). So given strings `a` and `aa`, `a` is "smaller". — D-side, Jul 31 '15 at 01:03

score 1 · Accepted Answer · answered Jul 31 '15 at 01:19

Have a look of implementation of Java.Util.String method compareTo will help you to understand how to compare two String in lexicographical order.

/**
 * Compares two strings lexicographically.
 * The comparison is based on the Unicode value of each character in
 * the strings. The character sequence represented by this
 * {@code String} object is compared lexicographically to the
 * character sequence represented by the argument string. The result is
 * a negative integer if this {@code String} object
 * lexicographically precedes the argument string. The result is a
 * positive integer if this {@code String} object lexicographically
 * follows the argument string. The result is zero if the strings
 * are equal; 
 */

public int compareTo(String anotherString) {
    int len1 = value.length;
    int len2 = anotherString.value.length;
    int lim = Math.min(len1, len2);
    char v1[] = value;
    char v2[] = anotherString.value;

    int k = 0;
    while (k < lim) {
        char c1 = v1[k];
        char c2 = v2[k];
        if (c1 != c2) {
            return c1 - c2;
        }
        k++;
    }
    return len1 - len2;
}

@MuhammadUmer Every character can be treated as an integer which value is corresponding ascii code. Please read https://en.wikipedia.org/wiki/ASCII . — Sayakiss, Jul 31 '15 at 02:09
For example, ASCII code of character 'a' is 97, and 'b' is 98. So 'b' - 'a' = 1. But 'B' is 66, so sort by ASCII code order will get `"Bzz" < "aAA"`. @MuhammadUmer — Sayakiss, Jul 31 '15 at 02:16
If you think sort by ASCII code is not proper for your case, you may define the order of characters first and then use the code mentioned above. @MuhammadUmer — Sayakiss, Jul 31 '15 at 02:17

How does string sorting work algorithmically?

1 Answers1