[PHP] 버블 정렬을 이용한 배열 원소 정렬

■ 버블 정렬을 이용한 배열 원소 정렬

 버블 정렬(bubble sort)은 인접한 원소 두 개를 비교해가면서 값을 정렬하는 방법으로, 처리 속도는 느리지만 코드가 단순해 자주 사용된다. 여섯 개의 숫자 28, 15, 10, 25, 32, 17을 오름차순으로 정렬하는 예를 통해 버블 정렬이 동작하는 원리를 알아보자.

① ~ ⑨ 단계를 거치면, 배열의 맨 오른쪽 여섯 번째 위치에 들어갈 가장 큰 수 32를 찾는다. 다음으로 다섯 번째 위치에 들어갈 두 번째로 큰 수를 찾기 위해 과정을 반복하되, 다섯 번째 원소까지만 비교한다. 버블 정렬 결과 여섯 번째 위치부터 값이 큰 순서대로 저장된다.

array_sort01.php

<?         $num = array(15, 13, 9, 7, 6, 12, 19, 30, 28, 26);     $count = 10;    // 배열 원소의 개수(10)를 $count에 입력     echo "정렬되기 전 : ";     for($a = 0; $a < 10; $a++) {                  echo $num[$a]."$nbsp";     }     echo "<br/>";     for($i = $count - 2; $i >= 0; $i--) {    // $i는 8 ~ 0으로 1씩 감소                  for($j = 0; $j <= $i; $j++) {        // $j는 0 ~ $i로 1씩 증가                          if($num[$j] > $num[$j + 1]) {    // 앞에 위치한 숫자가 더 크면 위치 바꿈                                  $tmp = $num[$j];                // 앞의 데이터를 $tmp에 잠시 저장                 $num[$j] = $num[$j + 1];      // 뒤의 데이터를 앞의 배열 원소에 저장                 $num[$j + 1] =$tmp;            // $tmp를 뒤의 배열 원소에 저장             }         }     }     echo "오름차순 정렬(버블정렬) : ";     for($a = 0; $a < 10; $a++) {            // 버블 정렬 후 배열 원소 출력                  echo $num[$a]. " ";     } ?>

출력결과

① 정렬하려는 숫자와 개수 입력

 2행 정렬하려는 숫자를 배열 변수 $num에 입력한다.

 4행 정렬하려는 수자의 개수를 나타내는 변수 $count에 10을 입력한다.

② 정렬 전 배열 원소 출력

 6행 ~ 8행 배열에 저장된 숫자를 출력한다.

③ 버블 정렬을 잉요한 배열 원소 정렬

 12 ~ 23행 이중 for 문을 이용하여 버블 정렬을 구한한다. 12행의 for문은 $i가 8에서 0으로 1씩 감소하는 동안 반복된다. $i값에 따라 14행 for문의 $j를 0에서 $i로 1씩 증가시키면서 16 ~ 21행에 있는 if문을 실행한다. if문에서 두 원소의 값을 비교해 앞의 원소가 뒤의 원소보다 크면 18 ~ 20행에서 두 원소의 위츨 서로 맞바꾼다.

④ 정렬 결과 출력

 25 ~ 27행 버블 정렬 숫자를 오름차순 정렬하고 출력한다.

---

 아래 코드를 22행과 23행 사이에 추가해 버블 정렬 수행 과정을 좀 더 자세히 살펴보자.

array_sort02.php

<?         $num = array(15, 13, 9, 7, 6, 12, 19, 30, 28, 26);     $count = 10;    // 배열 원소의 개수(10)를 $count에 입력     echo "정렬되기 전 : ";     for($a = 0; $a < 10; $a++) {                  echo $num[$a]."$nbsp";     }     echo "<br/>";     for($i = $count - 2; $i >= 0; $i--) {    // $i는 8 ~ 0으로 1씩 감소                  for($j = 0; $j <= $i; $j++) {        // $j는 0 ~ $i로 1씩 증가                          if($num[$j] > $num[$j + 1]) {    // 앞에 위치한 숫자가 더 크면 위치 바꿈                                  $tmp = $num[$j];              // 앞의 데이터를 $tmp에 잠시 저장                 $num[$j] = $num[$j + 1];    // 뒤의 데이터를 앞의 배열 원소에 저장                 $num[$j + 1] =$tmp;         // $tmp를 뒤의 배열 원소에 저장             }         }     }     echo "오름차순 정렬(버블정렬) : ";     for($a = 0; $a < 10; $a++) {            // 버블 정렬 후 배열 원소 출력                  echo $num[$a]. " ";     } ?>

출력결과

 $i가 8일 때 맨 마지막 원소에 가장 큰 값인 30이 저장된다. $가 7이면 아홉 번째 원소에 그 다음 큰 수 28이 저장된다 .마지막으로 $i가 0일 때, 두 번째 원소에 두 번째로 작은 7이 저장되면서 버블 정렬이 완료되고, 오름차순으로 정렬된 숫자를 확인할 수 있다.