[Algoritm] 초보자도 쉽게 버블정렬 이해하기! - java 예시, 버블정렬 문제풀이

 

버블정렬(Bubble sort)

버블정렬로 원소가 정렬되는 과정

 

버블정렬의 개념, 버블정렬이란?

정렬시, 원소가 이동하는 모습이 거품이 수면위로 올라오는 듯한 모습과 같다고해서 붙여진 이름으로

인접한 두 개의 원소를 비교하여 자리를 교환하는 방법으로 교환정렬의 일부에 속한다.

 

버블정렬로 정렬을 할 때는 원소의 갯수만큼 순회를 하게된다. 

 

오름차순일 경우 1회차때는 가장 큰수, 2회차때는 두번채로 큰수. 이런식으로 가장 큰수부터 자기 자리를 찾아간다. 

따라서 회차를 거듭할수록 1회씩 정렬의 횟수가 적어진다. 자기자리를 찾은 원소는 정렬할 필요가 없기때문이다.

 

 

그림으로 이해하기

출처 - https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html

 

 

시간 복잡도

• O(n^2)
  • 최악, 최선, 평균일 경우 모두 동일한 시간복잡도를 가진다.
  • 중간에 정렬이 완성되었어도 마지막까지 모든 비교가 수행되기 때문이다.

 

장단점 (사용하면 좋은/나쁜 상황)

장점

• 구현이 매우 간단하다
• 직관적이다
• 처음 정렬을 어떻게 적용하는지 배우는데 도움이된다. 
• 왜 해당 정렬이 비효율적인지를 이해하게된다
• 이미 정렬되어 있는경우에 사용하면 최적의 효율을 낸다.

단점

• 가장왼쪽에 있는 원소가 가장 오른쪽으로 이동하기 위해서는 모든 원소들과 교환되어야한다.
• 원소 교환(swap)은 원소 이동(move) 보다 더 복잡하기 때문에 단순성에도 불구하고 거의 사용되지 않는다. 
• 역순으로 되어있는 배열을 버블소트로 정렬하면 최악의 효율을 낸다. 

 

소스코드 예시와 설명 (백준문제_ java)

백준 2750문제 버블정렬로 풀기

  문제 -  https://www.acmicpc.net/problem/2750

import java.util.*;
public class 버블_수정렬하기_2750 {
    public static void main(String[] args)throws Exception{
         Scanner sc = new Scanner(System.in);
         int N = sc.nextInt();
         int[] a = new int[N];
         for(int i=0;i<N;i++){
             a[i]=sc.nextInt();
         }
         
         //오름차순정렬
         for (int i = 0; i < N-1; i++) { //메인 원소 선정
            for (int j = 0; j < N-1-i; j++) { //메인 원소를 인접한 다른 원소와 교환
                if(a[j]>a[j+1]){
                    int temp =a[j];
                    a[j]=a[j+1];
                    a[j+1]= temp;
                }
            }//for1
        }//for2
        for (int i = 0; i < N; i++) {
            System.out.println(a[i]);
        }
    }
}

 

 

백준 1377 문제로 버블정렬이해하기

  문제  -   https://www.acmicpc.net/problem/1377

  설명 참고  -  https://infinitt.tistory.com/229

import java.io.*;
import java.util.*;

class Box implements Comparable<Box>{
    int value, index;
    public Box(int value, int index){
        super();
        this.value=value; this.index=index;
    }
@Override
    public int compareTo(Box o) {
        return this.value-o.value;
    }
}

public class 버블소트프로그램_1377 {
    public static void main(String[] args)throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N =Integer.parseInt(br.readLine());
        Box[] a = new Box[N];

        for(int i=0;i<N;i++){
            a[i] = new Box(Integer.parseInt(br.readLine()),i); //원소, index
        }
        int result = 0;
        Arrays.sort(a); //객체를 빠르게 정렬 - 여기서 버블정렬사용하면 시간초과됨
        for(int i=0;i<N;i++){
            if(result < a[i].index-i){ //
                result = a[i].index-i;
            }
        }
        System.out.println(result+1);
    }
}