[ JAVA ] 정렬 (Sort) 알고리즘 : "향상된" 버블 정렬 (Bubble Sort)

※ 앞서 포스팅했던 selection sort 나 bubble sort의 성능은 같다(반복의 횟수로 측정)
하지만, 향상된 Bubble Sort는 대상이 되는 데이터의 구조에 따라 일반 bubble sort나 selection sort보다 성능이 좋을 수 있다.

예를 들어 원본데이터 {61, 15, 20, 22, 30}을 오름차순으로 정렬한다고 했을 때
15 20 22 30 61 : 1회전에서는 스왑이 발생
15 20 22 30 61 : 2회전에서는 스왑이 발생하지 않고 다음 회전이 필요 X
1회전 수행...2회전 수행...을 해봤더니 2회전을 수행하는 과정에서 스왑(자리바꿈)이 전혀 일어나지 않았기 때문에 불필요한 추가 연산이 필요하지 않다.

 

 

 

public class Test104
{
	public static void main(String[] args)
	{
		int[] a = {10, 50, 20, 33, 40};

		System.out.print("Source Data : ");
		for (int n:a)
			System.out.print(n + " ");
		System.out.println();


	
		//향상된 Bubble Sort 구현		
		int pass=0;
		boolean flag=false;

		do
		{
			pass++;
			flag = false;
			for (int i=0; i<a.length-pass; i++)  // pass/i  1/0123  2/012  3/01  4/0 
			{
				if (a[i] > a[i+1])
				{
					//자리바꾸기

					a[i] = a[i]^a[i+1];
					a[i+1] = a[i+1]^a[i];
					a[i] = a[i]^a[i+1];

					flag = true;  // 자리바꿈이 일어났다는 사실 확인!
				}
				
			}
		}
		while (flag);//자리바꿈이 일어났다면 다시 반복돌고 아니라면 빠져나온다. 
		//회전이 구분적으로 발생하는 동안(웅!) 스왑(자리바꿈)이 일어나지 않은 경우로 더 이상의 반복문 수행은 무의미한 것으로 판단!


		System.out.print("Sorted Data : ");
		for (int n:a)
			System.out.print(n + " ");
		System.out.println();



	}
}
/*
Source Data : 10 50 20 33 40
Sorted Data : 10 20 33 40 50
계속하려면 아무 키나 누르십시오 . . 
*/