Using mergesort to sort lexicographically

Question

The program should (and does) the following (paraphrased assignment):

There is a catalogue with a list of motorcycles.
They have a
- Name (spaceless string of 20 chars)
- Price (int < 99 999 999)
- Weight (int < 99 999 999)
- Speed (int < 99 999 999)

I have to output two lists, the first list is ordered lexicographically by price, speed, weight and then name. The second list is ordered by speed, weight, price and then name. The input is first an integer n, followed by n lines of motorcycles. You have to use mergesort.

An example input:
4 // Name, price, speed, weight
Harley 7000 180 240
Yamaha 3000 150 100
Ford 10000 110 240
Jawa 3000 150 240

Output: 4
Yamaha Ford
Jawa Yamaha
Harley Jawa
Ford Harley

The actual output is outlined, so that the second list always has 21 characters preceding it.

Here is my code:

I read place the inputs into two jagged arrays, and the strings into a separate array. The elements of the first (integer) array are [price, speed, weight, id], and the second (integer) array [speed, weight, price, id]. Since I do not sort the nameList, I need to keep track of which element belongs to which name. I do this using a unique id.

static void Main(string[] args)
{
    int n = Convert.ToInt32(Console.ReadLine().Split()[0]);
    int[][] motorProperties = new int[n][]; //[price, speed, weight, id]
    int[][] motorPropertiesSpeedFirst = new int[n][]; //[speed, weight, price, id]
    string[] motorNames = new string[n];

    //import inputs
    for(int i = 0; i < n; i++)
    {
        string inputLine = Console.ReadLine();
        //Element of motorProperties
        int[] temp = new int[4];

        //Element of motorPropertiesSpeedFirst
        int[] temp2 = new int[4];

        motorNames[i] = inputLine.Split()[0];

        temp[0] = Convert.ToInt32(inputLine.Split()[1]);
        temp[1] = Convert.ToInt32(inputLine.Split()[2]);
        temp[2] = Convert.ToInt32(inputLine.Split()[3]);
        temp[3] = i; //unique id, so name can be traced after sorting

        temp2[0] = temp[1];
        temp2[1] = temp[2];
        temp2[2] = temp[0];
        temp2[3] = i; //unique id, so name can be traced after sorting

        motorProperties[i] = temp;
        motorPropertiesSpeedFirst[i] = temp2;
    }

    //Sort arrays using merge sort.
    mergeSort(motorProperties, motorNames, 0, motorProperties.Length - 1);
    mergeSort(motorPropertiesSpeedFirst, motorNames, 0, motorProperties.Length - 1);

    //Gives output in desired form
    Console.WriteLine(n);
    for(int i = 0; i < n; i++)
    {
        string name1 = motorNames[motorProperties[i][3]];
        string name2 = String.Concat(Enumerable.Repeat(" ", 21 - name1.Length)) + motorNames[motorPropertiesSpeedFirst[i][3]];
        Console.WriteLine(name1 + name2);
    }

    Console.ReadLine();
}

Then for the merge sort logic:

static void mergeSort(int[][] arr, string[] motorNames, int startIndex, int endIndex)
{
    if(startIndex < endIndex)
    {
        int middle = (startIndex + endIndex) / 2;
        mergeSort(arr, motorNames, startIndex, middle);
        mergeSort(arr, motorNames, middle + 1, endIndex);
        merge(arr, motorNames, startIndex, middle, endIndex);
    }
}


static void merge(int[][] arr, string[] motorNames, int startIndex, int middle, int endIndex)
{
    //This merge sorts creates two arrays of approximately the same size
    //Then takes all elements in the main array left of the middle, and puts them into the leftArray
    //Likewise, we add all elements from the right of the middle into the rightArray
    int lengthLeftArray = middle - startIndex + 1;
    int lengthRightArray = endIndex - middle;

    //left and right array with extra element for sentinel card
    int[][] leftArray = new int[lengthLeftArray + 1][]; 
    int[][] rightArray = new int[lengthRightArray + 1][]; 

    //puts everything before middle into left array, and the rest in right array
    for (int i = 0; i < lengthLeftArray; i++)
    {
        leftArray[i] = arr[startIndex + i];
    }

    for(int i = 0; i < lengthRightArray; i++)
    {
        rightArray[i] = arr[middle + i +1];
    }

    //sentinel cards
    leftArray[lengthLeftArray] = new int[] { int.MaxValue};
    rightArray[lengthRightArray] = new int[] { int.MaxValue};


    int indexLeftArray = 0;
    int indexRightArray = 0;

    //Compare elements from leftArray and rightArray
    //Add the smaller one to the main array.
    for(int i = startIndex; i <= endIndex; i++)
    {
        for(int j = 0; j < 4; j++)
        {   
            if(j < 3)
            {
                if (leftArray[indexLeftArray][j] < rightArray[indexRightArray][j])
                {
                    arr[i] = leftArray[indexLeftArray];
                    indexLeftArray++;
                    break;
                }
                else if (leftArray[indexLeftArray][j] > rightArray[indexRightArray][j])
                {
                    arr[i] = rightArray[indexRightArray];
                    indexRightArray++;
                    break;
                }
                else
                {
                    continue;
                }
            }

            //Compares how the names of motorcycles should be ordered. 
            //Since speed, weight, price is the same
            else
            {
                string nameMotor1 = motorNames[leftArray[indexLeftArray][j]];
                string nameMotor2 = motorNames[rightArray[indexRightArray][j]];

                //if < 0 => motor 1 comes first alphabetically. = 0 => same names. > 0 motor 2 comes first alphabetically.
                int test = String.Compare(nameMotor1, nameMotor2 , true);
                if(test <= 0)
                {
                    arr[i] = leftArray[indexLeftArray];
                    indexLeftArray++;
                    break;
                }
                else
                {
                    arr[i] = rightArray[indexRightArray];
                    indexRightArray++;
                    break;
                }
            }
        }               
    }
}

My program runs in 8.3 seconds (multiple input tests -dumjudge). Some people have gotten it to run as fast as 3 seconds though. So I'm wondering where my program loses most time, and what changes I could implement to make it run faster.

I was thinking of perhaps using linked list, though I wouldn't be sure how to store multiple integers into one node, and then sorting by it. And I wasn't sure whether that would actually be faster.

Answer 1

You seem to have some confusion about how to use Split. Since it creates an array of string, your best option is to assign that array to a variable.

For instance if your original data is in an array it could look something like this:

string[] temp = data[i].Split();

This is where having a class comes in very handy. You can use the resulting array as it is, as a collection of arguments for a constructor for your class:

public Motorcycle(params String[] args)
{
    _name = args[0];
    if(!int.TryParse(args[1],out _price))
    {
        throw new ArgumentException($"parameter index 1 will not parse to int.  Value is {args[1]}.");
    }
    if (!int.TryParse(args[2], out _speed))
    {
        throw new ArgumentException($"parameter index 2 will not parse to int.  Value is {args[2]}.");
    }
    if (!int.TryParse(args[3], out _weight))
    {
        throw new ArgumentException($"parameter index 3 will not parse to int.  Value is {args[3]}.");
    }
}

As for sorting. My thought was to create an enum of the properties:

enum Properties
{
    Name,
    Price,
    Speed,
    Weight
}

Now with a list of these properties you can iterate through it and using a switch block do the comparisons needed for a CompareTo method.

public int CompareTo(Motorcycle other)
{
    foreach (var p in sortOrders[_compareOrder])
    {
        switch (p)
        {
            case Motorcycle.Properties.Price:
                {
                    if (Price == other.Price)
                    {
                        continue;
                    }
                    return Price.CompareTo(other.Price);
                }
            case Motorcycle.Properties.Speed:
                {
                    if (Speed == other.Speed)
                    {
                        continue;
                    }
                    return Speed.CompareTo(other.Speed);
                }
            case Motorcycle.Properties.Weight:
                {
                    if (Weight == other.Weight)
                    {
                        continue;
                    }
                    return Weight.CompareTo(other.Weight);
                }
            case Motorcycle.Properties.Name:
                {
                    if (Name == other.Name)
                    {
                        continue;
                    }
                    return Name.CompareTo(other.Name);
                }
        }
    }
    return 0;
}

A 2D list of Properties allows you to have different ways of sorting. A static variable to hold the index can be used. Simply change it to point to a different list, for a different comparison.

At this point you can use this method in your sort method to compare 2 Motorcycles. My thought is go one step further and overload the comparison operators. This will simplify your sort method since it will be able to use > or < or == or != and any comparisons will be done according to the sort order that you've specified:

public static bool operator ==(Motorcycle a, Motorcycle b) => a.CompareTo(b) == 0;
public static bool operator !=(Motorcycle a, Motorcycle b) => a.CompareTo(b) != 0;
public static bool operator >(Motorcycle a, Motorcycle b) => a.CompareTo(b) == 1;
public static bool operator <(Motorcycle a, Motorcycle b) => a.CompareTo(b) == -1;

When it's all put together it could look like this:

class Motorcycle:IComparable<Motorcycle>
{
    string _name = "";
    int _speed = 0;
    int _price = 0;
    int _weight = 0;
    static int _compareOrder = 0;
    public string Name
    {
        get { return _name; }
        private set{_name = value;}
    }
    public int Speed
    {
        get { return _speed; }
        private set { _speed = value; }
    }
    public int Price
    {
        get { return _price; }
        private set { _price = value; }
    }
    public int Weight
    {
        get { return _weight; }
        private set { _weight = value; }
    }
    public static int CompareOrder
    {
        private get { return _compareOrder; }
        set
        {
            if(value >= 0 && value < sortOrders.Count)
            {
                _compareOrder = value;
            }
            else
            {
                throw new ArgumentOutOfRangeException($"Value must be between 0 and {sortOrders.Count - 1}, inclusive. Value entered is {value}.");
            }
        }
    }
    enum Properties
    {
        Name,
        Price,
        Speed,
        Weight
    }
    static readonly List<List<Properties>> sortOrders = new List<List<Properties>>()
    {
        new List<Properties>(){Properties.Price, Properties.Speed, Properties.Weight, Properties.Name },
        new List<Properties>(){Properties.Speed, Properties.Weight, Properties.Price, Properties.Name},
    };

    public Motorcycle(){}
    public Motorcycle(string name, int price, int speed, int weight)
    {
        _name = name;
        _speed = speed;
        _price = price;
        _weight = weight;
    }
    public Motorcycle(params String[] args)
    {
        _name = args[0];
        if(!int.TryParse(args[1],out _price))
        {
            throw new ArgumentException($"parameter index 1 will not parse to int.  Value is {args[1]}.");
        }
        if (!int.TryParse(args[2], out _speed))
        {
            throw new ArgumentException($"parameter index 2 will not parse to int.  Value is {args[2]}.");
        }
        if (!int.TryParse(args[3], out _weight))
        {
            throw new ArgumentException($"parameter index 3 will not parse to int.  Value is {args[3]}.");
        }
    }
    public override string ToString()
    {
        return _name;
    }
    public override int GetHashCode() => $"{_name}{_price}{_speed}{_weight}".GetHashCode();
    public override bool Equals(object obj) => this == (Motorcycle)obj;
    public static bool operator ==(Motorcycle a, Motorcycle b) => a.CompareTo(b) == 0;
    public static bool operator !=(Motorcycle a, Motorcycle b) => a.CompareTo(b) != 0;
    public static bool operator >(Motorcycle a, Motorcycle b) => a.CompareTo(b) == 1;
    public static bool operator <(Motorcycle a, Motorcycle b) => a.CompareTo(b) == -1;
    public int CompareTo(Motorcycle other)
    {
        foreach (var p in sortOrders[_compareOrder])
        {
            switch (p)
            {
                case Motorcycle.Properties.Price:
                    {
                        if (Price == other.Price)
                        {
                            continue;
                        }
                        return Price.CompareTo(other.Price);
                    }
                case Motorcycle.Properties.Speed:
                    {
                        if (Speed == other.Speed)
                        {
                            continue;
                        }
                        return Speed.CompareTo(other.Speed);
                    }
                case Motorcycle.Properties.Weight:
                    {
                        if (Weight == other.Weight)
                        {
                            continue;
                        }
                        return Weight.CompareTo(other.Weight);
                    }
                case Motorcycle.Properties.Name:
                    {
                        if (Name == other.Name)
                        {
                            continue;
                        }
                        return Name.CompareTo(other.Name);
                    }
            }
        }
        return 0;
    }
}

Now you can rework and simplify your sorting method and it will be easier to follow your logic. This will aid in debugging it.

You'll notice that I added the ToString overload. This will allow Console.Write to print out the Name of a Motorcycle object without specifically calling the property.

Answer 2

• You duplicated all your input data in order to have two different sort orders, which is a strong indicative that you're doing something strange
• You abused primitive types, which makes the code less readable
• You implemented an iterative mergesort, which a good thing and has its advantages, but I find declarative mergesort way more elegant, especially in such a small program
• You called Split many times, you should call it 1 time and store the result into a variable

Rewriting your program I:

• Created a class to represent the motorcycle
• Changed the mergesort algorithm to a more declarative style
• Simplified the logic for input data
• Used an anonymous method (in the form of a lambda function) to abstract the comparison logic

The result is...

public class Motorcycle
{
    public string Name { get; set; }
    public int Price { get; set; }
    public int Speed { get; set; }
    public int Weight { get; set; }
}

class Program
{
    static void Main(string[] args)
    {
        var n = int.Parse(Console.ReadLine());
        var motorcycles = new List<Motorcycle>();

        for (var i = 0; i < n; i++)
        {
            var splitedLine = Console.ReadLine().Split();

            motorcycles.Add(new Motorcycle
            {
                Name = splitedLine[0],
                Price = int.Parse(splitedLine[1]),
                Speed = int.Parse(splitedLine[2]),
                Weight = int.Parse(splitedLine[3])
            });
        }

        var perPrice = Sort(motorcycles, (a, b) =>
        {
            return
                a.Price != b.Price ? a.Price > b.Price :
                a.Speed != b.Speed ? a.Speed > b.Speed :
                a.Weight != b.Weight ? a.Weight > b.Weight :
                a.Name != b.Name ? a.Name.CompareTo(b.Name) == 1 :
                false;
        });

        var perSpeed = Sort(motorcycles, (a, b) =>
        {
            return
                a.Speed != b.Speed ? a.Speed > b.Speed :
                a.Weight != b.Weight ? a.Weight > b.Weight :
                a.Price != b.Price ? a.Price > b.Price :
                a.Name != b.Name ? a.Name.CompareTo(b.Name) == 1 :
                false;
        });

        Console.WriteLine(n);

        for (var i = 0; i < n; i++)
        {
            Console.WriteLine(perPrice.ElementAt(i).Name + "\t\t" + perSpeed.ElementAt(i).Name);
        }

        Console.ReadLine();
    }

    public static IEnumerable<T> Sort<T>(IEnumerable<T> items, Func<T, T, bool> isGreater)
    {
        if (items.Count() <= 1)
        {
            return items;
        }

        var fstHalf = Sort(items.Take(items.Count() / 2), isGreater);
        var sndHalf = Sort(items.Skip(items.Count() / 2), isGreater);

        return Merge(fstHalf, sndHalf, isGreater);
    }

    public static IEnumerable<T> Merge<T>(IEnumerable<T> items1, IEnumerable<T> items2, Func<T, T, bool> isGreater)
    {
        var merged = new List<T>();
        var counter1 = 0;
        var counter2 = 0;

        while (counter1 < items1.Count() && counter2 < items2.Count())
        {
            if (isGreater(items1.ElementAt(counter1), items2.ElementAt(counter2)))
            {
                merged.Add(items2.ElementAt(counter2++));
            }
            else
            {
                merged.Add(items1.ElementAt(counter1++));
            }
        }

        while (counter1 < items1.Count())
        {
            merged.Add(items1.ElementAt(counter1++));
        }

        while (counter2 < items2.Count())
        {
            merged.Add(items2.ElementAt(counter2++));
        }

        return merged;
    }
}

There are some "optimizations" one could make in my program (e.g. calling less methods) but it wouldn't make any noticeable difference.

Answer 3

That code is hard to read.

Why are you performing the .Split() multiple times?

Use objects and implement IComparable

    public class Motorcycle : IComparable
    {
        public string Name { get; }
        public int Speed { get; }
        public int Price { get; }
        public bool SpeedFirstSort { get; set; }
        public int CompareTo(object obj)
        {
            if (obj == null) return 1;

            Motorcycle otherMotorcycle = obj as Motorcycle;
            if (otherMotorcycle != null)
            {
                if(SpeedFirstSort)
                {
                    if(this.Speed == otherMotorcycle.Speed)
                    {
                        return (this.Price.CompareTo(otherMotorcycle.Price));
                    }
                    else
                    {
                        return (this.Speed.CompareTo(otherMotorcycle.Speed));
                    }
                }
                else
                {
                    if (this.Price == otherMotorcycle.Price)
                    {
                        return (this.Speed.CompareTo(otherMotorcycle.Speed));
                    }
                    else
                    {
                        return (this.Price.CompareTo(otherMotorcycle.Price));
                    }
                }
            }
            else
            {
                throw new ArgumentException("Object is not a otherMotorcycle");
            }
        }
        public Motorcycle(string name, int price, int speed, bool speedFirstSort = true)
        {
            Name = name;
            Price = price;
            Speed = speed;
        }
    }

You don't have to implement IComparable. You could pass a Comparison Delegate.