Insertion Swaps Counting Number Of

[HankReardon]

Hello, I have been having quite a bit of trouble with this one. Can someone please tell me how many swaps it would require to sort the following array? {2, 4, 6, 3, 7, 1} I tried putting my counter in a couple of places and neither one of them add up to what I get by simply counting the swaps manually. My manual count is two.
Thank you,
Hank.

/**
   The IntInsertionSorter class provides a public static
   method for performing an insertion sort on an int array.
*/

   public class IntInsertionSorter2
   {
      private static int count = 0;

   /**
      The insertionSort method performs an insertion sort on
      an int array. The array is sorted in ascending order.
      @param array The array to sort.
   */

      public static void insertionSort2(int[] array)
      {
         int unsortedValue;  // The first unsorted value
         int scan;           // Used to scan the array


      // The outer loop steps the index variable through 
      // each subscript in the array, starting at 1. The portion of
      // the array containing element 0  by itself is already sorted.
         for (int index = 1; index < array.length; index++)
         {
         // The first element outside the sorted portion is
         // array[index]. Store the value of this element
         // in unsortedValue.
            unsortedValue = array[index];

         // Start scan at the subscript of the first element
         // outside the sorted part.
            scan = index;

         // Move the first element in the still unsorted part
         // into its proper position within the sorted part.
            while (scan > 0 && array[scan-1] > unsortedValue)
            {
               array[scan] = array[scan - 1];
               scan--;
               count ++;


            }

         // Insert the unsorted value in its proper position
         // within the sorted subset.
            array[scan] = unsortedValue;

         }
         //System.out.println(swap);
         System.out.println("count" + count);

      }
   }

Emphasized Text Here

[bguild]

My manual count of the swaps using an insertion sort is 7. Since the array is only 6 items long, there is clearly a way to sort it using at most 6 swaps, but every number in the array is out of its correct position and there are no two values which can be swapped to put them both into the correct position.

It would be an interesting exercise to find an algorithm to determine the exact minimum number of swaps required to sort a particular array. How exactly are you manually sorting this array in two swaps?

[HankReardon]

Hello bguild,
This is the if statement that I added to count my swaps. I came up with this by processing the array by hand with pen and paper.
Thank you,
Jim

         // Count swaps only if unequal.
            if (array[scan] != unsortedValue)
               swap ++;
         // Insert the unsorted value in its proper position
         // within the sorted subset.   
            array[scan] = unsortedValue;

[bguild]

I've come up with this toy that I expect finds the minimum number of swaps needed to sort an array. Perhaps it will help clarify your ideas about counting swaps.

import java.util.*;

public final class SwapStack {
    public static final class Swap {
        public final int first;
        public final int second;
        public Swap(int first, int second) {
            this.first = first;
            this.second = second;
        }
        public void perform(int[] array) {
            int temp = array[first];
            array[first] = array[second];
            array[second] = temp;
        }
        public void perform(Object[] array) {
            Object temp = array[first];
            array[first] = array[second];
            array[second] = temp;
        }
        @Override
        public String toString() {
            return String.format("%d <-> %d", first, second);
        }
    }
    private final int[] content;
    private final Deque<Swap> swaps = new ArrayDeque<Swap>();
    public SwapStack(int[] content) {
        this.content = Arrays.copyOf(content, content.length);
    }
    public int get(int index) { return content[index]; }
    public int size() { return content.length; }
    public void push(int first, int second) {
        Swap swap = new Swap(first, second);
        swaps.addLast(swap);
        swap.perform(content);
    }
    public Swap pop() {
        Swap swap = swaps.removeLast();
        swap.perform(content);
        return swap;
    }
    public int depth() { return swaps.size(); }
    public List<Swap> getSwaps() { return new ArrayList<Swap>(swaps); }
    @SafeVarargs
    public static <E extends Comparable<E>> List<Swap> findSwaps(E... inputArray) {
        E[] sortedArray = Arrays.copyOf(inputArray, inputArray.length);
        Arrays.sort(sortedArray);
        final Map<E,Integer> orderMap = new HashMap<E,Integer>();
        for (int i = 0; i < sortedArray.length; i++)
            orderMap.put(sortedArray[i], i);
        int[] orderArray = new int[inputArray.length];
        for (int i = 0; i < inputArray.length; i++)
            orderArray[i] = orderMap.get(inputArray[i]);
        return findSwaps(new SwapStack(orderArray));
    }
    private static List<Swap> findSwaps(SwapStack stack) {
        List<Swap> best = null;
        for (int i = 0; i < stack.size(); i++) {
            if(i != stack.get(i)) {
                stack.push(i, stack.get(i));
                List<Swap> attempt = findSwaps(stack);
                stack.pop();
                if(best == null || best.size() > attempt.size()) best = attempt;
            }
        }
        if(best == null) return stack.getSwaps();
        else return best;
    }
    public static void main(String... args) {
        if(args.length > 0) test(args);
        else {
            test(1, 2, 3);
            test(7, 4, 2, 6, 5, 1);
            test(2, 4, 6, 3, 7, 1);
        }
    }
    @SafeVarargs
    private static <E extends Comparable<E>> void test(E... array) {
        System.out.printf("Original: %s%n", Arrays.toString(array));
        final List<Swap> swaps = findSwaps(array);
        System.out.printf("Swaps: %s%n", swaps);
        System.out.printf("Swap count: %s%n", swaps.size());
        for (int i = 0; i < swaps.size(); i++) {
            Swap swap = swaps.get(i);
            swap.perform(array);
            System.out.printf("%2d: %s%n", i + 1, Arrays.toString(array));
        }
    }
}

[HankReardon]

Wow, this is awesome, it will take me a few to digest but I will look at it, thanks.

[HankReardon]

Hello bguild,
First, thank you for the good assistance. You are a lifeline to me in this storm on the high seas of data.
After looking at your code I think my method is the simplest for doing insertion sorting.
Why, because the while loop is designed to just move the scan around while the swap statement after the while loop actually makes a swap if the two are unequal. Therefore by testing if the two are unequal before the swap we can determine whether or not an actual swap was made and count it.
I am probably wrong about this but this is where I am stuck at for the moment.
Thank you,
Jim

[HankReardon]

I see the error in my ways. Thank you for the help with this.