[Sort] 버블 정렬

 

 

컴퓨터과학에서 데이터를 정렬하는 것은 매우 중요하다. 중요한 만큼 다양한 정렬 알고리즘이 존재하는데 차차 다 알아가 보자.

 

---

 

 

버블정렬

 

  버블 정렬(Bubble sort)은 배열을 순차적으로 비교하면서 정렬하는 알고리즘이다.

  1번째와 2번째 원소를 비교하고 정렬하고, 2번째와 3번째 비교 후 정렬 ...... n-1, n번째 비교 후 정렬이다.

 

  버블 정렬은 정렬 알고리즘 중 가장 최악의 성능을 보여주는 알고리즘이다.

 

  정렬에 대표적인 O(N^2)의 알고리즘이며

 

  O(n^2)은 1만 개 데이터를 1초에 정렬한다면 10만 개의 데이터는 100초 정도나 걸린다.

 

 

 

---

 

 

  버블 정렬은 성능이 최악이다. 보통 프로그래밍 처음 공부할 때 정렬을 처음 공부할 때 버블 정렬부터 공부를 한다. 가장 이해하기 쉽고 배우기 쉽고 코드가 짧다.

 

  입력량이 작으면 비효율적인 것을 느끼지 못하지만 정렬해야 할 데이터가 많아지면 버블정렬은 굉장히 비효율적이게 변한다.

 

  실제 프로그램 개발에서는 버블 쇼트는 안 사용한다고 한다.

 

---

 

 

  버블 쇼트는 단순하다. 중첩 반복문을 사용한다.

  해당 버블 정렬은 오름차순이다.

 

  외부 for문은 배열의 총길이 - 1 회만큼 돌린다.

  arr.length-1만큼 한 이유는 어차피 마지막 요소 이미 정렬된 값들이기 때문.

  

  내부 for문은 작성하고 싶은 대로 작성할 수 있지만

  

    void sort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 1; j < arr.length; j++) {
                if (arr[j] < arr[j - 1]) {
                    int temp = arr[j - 1];
                    arr[j - 1] = arr[j];
                    arr[j] = temp;
                }
            }
        }
    }

 

 

 

    static void bubble(int[] arr){
        for(int i=0; i<arr.length-1; i++){
            for(int j=i+1; j<arr.length; j++){
                if(arr[i]>arr[j]){
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
    }

 

 

 

  어떤 식으로 작성하든 상관없다 목적은 오름차순, 내림차순 기준으로

  이중 반복문을 통해 구현하면 된다.

 

 

 

 

상세하게 코드를 짜봤다.

 

public class BubbleSort {
    public static void main(String[] args) {
        int[] arr ={1,8,50,100,2};
        System.out.println("초기값");
        for(int i: arr){
            System.out.print(i+" ");
        }
        System.out.println();
        bubble(arr);
    }

    static void bubble(int[] arr){
        for(int i=0; i<arr.length-1; i++){
            System.out.println("버블정렬 "+(i+1)+"회차");
            for(int j=0; j< arr.length-i-1;j++){
                if(arr[j]>arr[j+1]){
                    swap(arr, j, j+1);
                }
            }

            for(int k:arr){
                System.out.print(k+" ");
            }
            System.out.println();
        }
    }

    static void swap(int[] arr, int index, int target){
        int temp = arr[index];
        arr[index] = arr[target];
        arr[target] = temp;
    }
}

 

 

 

 

 

 

 

버블 정렬 1회차 수행 과정

 

 

 

  외부 반복문 i가 1번 순환할 때 내부 for문은 이런 식으로 값 교환을 한다.

  한번 i가 돌면 맨 끝에 위치한 값은 배열에서 가장 큰 값이므로, 내부 for문은 arr.length-i-1만큼 돌면 된다.

 

  arr.length = 5이면,

  5-0-1 = 4,

  5-1-1 = 3.

  5-2-1 = 2

        .

        .

  5-n-1 = 길이