CODEWITHSUNDEEP
javaalgorithmarraylistinsertion-sort
M9A
M9A

Reputation: 3286

Record elements compared in sorting algorithm in java

Hi I am using the following insertion sort algorithm and I would like to record the elements being compared. Basically I want the comparisons to be stored in two array lists, arrList1 and arrList2. If an element is in its correct place then both array lists will have the same element. If its not then arrList1 will have the chosen element and arrayList2 will have the element its comparing itself to. I am currently struggling to do this, so I was wondering if anyone can help? Thanks

public static ArrayList<Integer> arrList1 = new ArrayList<Integer>();
public static ArrayList<Integer> arrList2 = new ArrayList<Integer>();
...
        public static void insertSort(int[] A){
      for(int i = 1; i < A.length; i++){
        int value = A[i];
        int j = i - 1;
        while(j >= 0 && A[j] > value){
          A[j + 1] = A[j];
          j = j - 1;
        }
        A[j + 1] = value;
      }
    }

EDIT: For example: If my array had the numbers 1,3,2,4,6,5 then when comparing, this is how I want my two array lists to look:

       arrList1    arrList2
#1        1           1
#2        3           3
#3        2           3 (As 2 goes before 3 then it must be compared to 3)
#4        4           4
#5        6           6
#6        5           6 (As 5 is lower then 6 then it must be compared to 6)

Sorted array: 1, 2, 3, 4, 5, 6

As you can see, arrList1 is basically the order of the input array whilst arrList2 is the element it compares to if its not in correct position. If its in correct position then arrList 2 will be same value.

Upvotes: 1

Views: 254

Answers (2)

Ivaylo Strandjev
Ivaylo Strandjev

Reputation: 71009

EDIT: now that I understand the question here is what I propose. First note that insert sort has sqare(O(n^2)) complexity so another computation of the same complexity will not change the overall complexity of the algorithm. So here is what you do - first you compute the values in arrList2 by traversing all values on the left of the current element and search for the first one greater then the current element. The second phase is simply the sorting algorithm - as you already pointed out arrList1 holds the sorted A. The whole thing could be implemented with better complexity but not using insert sort.

public static ArrayList<Integer> arrList1 = new ArrayList<Integer>();
public static ArrayList<Integer> arrList2 = new ArrayList<Integer>();
...
public static void insertSort(int[] A){
  for (int i = 0; i < A.length; ++i) {
    boolean found_greater = false;
    for (int j = i - 1; j >= 0; --j) {
      if (A[j] > A[i]) {
        found_greater = true;
        arrList2.add(A[j]);
        break;
      }
    }
    if (!found_greater) {
      arrList2.add(A[i]);
    }
  }

  for(int i = 1; i < A.length; i++){
    int value = A[i];
    int j = i - 1;
    while(j >= 0 && A[j] > value){
      A[j + 1] = A[j];
      j = j - 1;
    }

    arrList1.add(A[i]);
    A[j + 1] = value;
  }
}

Upvotes: 1

Alberto Gutierrez
Alberto Gutierrez

Reputation: 1588

There you have...

public class Test {
    public static List<Integer> arrList1;
    public static ArrayList<Integer> arrList2 = new ArrayList<Integer>();

    public static void main (String... args){
        Integer[] toSort = {1, 3, 2, 4, 6, 5};


        arrList1 = Arrays.asList(Arrays.copyOf(toSort, toSort.length));
        insertSort(toSort);

        List<Integer> sortedArray = new ArrayList<Integer>();
        for(int aux: toSort){
            sortedArray.add(aux);
        }

        System.out.println("Array list 1: " + arrList1);
        System.out.println("Array list 2: " + arrList2);
        System.out.println("Sorted array: " + sortedArray);
    }

    public static void insertSort(Integer[] A){
        arrList2.add(arrList1.get(0));
        for(int i = 1; i < A.length; i++){
            int value = A[i];
            int j = i - 1;
            if ((j >= 0 && A[j] > value)){
                arrList2.add(A[j]);
            }else{
                arrList2.add(A[i]);
            }
            while(j >= 0 && A[j] > value){
                A[j + 1] = A[j];
                j = j - 1;
            }

            A[j + 1] = value;
        }
    }
}

The output of this code for me is:

Array list 1: [1, 3, 2, 4, 6, 5] Array list 2: [1, 3, 3, 4, 6, 6] Sorted array: [1, 2, 3, 4, 5, 6]

Upvotes: 1

Related Questions