Minimum Swaps 2

  • + 0 comments
        // Intialize the Minimum Swaps Counter
        int swaps = 0;
    
        // Push all values in the Array to a List for Monitoring purposes
        // This List will be updated as and when the array elements get processed
        List<int> arrList = new List<int> (arr);
    
        // Create a List of Dictionaries for the previous index mapping to the new index
        List<Dictionary<int,int>> dictList = new List<Dictionary<int, int>>{};
    
        // Loop over all the elements in the Array
        // The List of Array elements will be checked here till any Array elements exist
        while (arrList.Count != 0)
        {
            // Find the index of the first element of the List from the Array
            var i = Array.IndexOf(arr, arrList[0]);
    
            // Initiate the Dictionary object that will be added to the Tracker List
            Dictionary<int, int> dict = new Dictionary<int, int>{};
            dictList.Add(dict);
    
            // Check if the Element is at the correct place
            while (arr[i] != i+1 && !dict.ContainsKey(i))
            {
                // Element not at correct place
                // Find the correct place of the element
                int newIndex = arr[i]-1;
    
                // Add the previous index mapped to the new index to the dictionary
                dict[i] = newIndex;
    
                // Remove the traversed index from the Array List
                arrList.Remove(arr[i]);
    
                // Continue with the next Index
                i = newIndex;
            }
    
            // Remove the last traversed index from the Array List
            arrList.Remove(arr[i]);
    
            // Check the Dictionary Keys created so far
            foreach (var k in dict.Keys)
            {
                Console.WriteLine("{0} --> {1}", k, dict[k]);
            }
    
            // Update the Minimum Swaps needed so far
            if (dict.Keys.Count != 0) { swaps = swaps + dict.Keys.Count-1; };
    
            Console.WriteLine();           
    
        // Return the Minimum Swaps Counter
        return swaps;
    }