// 향상된 버블 정렬(Bubble Sort)
// ※ 앞에서 본 Selection Sort(Test107.java)나 Bubble Sort(Test108.java)의 성능은 같다.
// (→ 성능에 대한 추정 근거 : 반복문을 수행한 횟수)
// 하지만, 향상된 Bubble Sort 는 대상 데이터의 구조에 따라서
// 일반 Bubble Sort 나 Selection Sort 에 비해 성능이 좋을 수 있다.
// 원본 데이터 : 61 15 20 22 30
// 15 20 22 30 61 - 1회전 (스왑 발생 → true) → 다음 회전 진행 ○
// 15 20 22 30 61 - 2회전 (스왑 발생 → false) → 다음 회전 진행 Ⅹ
//==> 1회전 수행... 2회전 수행... 을 해 보았더니...
// 2회전에서 스왑(자리바꿈)이 전혀 일어나지 않았기 때문에
// 불필요한 추가 연산(더 이상의 회전)은 무의미한 것으로 판단하여
// 수행하지 않는다.
// 실행 예)
// Source Data : 10 50 20 30 40
// Sorted Data : 10 20 30 40 50
// 계속하려면 아무 키나 누르세요...
/*
10, 50, 20, 30, 40
== --
10, 20, 50, 30, 40
== --
10, 20, 30, 50, 40
== --
10, 20, 30, 40, 50
== --
------------------------------- 1회전 → 스왑 발생
10, 20, 30, 40, 50
== --
10, 20, 30, 40, 50
== --
10, 20, 30, 40, 50
== --
10, 20, 30, 40, 50
== --
------------------------------- 2회전 → 스왑 발생하지 않음
Ⅹ
Ⅹ
------------------------------- 3회전 → Ⅹ (할 필요 없음)
Ⅹ
------------------------------- 4회전 → Ⅹ (할 필요 없음)
*/
public class Test109
{
public static void main(String[] args)
{
int[] a = {10, 50, 20, 30, 40};
System.out.print("Source Data : ");
for (int n : a)
{
System.out.print(n + " ");
}
System.out.println();
// 정렬
// → 향상된 정렬
boolean flag;
int pass = 0;
do
{
flag = false; //-- 이번 회전에서자리바꿈이 발생하지 않을 것이다.
pass++;
for (int i=0; i<a.length-pass; i++)
{
// 테스트
// System.out.println("쑝~");
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;
//-- 단 한번이라도 스왑(자리바꿈)이 발생하게 되면
// flag 변수는 true로 변경~!!!
}
}
}
while (flag);
//-- flag 변수가 false라는 것은
// 회전이 구분적으로 ㅂ라생하는 동안 스왑이 일어나지 않은 경우로
// 더 이상의 반복문 수행은 무의미한 것으로 판단 가능~!!!
System.out.print("Sorted Data : ");
for (int n : a)
{
System.out.print(n + " ");
}
System.out.println();
}
}
