C#: Permutation sort

C# Sharp Searching and Sorting Algorithm: Exercise-8 with Solution

Write a C# Sharp program to sort a list of elements using Permutation sort.

Permutation sort, proceeds by generating the possible permutations of the input array/list until discovering the sorted one.

Sample Solution:-

C# Sharp Code:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class Program
{
    // Method to swap two characters using XOR operation
    private static void Swap(ref char a, ref char b)
    {
        if (a == b) return; // No need to swap if the characters are the same

        a ^= b; // XOR operation to swap characters
        b ^= a;
        a ^= b;
    }

    // Method to get permutations of characters in the list
    public static void GetPer(char[] list)
    {
        int x = list.Length - 1;
        GetPer(list, 0, x); // Calls the overloaded method to get permutations
    }

    // Recursive method to generate permutations
    private static void GetPer(char[] list, int k, int m)
    {
        if (k == m)
        {
            // Print the generated permutation when k equals m
            Console.WriteLine(list);
        }
        else
        {
            // Loop to generate permutations
            for (int i = k; i <= m; i++)
            {
                // Swap characters at positions k and i
                Swap(ref list[k], ref list[i]);

                // Recursively generate permutations with the updated list
                GetPer(list, k + 1, m);

                // Restore the original order by swapping back the characters
                Swap(ref list[k], ref list[i]);
            }
        }
    }

    static void Main()
    {
        string str = "ABC";
        char[] arr = str.ToCharArray(); // Convert the string to a character array
        GetPer(arr); // Call the method to generate permutations
    }
}
	

Sample Output:

ABC
ACB
BAC
BCA
CBA
CAB

Flowchart:

C# Sharp Code Editor:

Contribute your code and comments through Disqus.

Previous: Write a C# Sharp program to sort a list of elements using Merge sort.
Next: Write a C# Sharp program to sort a list of elements using Quick sort.