정렬(Sort)-버블정렬

버블정렬

 

• 붙어 있는 두 값을 검사하여 정렬한다 
• 오름차순으로 정렬할 때는 왼쪽의 값이 오른쪽의 값보다 작아야하고, 이에 맞지 않다면 값을 서로 교환한다
• 내림차순으로 정렬할 때는 오른쪽의 값이 왼쪽의 값보다 작아야하고, 이에 맞지 않다면 값을 서로 교환한다

 

ex) 오름차순 정렬  

 

6

4

3

7

1

9

8

1. 9와 8을 비교하고 왼쪽 값이 오른쪽 값보다 작아야하기에 8과 9를 교환한다

6

4

3

7

1

8

9

2. 8과 1을 비교하고 왼쪽 값이 오른쪽 값보다 작기 때문에 1과 8은 교환하지 않는다

6

4

3

7

1

8

9

3. 1과 7을 비교하고 왼쪽 값이 오른쪽 값보다 작아야하기에 7과 1를 교환한다

6

4

3

1

7

8

9

4. 1과 3을 비교하고 왼쪽 값이 오른쪽 값보다 작아야하기에 1과 3을 교환한다

6

4

1

3

7

8

9

5. 1과 4를 비교하고 왼쪽 값이 오른쪽 값보다 작아야 하기에 값을 교환한다 

6

1

4

3

7

8

9

6. 1과 6을 비교하고 왼쪽 값이 오른쪽 값보다 작아야 하기에 값을 교환한다 

 

이러한 순서로 총 n-1회 진행한다 

 

 

그 뒤, 배열의 뒤에서 2번째 요소부터 첫번째 요소까지 똑같은 과정을 반복한다. 

(n-1)+(n-2) + (n-3) + (n-4) ..... = n(n-2)/2

 

 

코드로 나타낸 버블정렬 

ex) 

//오름차순 

public static void BubbleSort(int[] a){
   for(int i = 0; i<a.length; i++){
      //처음부터 n-1회이기 때문이다
      for(int j=0; j<a.length-i-1; j++){
         if(a[j]>a[j+1]){
            int t = a[j+1];
            a[j+1] = a[j];
            a[j] = t;
         }
      }
   }
}