Algorithm Practice : Bubble Sort and Merge Sort.

Algorithm Java

Motivation

Recently I take small tests on line like below. But I'm not good at actually..

ITプログラマー・エンジニア転職のpaiza

Understanding Algorithm is a kind of required skill if you are not a new. I need to learn it even if step by step..

Bubble Sort

Bubble sort is the easiest one in several sort algorithms. The concept is just below:

repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order.

When you want to sort an array as descending, starting comparing a pair in array bottom to set smaller element in smaller index. Just continue the same thing to the next bottom pair recursively. Finally your array will be sorted. In case of Ascending sort, do the opposite way.

Condition: https://paiza.jp/learning/sort-number

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws Exception {
        // 自分の得意な言語で
        // Let's チャレンジ！！
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = br.readLine();
        
        /* 
        * create not sorted array
        */
        int rowCount = Integer.parseInt(line);
        int[] ansArray = new int[rowCount];
        for (int i = 0; i < rowCount; i++) {
            ansArray[i] = Integer.parseInt(br.readLine());
        }
        
        /* 
        * Bubble Sort
        */
        for (int i = 0; i < ansArray.length; i++) {
            // After the first loop, ansArray[0] becomes 
            // the smallest value.
            // It means you don't have to think about 
            // the last ansArray[i] in the next loop.
            // So "i" is getting be incremented 
            // and comparing target length getting be minus "i".

            for (int j = ansArray.length - 1; j > i; j--) {
                // From the last element to right before i.
                
                if (ansArray[j - 1] > ansArray[j]) {
                    // if a lower positioned value ansArray[j] is smaller than ansArray[j - 1]
                    // change the position
                    int smaller = ansArray[j];
                    ansArray[j] = ansArray[j - 1];
                    ansArray[j - 1] = smaller;
                }
            }
            System.out.println("" + ansArray[i]);
        }
    }
}

When N is the number of elements. Bubble sort's computational complexity is O(N2). N's dimension is calculated below:

(N-1) + (N-2) + (N-3) + … + 2 + 1 = N(N-1)/2

Merge Sort

It is easy to merge 2 sorted array. Just get each array's value according to indexes, compare them, then push bigger or smaller value to "an answer" stack. Merge sort uses this concept. To realize this, there are 2 steps which are "repeatedly divide" and "repeatedly merge".

Condition: https://paiza.jp/learning/sort-number

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    
    private static void merge(int[] a1,int[] a2,int[] a){
        
        int i = 0;
        int j = 0;
      

        // loop until reaching 2 both arrays elements. 
        while (i < a1.length || j < a2.length) {

            // j can be smaller than i because of splitIndex spec.
            // to avoid OutOfIndex error when attempt to get a2[j], 
            // "j >= a2.length " have to in if condition.
            if( j >= a2.length

                // to avoid OutOfIndex error when i reached at a1.length, 
                // "i < a1.length" have to be in if condition 
                || ( i < a1.length && a1[i] < a2[j] )){
                
                // basically, here is for a1[i] < a2[j] 
                // Next smaller element is a2[i] 

                a[i+j]=a1[i];
                
                i++;
                
            } else {
                
                // basically, here is for a1[i] > a2[j] 
                // Next smaller element is a2[j] 


                a[i+j]=a2[j];
                
                j++;
                
            }
        }
    }
    
    private static void mergeSort(int[] a) {
        
        if(a.length > 1){
          
          /*
          * split input array into 2 as equal number of elements as.
          */

          int splitIndex = a.length / 2;
          int restIndex = a.length - splitIndex;
          
          int[] a1 = new int[splitIndex];
          int[] a2 = new int[restIndex];
          
          for(int i = 0; i < splitIndex; i++) {
              a1[i] = a[i];
          }
          for(int i = 0; i < restIndex; i++) {
              a2[i] = a[splitIndex + i];
          }
          
          // mergeSort and merge. 
          // Caller waits until 
          // Callee finishes "merge" method recursively.
          // At the lowest level, a1 and a2 are array 
          // but they has a single value.
          // At the next level, they has 2 values. next is 4, 8 ...
          // In the end, 
          // each a1 and a2 are just a 2 arrays 
          // created by input array, and have been sorted. 
          // after merging them, sort has been finished.
          mergeSort(a1);
          mergeSort(a2);
          merge(a1, a2, a);
        }
    }
    
    public static void main(String[] args) throws Exception {
        // 自分の得意な言語で
        // Let's チャレンジ！！
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = br.readLine();

        /* 
        * create not sorted array
        */
        int rowCount = Integer.parseInt(line);
        int[] ansArray = new int[rowCount];
        for (int i = 0; i < rowCount; i++) {
            ansArray[i] = Integer.parseInt(br.readLine());
        }
       
        /*
        * Do merge sort
        */
        mergeSort(ansArray);
        
        for (int i = 0; i < ansArray.length; i++) {
            System.out.println("" + ansArray[i]);
        }
        
        
    }
}

When N is the number of elements. Bubble sort's computational complexity is O(N log(N)). ※Base of a logarithm is 2. N's dimension is calculated below:

  1. Divide single pair in each array ... N log(N)
  2. Merge them recursively ... N log(N)
  3. 1 + 2 = 2N log(N) = O(N log(N))