0
\$\begingroup\$

I'm writing a code where a class member, if != -1, set its own position at array. If the value is == -1, the next free index (whose range is 0 too array's length) is used. In this review, I'm more interested in the algorithm, making it faster, accurate and readable than anything else. despite I'm using C#, I'd like to keep it simple, C-like and avoid C#'s stuff like Linq, etc. If there's a readable and faster way to do that without the valueSet flag, would be nice. I just added it because after the swap() call, the swapped elements would be visited twice, with value != -1, making it to be set again, wrongly. Let me know if there's anything that's not clear. Below the code with some functions that acts like unittests. Complete different ways to do that are also very welcome.

UPDATE:

  1. the index range is 0 to arr.Length. Anything outside this bounds is wrong.
  2. The indexes are linear and sequential, so for each i in arr, this must be true arr[x] + 1 == arr[x + 1]
  3. null storage isn't allowed

;

using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace sort
{
    class Program
    {
        static void Main(string[] args)
        {
            t1();
            t2();
            t3();
            t4();
        }

        //test case 1
        static void t1()
        {
            var arr = new List<A>();
            arr.Add(new A(-1, "a"));
            arr.Add(new A(-1, "b"));
            arr.Add(new A(0, "c"));
            arr.Add(new A(-1, "d"));

            var sortedArr = doSort(arr.ToArray());
            Debug.Assert(isSorted(sortedArr));
        }

        // test case 2
        static void t2()
        {
            var arr = new List<A>();
            arr.Add(new A(-1, "a"));
            arr.Add(new A(-1, "b"));
            arr.Add(new A(-1, "c"));
            arr.Add(new A(-1, "d"));

            var sortedArr = doSort(arr.ToArray());
            Debug.Assert(isSorted(sortedArr));
        }

        // test case 3
        static void t3()
        {
            var arr = new List<A>();
            arr.Add(new A(0, "a"));
            arr.Add(new A(1, "b"));
            arr.Add(new A(2, "c"));
            arr.Add(new A(3, "d"));

            var sortedArr = doSort(arr.ToArray());
            Debug.Assert(isSorted(arr.ToArray()));
        }

        static void t4()
        {
            var arr = new List<A>();
            arr.Add(new A(-1, "a"));
            arr.Add(new A(1, "b"));
            arr.Add(new A(0, "c"));
            arr.Add(new A(-1, "d"));

            var sortedArr = doSort(arr.ToArray());
            Debug.Assert(isSorted(sortedArr));
        }

        // not meant to be very fast just to be used in the "unittest"
        static bool isSorted(A[] arr)
        {
            if(arr.Length == 0)
            {
                return false;
            }

            // this make sure the values is sequential, starting with 0
            // and the last value must be same value as array's length
            if(arr[0].index != 0 || arr[arr.Length - 1].index != arr.Length - 1)
            {
                return false;
            }

            // we have checked already if the first and last values
            // are sequential, no need to recheck here so
            // we loop from 1 to arr.length - 1
            for (int i = 1; i < arr.Length - 1; i++)
            {
                if(i + 1 > arr.Length &&
                  arr[i].index + 1 != arr[i + 1].index)
                {
                    return false;
                }
            }

            return true;
        }

        static A[] doSort(A[] arr)
        {
            for(int i = 0; i < arr.Length; i++)
            {
                initValue(arr, i);
            }

            return arr;
        }

        static void initValue(A[] arr, int i)
        {
            var e = arr[i];

            if(e.valueSet)
            {
                return; /* nothing to do, value initialized already */
            }

            // initialize to current index
            if(e.index == -1)
            {
                e.index = i;
            }
            // an explicit index was set, the value at i index
            // must be set to the value at e.index index
            else if(e.index != i)
            {
                swap(arr, i, e.index);
                // after the swap, that element may be left
                // unitialized. Do initialize now.
                initValue(arr, i);
            }

            e.valueSet = true;
        }

        static void swap(A[] arr, int i, int j)
        {
            // swap items
            var t = arr[i];
            arr[i] = arr[j];
            arr[j] = t;

            // update indexes
            arr[i].index = i;
            arr[j].index = j;
        }
    }

    class A
    {
        public A(int i, string s)
        {
            index = i;
            value = s;
        }

        public override string ToString()
        {
            return string.Format("index = {0}, value = {1}", index, value);
        }

        public int index { get; set; }
        public string value { get; set; }
        public bool valueSet { get; set; }
    }
}
\$\endgroup\$
10
  • \$\begingroup\$ Is arr.Add(new A(0, "aaa")); arr.Add(new A(0, "bbb")); a wrong input? How sorting method must behave with such input? arr.Add(null)? arr.Add(new A(-456, "ccc"))? arr.Add(new A(int.MaxValue, "ddd"))? I'm not suggesting to fix it now but asking, what's the idea for these test cases? \$\endgroup\$ – aepot Mar 30 at 20:08
  • 1
    \$\begingroup\$ @Jack If you would like to improve on legibility then the bear minimum would be to use better naming than A, e, arr, t, etc. \$\endgroup\$ – Peter Csala Mar 31 at 6:52
  • 1
    \$\begingroup\$ Welcome to Code Review@SE. Please heed How do I ask a Good Question?, starting with providing more context: where do the indices specified stem from, how is the result going to be used? \$\endgroup\$ – greybeard Mar 31 at 10:05
  • 1
    \$\begingroup\$ @aepot Duplicate cases can be ignored. At time index is set the value it can have is from 0 to arr.Length. arr.Add(null) isn't allowed, we can throw an exception. -456 and int.MaxValue are out of the 0 .. arr.Length length I mentioned so outOfRangeException would be throw \$\endgroup\$ – Jack Apr 1 at 14:53
  • 2
    \$\begingroup\$ Welcome to Code Review! After getting an answer you are not allowed to change your code anymore. This is to ensure that answers do not get invalidated and have to hit a moving target. Refer to this post for more information \$\endgroup\$ – Sᴀᴍ Onᴇᴌᴀ Apr 1 at 17:13
0
\$\begingroup\$

Review

  • In your test cases, why not use array directly (new A[] { new A(-1, "a"), new A(-1, "b"), new A(0, "c"),... };) instead of List<A>.ToArray()?

  • In the part of isSorted method, do you expect that the return value is false if (arr.Length == 0)? Or ArgumentException Class can be used here.

  • In class A, maybe Dictionary<TKey,TValue> Class can be used here. Make TKey is index and TValue is string .

\$\endgroup\$
1
  • \$\begingroup\$ Keys are immutable in Dictionary. The code is modifying indexes. \$\endgroup\$ – aepot Mar 30 at 23:35

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.