Bubble Sort

 

 

Bubble Sort 버블정렬

 

맨 앞의 index부터 바로 옆의 index와 비교를 해서 큰 수가 오른쪽으로 자리하면서 더이상 비교할 값이 없을 때까지 정렬을 해나가는 알고리즘. 

 

 

3

2

5

1

4

1st Pass - The largest number is placed at the last when each pass is complete. 한번의 실행마다 가장 큰 수가 가장 마지막 index 에 자리하게 된다. 

2

3

1

4

5

2nd Pass

2

1

3

4

5

3rd Pass

1

2

3

4

5

 

 

Example Code in Java

public class Main {
    public static void main(String[] args) {
        int arr[] = {3,2,5,1,4};
        printArray(arr); //before sorting
        bubbleSort(arr); //sorting
        printArray(arr); //after sorting
    }
 
    private static void bubbleSort(int[] arr){
        bubbleSort(arr, arr.length-1); //last index
    }
 
    private static void bubbleSort(int[] arr, int last){
        if(last > 0){ //last index number is going to '0' then terminate recursion
            for (int i = 1; i <= last ; i++) {
                if(arr[i-1] > arr[i]){
                    swap(arr, i-1, i); //swap adjacent pairs
                }
            }
            bubbleSort(arr, last-1);//no need the last index because it is always the biggest number
        }
    }
 
    private static void swap(int[]arr, int source, int target){
        int tmp = arr[source];
        arr[source] = arr[target];
        arr[target] = tmp;
    }
 
    private static void printArray(int[] arr){
        for (int data : arr) {
            System.out.print(data + ", ");
        }
        System.out.println();
    }
}
 
//output
//3, 2, 5, 1, 4,
//1, 2, 3, 4, 5, 

 

 

Big-O notation for Bubble Sort is O(n²) 

               Why?

 

n - 1 + n - 2 + ... + 2 + 1 

                 +                    // Sum the total number of steps

1 + 2 + ... + n - 2 + n - 1  

                /2

                 =

       n x (n - 1) / 2 

                 =

         1/2(n² - n) 

              n² - n //Remove constant

              O(n²) //Leave only larger value. 'n²' is larger than 'n'

 

 

 

Example Code in Javascript

const arr = [5,1,3,2,4];

function bubble(arr){
    for (let i = 0; i < arr.length-1; i++) { //정확히 sort되었는지 확인하기위해사용.
        for (let j = 0; j < arr.length-1; j++) {
            if (arr[j] > arr[j + 1]) {
                let temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    console.log(arr);
}

bubble(arr);

 

 

 

 

Reference

medium.com/javascript-algorithms/javascript-algorithms-bubble-sort-3d27f285c3b2

https://www.youtube.com/watch?v=m4reW0jkSYk&t=1s

https://www.youtube.com/watch?v=D6xkbGLQesk&t=1767s

https://stackoverflow.com/questions/11477743/why-is-bubble-sort-on2

https://www.youtube.com/watch?v=YbsQiiubO74