JAVA_ Test104_ 정렬(Sort) 알고리즘 / 향상된 버블 정렬(Bubble Sort)

Test104  정렬(Sort) 알고리즘 / 향상된 버블 정렬(Bubble Sort)

※ 앞서 공부한 Selection Sort 나 Bubble Sort 의 성능은 같다. (반복의 횟수로 추정)

    하지만, 향상된 Bubble Sort 는 대상 데이터의 구조에 따라 일반 Bubble Sort 나 Selection Sort 보다 성능이 좋다.

※ 불필요한 추가 연산 (회전:반복)을 수행하지 않는다.

Test104.java

public class Test104

{

public static void main(String[] args)

{

int[] a = {10, 50, 20, 33, 40};

int pass, temp;

boolean flag;

System.out.print("Source Data : ");

for (int n : a)

System.out.print(n + " ");

System.out.println();

// 향상된 Bubble Sort 구현

pass = 0;

do

{

flag=false;

pass++;

for (int i=0; i<a.length-pass; i++)

{

if (a[i] > a[i+1])

{

// 자리바꾸기

temp = a[i];

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

a[i+1] = temp;

flag=true;

//-- 단 한 번이라도 스왑(자리바꿈)이 일어나면

//   flag 변수는 true 로 변경

}

}

}

while (flag);

// 회전이 구분적으로 발생하는 동안 스왑이 일어나지 않은 경우로

// 더 이상의 반복문 수행은 무의미한 것으로 판단 → 중단

                /*

10 50 20 33 40

++---

10 50 20 33 40

   ++---

10 20 50 33 40

      ++---

10 20 33 50 40

         ++---

10 20 33 40 50

-------------------------- 1 cycle (4번)

10 20 33 40 50

++---

   ++---

      ++---

-------------------------- 2 cycle (3번)

X

X

X

*/

System.out.print("Source Data : ");

for (int n : a)

System.out.print(n + " ");

System.out.println();

}

}

cmd

Source Data : 10 50 20 33 40

Source Data : 10 20 33 40 50

계속하려면 아무 키나 누르십시오 . . .