CODEWITHSUNDEEP
javaalgorithminsertion-sort
TaiAu
TaiAu

Reputation: 49

Java: Insertion Sort Algorithm Swap

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);
  }
}

Upvotes: 2

Views: 1147

Answers (2)

Andy Turner
Andy Turner

Reputation: 140328

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.

Upvotes: 1

Eran
Eran

Reputation: 393831

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.

Upvotes: 1

Related Questions