기본 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구현

	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
	}

}