Array member set its own index in the array

Question

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; } } } 

Answer 1

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 .