How to sort string by cases and number order?

Question

Given an array of randomly arranged lower case letters , uppercase letters, and numbers.

How can I sort the array such that all lower case letters come before all uppercase letters, come before all numbers? The classes of characters do not need to be in order in their respective sections.

MUST RUN IN O(n) time, and O(1) space. Obviously can't use build in sort function.

My instant reaction is to looping through the string 3 times for example below.

var newArr = [];

for x in oldArr
    if x is lowercase
        newArr.add(x)

for x in oldArr
    if x is uppercase
        newArr.add(x)

for x in oldArr
    if x is number
        newArr.add(x)

But this uses O(n) memory.

Use Radix Sort or Counting Sort. Read about it, write code, and if you stuck, back here. Radix is not comparison sort. All comparison sorts have lower bound of Ω(n log n). — Niyoko, Oct 31 '16 at 01:48
You can get idea about radix, counting and bucket sort from here - http://stackoverflow.com/questions/14368392/radix-sort-vs-counting-sort-vs-bucket-sort-whats-the-difference — Wasi Ahmad, Oct 31 '16 at 01:56
https://en.wikipedia.org/wiki/Dutch_national_flag_problem : The problem is to partition a vector of elements with three colours so that the elements are contiguous by colour. AIUI, that's exactly what you are trying to do. — rici, Oct 31 '16 at 03:51
dutch national flag problem solution works, radix sort and counting sort doesn't use constant space or run in linear time so it dosen't apply to my question — Ohhh, Oct 31 '16 at 18:39

score 1 · Answer 1 · answered Oct 31 '16 at 12:47

To use O(1) memory you should do swaps in place. To do in in O(n) time you should do 2 runs partitioning array of chars.

1) Make swap function that replaces 2 item with indexes i and j of array a:

swap (a, i, j):
    if i <> j:
        tmp = a[i]
        a[i] = a[j]
        a[j] = a[i]

2) Make run over array and put lowercase letters first:

j = 0
for i in range(0, len(oldArr)):
    if oldArr[i] is lowercase:
        swap(oldArr, i, j)
        j++

3) Make run over array and put uppercase letters after lowercase letters:

for i in range(j, len(oldArr)):
    if oldArr[i] is uppercase:
        swap(oldArr, i, j)
        j++

4) If number is the only left option for characters, you can do nothing else

score 0 · Answer 2 · answered Oct 31 '16 at 18:45

Radix sort and counting sort doesn't run in linear time or uses constant space. However, I found the Dutch National Flag problem to be similar and found the solution. Below is the link and my code. http://www.geeksforgeeks.org/sort-an-array-of-0s-1s-and-2s/ https://en.wikipedia.org/wiki/Dutch_national_flag_problem

var sortLowerUpperNumber = function(arr) {

    var lower = 0;                  // Index for lower case letter
    var mid = 0;                    // Index for upper case letter
    var num = nums.length - 1;      // Index for number 

    while (mid <= num) {
        switch(arr[mid]) {
            case lowerCaseLetter:
                swap(arr[low], arr[mid])
                low++;
                mid++;
                break;
            case upperCaseLetter:
                mid++;
                break;
            case number:
                swap(arr[mid], arr[num])
                num--;
                break;
        }
    }
};

How to sort string by cases and number order?

2 Answers2