Single swap can sort the array?

Program to check if a single swap can sort the array

Solution :

1. Find the first left incorrect position;
2. Find first right side incorrect position;
3. Swap elements;
4. Check if array is sorted , if not, return false;

public static bool SingleSwapSortArray(int[] input)
{
    int leftIndex = FindLeftIndex(input);
    int rightIndex = FindRightIndex(input);
    if (leftIndex == rightIndex || leftIndex == -1 || rightIndex == -1)
    {
        return false; // check these edge cases just to be on safe side.
    }                
    Swap(input, leftIndex, rightIndex);
    return IsSorted(input);
}

Time Complexity : O(N)

Step 1. Find the first left incorrect position;

public static int FindLeftIndex(int[] input)
{
    for (int index = 0; index < (input.Length - 1); index++)
    {
        if (input[index] > input[index + 1])
        {
            while (index > 0 && input[index] == input[index - 1])
            {
                index--;
            }
            return index;
        }
    }
    return -1;
}

Step 2. Find the first right incorrect position;

public static int FindRightIndex(int[] input)
{
    for (int index = input.Length - 1; index >= 1; index--)
    {
        if (input[index - 1] > input[index])
        {
            while (index < input.Length - 1 && input[index] == input[index + 1])
            {
                index++;
            }
            return index;
        }
    }
    return -1;
}

Step 3. Swap elements;

public static void Swap(int[] input, int leftIndex, int rightIndex)
{
    int temp = input[leftIndex];
    input[leftIndex] = input[rightIndex];
    input[rightIndex] = temp;
}

Step 4. Check if array is sorted , if not, return false;

public static bool IsSorted(int[] input)
{
    for (int index = 0; index < input.Length - 1; index++)
    {
        if (input[index] > input[index + 1])
        {
            return false;
        }
    }
    return true;
}

Complete Program

using System;

namespace SingleSwapCanSortArray
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] input = { 1, 3, 2, 1 };
            Console.WriteLine("Input Array: ");
            foreach (int num in input)
            {
                Console.Write("{0} ", num);
            }
            bool result = SingleSwapSortArray(input);
            Console.WriteLine("\nCan we sort array using single swap: {0}", result);
            if (result)
            {
                Console.WriteLine("Output Array: ");
                foreach (int num in input)
                {
                    Console.Write("{0} ", num);
                }
            }
            Console.Read();
        }
        public static bool SingleSwapSortArray(int[] input)
        {
            int leftIndex = FindLeftIndex(input);
            int rightIndex = FindRightIndex(input);
            if (leftIndex == rightIndex || leftIndex == -1 || rightIndex == -1)
            {
                return false; // check these edge cases just to be on safe side.
            }
            Swap(input, leftIndex, rightIndex);
            return IsSorted(input);
        }

        public static int FindLeftIndex(int[] input)
        {
            for (int index = 0; index < (input.Length - 1); index++)
            {
                if (input[index] > input[index + 1])
                {
                    while (index > 0 && input[index] == input[index - 1])
                    {
                        index--;
                    }
                    return index;
                }
            }
            return -1;
        }

        public static int FindRightIndex(int[] input)
        {
            for (int index = input.Length - 1; index >= 1; index--)
            {
                if (input[index - 1] > input[index])
                {
                    while (index < input.Length - 1 && input[index] == input[index + 1])
                    {
                        index++;
                    }
                    return index;
                }
            }
            return -1;
        }

        public static void Swap(int[] input, int leftIndex, int rightIndex)
        {
            int temp = input[leftIndex];
            input[leftIndex] = input[rightIndex];
            input[rightIndex] = temp;
        }

        public static bool IsSorted(int[] input)
        {
            for (int index = 0; index < input.Length - 1; index++)
            {
                if (input[index] > input[index + 1])
                {
                    return false;
                }
            }
            return true;
        }
    }
}

//Output
//Input Array:
//1 3 2 1
//Can we sort array using single swap: True
//Output Array:
//1 1 2 3

In this example

1. you will find 3
2. you will find 1
3. swap 3,1- > {1 1 2 3}
4. check if the array is sorted, it's sorted so return true.

Reference

• https://stackoverflow.com/questions/11032015/how-to-find-time-complexity-of-an-algorithm

Your Turn

Now it is your turn. Take this sample and implement your own C# program. Leave a comment below telling what you accomplished.

Best wishes on your adventure learning C#!