Thursday, January 16, 2020

[Java][Exercise] Impletment of swap and bubble sort

Swap is a act of exchanging the values of the variables mutually. In this article, logic of swap will be used for exchange 2 values for using in bubble search, it will be used if a number bigger than folowing number.Here is the logic of swap function:
public class Main{
  public static void main(String[] args){
    int a = 9;
    int b = 5;
    int[] c = swap(a,b);
    System.out.println(a+":"+b);
    System.out.println(c[0]+":"+c[1]);
  }
  public static int[] swap(int arg1, int arg2){
    int temp = arg2;
    arg2 = arg1;
    arg1 = temp;
    return new int[]{arg1, arg2};
  }
}
Result:
9:5
5:9

By wiki defination, "bubble sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted." To understand what is bubble sort, let have an example with 5 numbers, right now we have 5 numbers 9,8,7,6,5 in decreasing order, and want to sort them in in increasing order, how can we do that with bubble sort?

We would compare the first pair of 2 numbers (with index 0 and index 1), and swap(excahnge the valueables) them if first value bigger than latter one.and then repeat this action on next pair of 2 numbers (with index 1 and index 2) until the last number in this set is compared. If we using [9,8,7,6,5] as instance, there are 4 passes is required.

First pass
source  :   9,8,7,6,5
1st swap:   8,9,7,6,5
2nd swap:   8,7,9,6,5
3rd swap:   8,7,6,9,5
4th swap:   8,7,6,5,9

Second pass:
source  :   8,7,6,5,9
1st swap:   7,8,6,5,9
2nd swap:   7,6,8,5,9
3rd swap:   7,6,5,8,9

Third pass:
source  :   7,6,5,8,9
1st swap:   6,7,5,8,9
2nd swap:   6,5,7,8,9

Fourth pass:
source  :   6,7,5,8,9
1st swap:   5,6,7,8,9

The first for-loop is the passes for comparing each number item in source array.The second for-loop is for comparing each number item in a pass. Swap logic would applied in script inside these 2 for-loop to do in-place sorting:
public class Main{
  public static void main(String[] args){
    int[] arr = new int[]{9,8,7,6,5};
    System.out.println(Arrays.toString(bubbleSort(arr)));
  }
  public static int[] bubbleSort(int[] arr){
    for(int count=arr.length;1<count;count--){
      for(int i=1;i<arr.length;i++){
        if(arr[i-1]>arr[i]){
          int temp = arr[i-1];
          arr[i-1] = arr[i];
          arr[i] = temp;
          count++;
        }
      }
    }
    return arr;
  }
}
input : [9,8,7,6,5]
output: [5,6,7,8,9]

Reference

https://4xsc.com/java-swap/
https://en.wikipedia.org/wiki/Bubble_sort
https://en.wikipedia.org/wiki/In-place_algorithm
https://en.wikipedia.org/wiki/Swap_(computer_programming)

No comments :

Post a Comment