Java: Insertion Sort Algorithm Swap

Question

Dear fellow Stackoverflowers,

My swap method isn't working inside the insertionSort method; it is not swapping my array elements.

What's wrong with my insertion sort algorithm?

package AlgoExercises;

import java.util.Arrays;

public class InsertionSort {

  static int[] numbersArray = { 5, 2, 4, 6, 1, 3 };

  static void swap(int a, int b) {
    int temp = a;
    a = b;
    b = temp;
  }

  static void insertionSort(int[] numbersArray) {
    for (int i = 1; i < numbersArray.length - 1; i++) {
      int j = i;
      while ((j > 0) && (numbersArray[j] < numbersArray[j - 1])) {
        swap(numbersArray[j], numbersArray[j - 1]);
        j = j - 1;
        System.out.println(Arrays.toString(numbersArray));
      }
    }
  }

  public static void main(String args[]) {
    insertionSort(numbersArray);
  }
}

Solution:

After fixing the swap method where int[] was included in its parameters, swap now works! I've also edited numbersArray.length-1 to numbersArray.length.

Thank you for your help guys!

package AlgoExercises;

import java.util.Arrays;

public class InsertionSort {

  static int[] numbersArray = { 5, 2, 4, 6, 1, 3 };

  static void swap(int i, int j) {
    int temp = numbersArray[j];
    numbersArray[j] = numbersArray[i];
    numbersArray[i] = temp;
  }

  static void insertionSort(int[] numbersArray) {
    for (int i = 1; i < numbersArray.length; i++) {
      int j = i;
      while ((j > 0) && (numbersArray[j] < numbersArray[j - 1])) {
        swap(j, j - 1);
        j = j - 1;
        System.out.println(Arrays.toString(numbersArray));
      }
    }
  }

  public static void main(String args[]) {
    insertionSort(numbersArray);
  }
}

you have to set the swap in your array. currently that is not the case. — nano_nano, Jan 14 '16 at 12:34
Possible duplicate of http://stackoverflow.com/questions/32431061/simple-swap-in-java — Andy Turner, Jan 14 '16 at 12:43

score 1 · Accepted Answer · answered Jan 14 '16 at 12:34

1

Java is a pass by value language, so swapping the int variables passed to the swap method makes no difference. You should pass the array itself + the two indices to swap to the method, and modify the array in the swap method.

static void swap(int[] arr, int i, int j) {
    int temp = arr[j];
    arr[j] = arr[i];
    arr[i] = temp;
}

and call it

swap(numbersArray, j, j-1);

Note that I didn't check the logic of your insertion sort implementation. This answer only deals with the swap issue.

answered Jan 14 '16 at 12:34

Eran

387,369
54
702
768

Well, no, it's not by value, but by copy of reference. – user unknown Jan 14 '16 at 14:18
That's what "pass-by-value" means; see https://stackoverflow.com/questions/40480/is-java-pass-by-reference-or-pass-by-value – kaya3 Nov 11 '19 at 14:03

Andy Turner · Answer 2 · 2016-01-14T12:58:01.713

Just to give you another way of thinking why your existing swap method doesn't work: if you write code like this:

void swap(int a, int b) {
  int t = a;
  a = b;
  b = t;
}

void callSwap() {
  int x = 1;
  int y = 2;

  swap(x, y);

  System.out.println(x + ", " + y);
}

You can 'inline' the swap method, basically copying it into the callSwap method. The semantically equivalent code would be:

void callSwap() {
  int x = 1;
  int y = 2;

  // Start of inlined swap method.
  {
    int a = x;
    int b = y;

    int t = a;
    a = b;
    b = t;
  }
  // End of inlined swap method.

  System.out.println(x + ", " + y);
}

Hopefully, you wouldn't expect x and y to have swapped values.

Note that this behaviour has nothing to do with the fact that the variable names a and b are different to x and y; I simply chose them to be different. Were the parameters of swap called x and y, it would be necessary to rename them to something else when inlining, since they are completely separate from the x and y in callSwap.

Java: Insertion Sort Algorithm Swap

2 Answers2