버블 정렬 (bubble sort)

인접한 두 원소를 비교하여 큰값을 오른쪽으로 스왑(swap)하여 정렬하는 알고리즘

버블 정렬

- 구현이 간단하지만, 하나의 요소가 가장 왼쪽에서 가장 오른쪽으로 이동하기 위해서는 배열에서 모든 다른 요소들과 교환되어야 한다.

- 특히 특정 요소가 최종 정렬 위치에 이미 있는 경우라도 교환되는 일이 일어난다.

- 일반적으로 자료의 교환 작업(SWAP)이 자료의 이동 작업(MOVE)보다 더 복잡하기 때문에 버블 정렬은 단순성에도 불구하고 거의 쓰이지 않는다.

- 시간 복잡도 : $$ {n}^{2} $$

worst, average case 모두 O(n^2)의 시간복잡도를 갖는다.

(처음 n, 그 다음 n-1, 그 다음 n-2 ...... 2, 1 = n*n-1*-n-2 .... 2,1 = n(n-1)/2 = O(n^2))

best 인 경우에는 O(n)의 시간복잡도를 갖는다 ( 이미 정렬이 된 상태라면 스왑이 일어나지 않기 때문)

- Stable sort (안정적 정렬, 정렬을 했을 때 중복된 값들의 순서가 변하지 않음) 

 

 

코드

import java.io.IOException;


public class Main {
    public static void main(String[] args) throws IOException {
       int[] numArr = new int[10];

       for(int i=0;i<numArr.length;i++){
           System.out.print(numArr[i] = (int) (Math.random() *10));
       }

        System.out.println();

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

           for(int k=0;k<numArr.length;k++){
               System.out.print(numArr[k]);
           }
           System.out.println();
       }
    }
}

 

설명

  for(int i=0;i<numArr.length;i++){
           System.out.print(numArr[i] = (int) (Math.random() *10));
       }

1부터 10까지의 숫자(Math.ramdon()) 10개를 배열 numArr의 각 요소에 대입한다.

 

 for(int i=0;i<numArr.length-1;i++){

첫번째 for문:

배열의 각 요소에 접근 (각 요소에 대한 정렬을 해야함) 

이때 전체 요소의 개수 -1(numArr.length-1)로 하는 이유는 두개의 원소를 비교하기 때문에 전체 -1 을 하더라도 모든 요소에 대한 비교가 되므로 numArr.length-1 을 전체 범위로 잡아도 안전하다.

 

for(int j=0;j<numArr.length-1-i;j++){

두번째 for문: 

j번째 요소를 '배열의 길이-1-i'번 만큼 반복해서 비교

(j번째 요소를 정렬되지 않은 남은 요소들 (배열의 길이-1-i)만큼 반복 해야함)

 

 if(numArr[j] > numArr[j+1]){
                   int temp = numArr[j];
                   numArr[j] = numArr[j+1];
                   numArr[j+1] = temp;
                 }

두번째 for문 안의 if문:

j번째 요소와 j+1번째 요소의 크기를 비교해서 큰쪽을 오른쪽(j+1)으로 대입하고, 작은 쪽을 왼쪽(j)으로 대입

 

 for(int k=0;k< numArr.length;k++){
               System.out.print(numArr[k]);
           }

세번재 for문:

현재 배열의 정렬 상황을 for문을 통해 출력함

 

 System.out.println();

줄바꿈

---

출력

4944514435
4445144359
4441443559
4414434559
4144344559
1443444559
1434444559
1344444559

 

 

 

 

 

 

 

Reference

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