1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Is there any reason you are using multidimensional arrays instead of types with strong properties? Btw. your code uses such poor names that it's extremely hard to read. \$\endgroup\$ – t3chb0t Jun 3 '18 at 15:02
  • \$\begingroup\$ I'm not familiar with types with strong properties. Not by name anyway. \$\endgroup\$ – PaRaXeRoX Jun 3 '18 at 16:39
  • \$\begingroup\$ What are some of the names that are really unclear? I will change them to better ones, to make my code more readable. \$\endgroup\$ – PaRaXeRoX Jun 3 '18 at 16:53
  • \$\begingroup\$ I give up. You still have 4 Split(). \$\endgroup\$ – paparazzo Jun 3 '18 at 19:32
  • \$\begingroup\$ Besides actually implementing a class, like your example. How could I avoid using those splits? The exercise demands the use of mergesort. And the data input is a line of a string, followed by integers ( as I explained in my original post), how then would I add them to my array, if not for split? \$\endgroup\$ – PaRaXeRoX Jun 3 '18 at 20:43
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I find each of the switch cases should be it's own class implementing the IComparer<T> interface so that you can easily pass it to OrderBy. \$\endgroup\$ – t3chb0t Jun 5 '18 at 6:05
  • \$\begingroup\$ @t3chb0t - That is definitely an option. but, since the OP's question is dealing specifically with a custom sorting algorithm, that, to me would be going kind of astray from the point. Also, wouldn't OrderBy just use the the properties themselves, in whatever order is desired? \$\endgroup\$ – tinstaafl Jun 5 '18 at 6:10
  • \$\begingroup\$ How do you mean the properties themselves? That's what the IComparar<T> is for. So that you can implement your custom sorting logic. \$\endgroup\$ – t3chb0t Jun 5 '18 at 6:16
  • 2
    \$\begingroup\$ @t3chb0t - By chaining the OrderBy and ThenBy you will create a custom sort for whatever weight you put on each property.motorcycles.OrderBy(m => m.Speed).ThenBy(m => m.Price).ThenBy(m => m.Weight).ThenBy(m => m.Name) \$\endgroup\$ – tinstaafl Jun 5 '18 at 6:23
1
\$\begingroup\$
  • 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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I see, what could I do to improve readability? \$\endgroup\$ – PaRaXeRoX Jun 3 '18 at 16:25
  • \$\begingroup\$ Regarding split. I read each line as a large string. Then I obtain each part of the string, which represent a single property, using split. How should I do it otherwise? \$\endgroup\$ – PaRaXeRoX Jun 3 '18 at 16:26
  • \$\begingroup\$ You don't think Motorcycle is more readable than int[][] motorList. Do you need to .Split() 6 times? \$\endgroup\$ – paparazzo Jun 3 '18 at 16:28
  • \$\begingroup\$ Oh right. That's actually a brain fart. That's unnecessary, I needed to add each element to different temp arrays. So I blindly applied split twice, I could do it only once. \$\endgroup\$ – PaRaXeRoX Jun 3 '18 at 16:33
  • \$\begingroup\$ I must use merge sort, your code doesn't seem to use it? And yeah, motorcycle is more readable \$\endgroup\$ – PaRaXeRoX Jun 3 '18 at 16:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.