기본 Sort 알고리즘 - BubleSort

출처 : 쉽게 배우는 알고리즘 (문병로 저)

 

1. 기본

  - Array 에서 가장 큰 숫자를 맨 뒤로 보낸다.

    단, 이웃한 array를 비교해서 큰값을 다음값과 교환한다.

 

2. 알고리즘 version 1

BubleSort (int A[])

{

for i = N-1 downto 1

for j = 0 to i-1

if (A[j] > A[j+1]) swap(A, j, j+1);

}

 

2. 알고리즘 version 2

 

만약 아래의 비교 구문에서 한번도 swap이 발생하지 않는다면,

이미 정렬되어 있다는 뜻이다. 따라서 그냥 종료한다.

BubleSort (int A[])

{

bool bSorted= true;

for i = N-1 downto 1

for j = 0 to i-1

if (A[j] > A[j+1])

bSorted = false;

swap(A, j, j+1);

if (bSorted)

return;

}

 

3. 알고리즘 version 2구현

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

public class BubleSort extends BaseSort {       @Override    public void privateSort(int[] A) {        boolean bSorted = false;        for (int i =A.length-1 ; i >=0; i--){                   for (int j =0 ; j < i-1 ; j++) {             if( A[j] > A[j+1] ) {                 bSorted = false;                 swap(A, j, j+1);             }         }                   if (bSorted == true)             return;        }    }       /**      *      */     public BubleSort() {         // TODO Auto-generated constructor stub     }   }