[알고리즘] 버블정렬(Bubble Sort)

저번시간에 이어 이번시간에는 버블 정렬에 대해 알아보겠습니다.

다들 알다시피 버블은 거품입니다. 원소들을 정렬하는데 그 이동하는 모습이 거품이 수면으로 올라오는 듯한 모습으로 보이기 떄문에 버블정렬이라고 지어졌습니다.

 

버블정렬은 인접한 두 원소의 값을 비교하여 큰 값을 오른쪽으로 하나씩 옮기는 방법입니다. 그래서 처음부터 끝까지 한번 반복했을 때, 가장 큰 값이 오른쪽에 정렬되게 됩니다.

 

마찬가지로 이번 시간에도 선생님이 버블정렬 방식으로 영호(175),호진(178),태경(180),웅광(167),동욱(173) 5명의 학생들을 키 순서대로 줄을 세울 생각입니다.



먼저 태경이와 동욱이를 비교합니다. 태경이가 더 크네요. 동욱이와 자리를 바꿔줍니다.

 

태경이와 영호를 비교합니다. 태경이가 더 크네요. 영호와 자리를 바꿔줍니다.

 

태경이와 웅광이를 비교합니다. 태경이가 더 크네요. 웅과이와 자리를 바꿔줍니다.

 

태경이와 호진이를 비교합니다. 태경이가 더 크네요. 호진이와 자리를 바꿔줍니다.

 

 

이제 한번이 끝났네요 !! 한번 끝났을 때 가장 큰 수가 오른쪽에 정렬되게 됩니다. 이런 방법으로 나머지 동욱, 영호, 웅광, 호진이도 반복을 정렬을 할 수 있습니다.

 

import java.util.Scanner;
public class Main{
    public static void main(String[] args){

       int[] ary = {1,5,6,2,7,8,10,21};
       
      for(int a=0;a<ary.length;a++){
        for(int b=0;b<ary.length-a-1;b++){
          if(ary[b]>ary[b+1]){
            int temp;
            temp=ary[b];
            ary[b]=ary[b+1];
            ary[b+1]=temp;
          }
        }
      }
      
        for(int r:ary){
         System.out.println(r);
       }
       

    }
}

생각해볼 점은 두번째 for문의 b값은 배열의 어디까지 검사해야하느냐 입니다. 일단 배열의 길이는 8입니다.

a=0 일때, 7번을 검사합니다.

a=1 일때, 6번을 검사합니다.

a=2 일때, 5번을 검사합니다.

a=3 일때, 4번을 검사합니다.

.......

이런 규칙에 의하여 b의 범위는 ary.length-a-1이 됩니다. 위의 경우를 하나씩 대입해보면서 확인할 수 있습니다.

그리고 if문에서 현재 나의 값과 내 바로 앞의 값을 비교해서 내가 더 크다면 교환해 줍니다. 더 큰 값이 오른쪽으로 가야하니깐요. 

 

 

시간복잡도는 n개의 숫자들을 n번 검사해야 하기 떄문에 O(n^2)의 시간복잡도는 가집니다.