How do i count the number of letter swaps made to the string?-CodePudding

i want my program to count the number of swaps of chars occured to arrange them in alphabetical order. is there any simple way to do this? here is my code.

import java.util.Arrays;
import java.util.Scanner;

class ArrangingBooks{
public static void main(String[] args) {
     Scanner scan= new Scanner(System.in);
     String str = scan.nextLine();
     char c[] = str.toCharArray();
     Arrays.sort(c);
     System.out.println(new String(c));

     scan.close();
}
}

Sample Input = LLSLM

Output for Sample Input = 2

CodePudding user response：

Arrays.sort would choose the most optimal sorting algorithm but you would not be able to track the steps unless you modify the Arrays package.

Alternatively, you can implement your own sort code, or copy/paste one from online and add an Integer counter to increment for every sort-loop iteration. Then you would be able to get the number of steps per input.

CodePudding user response：

You can create a 2-dimensional array to store each codePoint and its index. Then you can sort the array comparing the codePoints:

public static int countSortedSwaps(String str) {
    int[] arr = str.codePoints().toArray();
    int size = arr.length;
    
    int[][] charIndices = IntStream.range(0, size).boxed()
            .sorted(Comparator.comparingInt(i -> arr[i]))
            .map(i -> new int[] {arr[i], i})
            .toArray(int[][]::new);
   
    boolean[] swp = new boolean[size];
    
    return IntStream.range(0, size)
            .filter(i -> swp[i] != true && charIndices[i][1] != i)
            .map(i -> count(charIndices, swp, i)).sum();
}

private static int count(int[][] charIndices, boolean[] swp, int index) {
    int count = 0;
    int i = index;
    while (swp[i] == false) {
        swp[i] = true;
        count  ;
        i = charIndices[i][1];
    }
    return (count - 1);
}