Tuesday, July 11, 2017

Sort the odd numbers in array

Given an array of numbers, it is required to sort ascending odd numbers but even numbers must be on their places.

ex:
{ 5, 3, 2, 8, 1, 4 } should give { 1, 3, 2, 8, 5, 4 }
{ 5, 3, 1, 8, 0 } should give { 1, 3, 5, 8, 0 }

Algorithm:
define sorted list
define another list to save the odd number indexes
Iterate through the array for each item
     if item is even skip it
     if item is odd:
           add it to the sorted list
           add the item index to indexes list
loop through the indexes list, for each index
     save the item from the sorted list into the the numbers array at the that index

Note: the sorted list should support duplicate items

Example implementations

Using a list

using System;
using System.Collections.Generic;
using System.Linq;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace sortOdd
{
    public class Program
    {
        static void Main(string[] args)
        {
            CollectionAssert.AreEqual(new int[] { 1, 3, 2, 8, 5, 4 }, Program.SortArray(new int[] { 5, 3, 2, 8, 1, 4 }));
            CollectionAssert.AreEqual(new int[] { 1, 3, 5, 8, 0 }, Program.SortArray(new int[] { 5, 3, 1, 8, 0 }));
            CollectionAssert.AreEqual(new int[] { }, Program.SortArray(new int[] { }));
        }

        public static int[] SortArray(int[] array)
        {
            var result = new int[array.Length];
            List<int> sortedOdd = new List<int>();
            var indexes = new List<int>();
            for (int i = 0; i < array.Length; i++)
            {
                if (array[i]%2 == 0)
                    result[i] = array[i];
                else
                {
                    int index = sortedOdd.BinarySearch(array[i]);
                    if (index < 0)
                        sortedOdd.Insert(~index, array[i]);
                    else
                        sortedOdd.Insert(index, array[i]);
                    indexes.Add(i);
                }
            }
            for (int i = 0; i < indexes.Count; i++)
            {
                result[indexes.ElementAt(i)] = sortedOdd.ElementAt(i);
            }
            return result;
        }
    }
}

Using sorted list 

using System;
using System.Collections.Generic;
using System.Linq;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace sortOdd
{

    public class Program
    {
        static void Main(string[] args)
        {
            CollectionAssert.AreEqual(new int[] { 1, 3, 2, 8, 5, 4 }, Program.SortArray(new int[] { 5, 3, 2, 8, 1, 4 }));
            CollectionAssert.AreEqual(new int[] { 1, 3, 5, 8, 0 }, Program.SortArray(new int[] { 5, 3, 1, 8, 0 }));
            CollectionAssert.AreEqual(new int[] { }, Program.SortArray(new int[] { }));
        }

        public static int[] SortArray(int[] array)
        {
            var result = new int[array.Length];
            var sortedOdd = new SortedSet<int>(new DuplicateKeyComparer<int>());
            var indexes = new List<int>();
            for (int i = 0; i < array.Length; i++)
            {
                if (array[i]%2 == 0)
                    result[i] = array[i];
                else
                {
                    sortedOdd.Add(array[i]);
                    indexes.Add(i);
                }
            }
            for (int i = 0; i < indexes.Count; i++)
            {
                result[indexes.ElementAt(i)] = sortedOdd.ElementAt(i);
            }
            return result;
        }
    }

    public class DuplicateKeyComparer<TKey>:IComparer<TKey> where TKey : IComparable
    {
        public int Compare(TKey x, TKey y)
        {
            int result = x.CompareTo(y);

            if (result == 0)
                return 1;  
            return result;
        }
    }
}

No comments:

Post a Comment