Sort months ( with strings ) algorithm

Question

I have this months array:

["January", "March", "December" , "October" ]

And I want to have it sorted like this:

["January", "March", "October", "December" ] 

I'm currently thinking in a "if/else" horrible cascade but I wonder if there is some other way to do this.

The bad part is that I need to do this only with "string" ( that is, without using Date object or anything like that )

What would be a good approach?

Answer 1

If I had a way to supply a custom sorting order, I'd create a list defining the correct order:

correct = List("January", "February", "March", ...)

And then sort by the position in that list, something like:

toSort.sort(a, b) => compare(correct.index(a), correct.index(b))

Answer 2

Create a table with name->index, then sort the array based on its value in the table.

A couple of examples may be useful, in C# arr.sort(myCompare), in Java Collections.sort(arr, myCompare), in Python arr.sort(myCompare), in PHP usort($arr, 'myCompare'), in C++ sort(vec.begin(), vec.end(), myCompare).

Answer 3

Have an array with the proper sort, and sort based on it.

Another solution (if your language supports it) is to have an associative array from month names to numbers (1..12) and use a custom comparator running sort on your array.

Solution in Perl :D

my @mon = qw( January February March April May June July August September October November December );
my $mon;
@{$mon}{@mon} = (0..$#mon);

sub by_month {
    $mon->{$a} <=> $mon->{$b};
}

sort by_month @data_to_sort

(although I'm sure a golfer could do that in < 30 characters)

And here's a solution in plain C : http://www.pnambic.com/CPS/SortAnal/html/MonOrder.html

Answer 4

Talking from a Java POV, I'm going to pimp (as I often do) google-collections (soon to be replaced with Guava):

Arrays.sort(myMonths, Ordering.explicit("Jan", "Feb", "Mar", ....));

... and you're done.

Don't write it yourself if someone else has done it, probably more efficiently and with a nicer API than you probably would.

Not helpful in the general case, but just in case any Java folk have the same problem...

Answer 5

Colleagues,

I see the issue/business problem lasts more than 2 year. I decided to write comparator for sorting months' names (stored as strings) properly. It also holds names of the months for desired locale ============== Comparator =======================

import java.text.SimpleDateFormat;
import java.util.ArrayList;
import java.util.Calendar;

import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Locale;
import java.util.Map;

/**
 *
 * @author akashtalyan
 */
public class MonthNamesComparator implements Comparator {

    private static Map<Locale, List> monthMap = new HashMap<Locale, List>();
    private final Locale locale;

    public MonthNamesComparator(Locale locale) {
        if (locale == null) {

            throw new NullPointerException("MonthNamesComparator cannot accept null value for Locale parameter.");
        }
        List months = new ArrayList(12);
        Calendar cal = Calendar.getInstance(locale);
        SimpleDateFormat dateFormat = new SimpleDateFormat("MMMM", locale);
        this.locale = locale;
        if (!monthMap.containsKey(locale)) {
            for (int i = 0; i < 12; i++) {
                cal.set(Calendar.MONTH, i);
                months.add(dateFormat.format(cal.getTime()).toLowerCase());
            }
            monthMap.put(locale , months);
        }
    }

    @Override
    public int compare(Object month1, Object month2) {
        List months = monthMap.get(this.locale);
        if (months == null) {
            throw new NullPointerException("MonthNamesComparator cannot perform comparison - internal data is not initialized properly.");
        }
        return (months.indexOf(((String) month1).toLowerCase()) - months.indexOf(((String) month2).toLowerCase()));

    }
}

And simple test class to POC:

import java.util.Locale;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;

/**
 *
 * @author akashtalyan
 */
public class TestMonths {
    public static void main(String[] args){
        Locale en = Locale.ENGLISH, ru = new Locale("ru","RU");
        String[] monthsToTestEn = new String[] {"FebRUary", "maY", "sepTember", "january", "december"};
        String[] monthsToTestRu = new String[] {"АпреЛь", "январь", "Март", "Август"};

        Map map = new TreeMap(new MonthNamesComparator(en));
        int i = 0;
        System.out.println("En Map original:");
        for (String month : monthsToTestEn) {
            System.out.print(month + " ");
            map.put(month, new StringBuilder(String.valueOf(++i)).append(" position in source array").toString());
        }
            System.out.println();
            System.out.println("En Map sorted:");
        for (String month : (Set<String>)map.keySet()) {
            System.out.println(month + " " + map.get(month));
        }
        i = 0;
        map = new TreeMap(new MonthNamesComparator(ru));
        System.out.println("Ru Map original:");
        for (String month : monthsToTestRu) {
            System.out.print(month + " ");
            map.put(month, new StringBuilder(String.valueOf(++i)).append(" position in source array").toString());
        }
            System.out.println();
        System.out.println("Ru Map sorted:");
        for (String month : (Set<String>)map.keySet()) {
            System.out.println(month + " " + map.get(month));
        }
    }

}

Enjoy it, works like a charm.

Answer 6

Create a mapping:

month_map = {"January":1,
             "February":2,
             "March":3,
             "April":4} # etc..

Use the mapping to compare one month to the other.

OR

Most languages/frameworks have objects for handling dates. Create date objects for all the months and compare them using the native (if available) inequality operators or basic sorting functions:

import datetime
January  = datetime.date(2010,1,1)
February = datetime.date(2010,2,1)
if February < January: print("The world explodes.")

Answer 7

Thanks all for the suggestions, I would like to mark you all as accepted.

Here's the resulting code:

// correct order 
months as String[] = ["jan", "feb", "mar", "apr", "may", "jun",
                      "jul", "aug", "sep", "oct", "nov", "dec"]
// my unsorted months 
myMonths as String[] = ["mar", "dec", "jul", "jan", "sep"]

// poor substitute for Map
mappedIndex as Int[]

// create an array with the corresponding index 
for each m in myMonths do
    i as Int = 0;
    for each month in months do 
       if m == month then 
           mappedIndex[] = i // no break, so I should use "else"
       else
          i = i + 1
       end
    end
end

// At this point mapped index has the same order as my "unsorted" array
// in this case [2,11,5,0,8]

// Fortunately this language has "sort" otherwise I would jump out of the window
mappedIndex.sort()

// create a new array to hold the sorted values
myMonthsSorted as String[]

// and fill it with the correct value
for each i in mappedIndex do 
   myMonthsSorted[] = months[i]
end

Answer 8

For something like months, I'd just hard-code the arrays I needed...

var correctOrdering = {
    english: ["January", "February", "March", ...],
    french: ["Janvier", "Février", "Mars", ...],
    russian: ["Январь", "февраль", "март"],
    ...
};

It's not like month names are going to change any time soon.

Answer 9

tl;dr

EnumSet.of( Month.JANUARY , Month.MARCH , Month.OCTOBER , Month.DECEMBER ).toString()

Enum

If your language provides a powerful enum facility as does Java, define a dozen objects. See Oracle Tutorial.

java.time.Month

The java.time classes include the handy Month enum, defining a dozen objects one for each month of the year January-December.

They are numbered 1-12, and defined in proper order, January to December.

In your code base, use objects of this enum to replace any use of mere integers or use of name-of-month strings. Using Month objects throughout provides type-safety, ensures valid values, and makes your code more self-documenting.

In Java, the EnumSet and EnumMap are implementations of Set and Map that are optimized for enum values. They execute very quickly and take very little memory.

EnumSet<Month> months = EnumSet.of( Month.JANUARY , Month.MARCH , Month.OCTOBER , Month.DECEMBER );

The EnumSet iterates in natural order, the order in which the enum constants are declared. So no need to explicitly sort your collection.

The class includes a getDisplayName method for generating a localized String of the name of the month. Specify a TextStyle for how long or abbreviated you want the text. And specify a Locale for (a) the human language to use in translation, and (b) the cultural norms to decide issues such as abbreviation, punctuation, and capitalization.

for( Month month : months ) {
    String output = month.getDisplayName( TextStyle.SHORT_STANDALONE , Locale.CANADA_FRENCH );  // Or Locale.US, Locale.ITALY, etc.
    System.out.println( output );
}

Answer 10

Add a prefix for each month:

Jan -> aJan
Feb -> bFeb
...

Sort, then remove the prefix.