[PHP] 배열 버블 정렬

버블 정렬(Bubble Sort)은 가장 간단한 정렬 알고리즘 중 하나로, 배열의 인접한 두 요소를 비교하여 필요한 경우 교환(swap)하는 방식으로 작동합니다. 이를 반복하여 가장 큰 값이 배열의 끝으로 "거품처럼" 이동합니다.

PHP에서 배열을 버블 정렬하는 코드는 다음과 같습니다.

 

PHP로 버블 정렬 구현

1. 숫자 배열의 버블 정렬

<?php
function bubbleSort(array $arr): array {
    $n = count($arr); // 배열의 길이
    for ($i = 0; $i < $n - 1; $i++) {
        for ($j = 0; $j < $n - $i - 1; $j++) {
            if ($arr[$j] > $arr[$j + 1]) {
                // 두 요소를 교환
                $temp = $arr[$j];
                $arr[$j] = $arr[$j + 1];
                $arr[$j + 1] = $temp;
            }
        }
    }
    return $arr;
}

// 예제
$array = [5, 3, 8, 4, 2];
$sortedArray = bubbleSort($array);

print_r($sortedArray);
// 출력: Array ( [0] => 2 [1] => 3 [2] => 4 [3] => 5 [4] => 8 )
?>

설명

- 외부 루프는 정렬이 완료될 때까지 반복합니다.

- 내부 루프는 현재 인접한 두 요소를 비교하고, 필요하면 위치를 교환합니다.

- 점진적으로 큰 값이 배열의 오른쪽 끝으로 이동합니다.

 

2. 문자열 배열의 버블 정렬

문자열 배열도 동일한 방식으로 정렬할 수 있습니다. 문자열의 정렬은 PHP에서 사전 순서(ASCII 코드값)로 비교됩니다.

<?php
function bubbleSortStrings(array $arr): array {
    $n = count($arr);
    for ($i = 0; $i < $n - 1; $i++) {
        for ($j = 0; $j < $n - $i - 1; $j++) {
            if (strcmp($arr[$j], $arr[$j + 1]) > 0) {
                // 두 문자열 교환
                $temp = $arr[$j];
                $arr[$j] = $arr[$j + 1];
                $arr[$j + 1] = $temp;
            }
        }
    }
    return $arr;
}

// 예제
$array = ["pear", "apple", "orange", "banana"];
$sortedArray = bubbleSortStrings($array);

print_r($sortedArray);
// 출력: Array ( [0] => apple [1] => banana [2] => orange [3] => pear )
?>

 

3. 최적화된 버블 정렬

기본 버블 정렬은 배열이 이미 정렬된 경우에도 모든 비교를 수행합니다. 최적화된 버전은 교환이 발생하지 않으면 정렬이 완료된 것으로 간주하여 루프를 조기 종료합니다.

<?php
function optimizedBubbleSort(array $arr): array {
    $n = count($arr);
    for ($i = 0; $i < $n - 1; $i++) {
        $swapped = false; // 교환 여부 플래그
        for ($j = 0; $j < $n - $i - 1; $j++) {
            if ($arr[$j] > $arr[$j + 1]) {
                // 두 요소를 교환
                $temp = $arr[$j];
                $arr[$j] = $arr[$j + 1];
                $arr[$j + 1] = $temp;
                $swapped = true;
            }
        }
        // 교환이 없으면 정렬 완료
        if (!$swapped) break;
    }
    return $arr;
}

// 예제
$array = [1, 2, 3, 4, 5];
$sortedArray = optimizedBubbleSort($array);

print_r($sortedArray);
// 출력: Array ( [0] => 1 [1] => 2 [2] => 3 [3] => 4 [4] => 5 )
?>

장점

- 정렬된 배열에 대해 더 빠르게 작동합니다.

- 교환이 없는 경우 루프를 중단하여 불필요한 비교를 방지합니다.

 

4. 내림차순 정렬

버블 정렬을 내림차순으로 변경하려면 비교 연산자를 뒤집으면 됩니다.

<?php
function bubbleSortDescending(array $arr): array {
    $n = count($arr);
    for ($i = 0; $i < $n - 1; $i++) {
        for ($j = 0; $j < $n - $i - 1; $j++) {
            if ($arr[$j] < $arr[$j + 1]) {
                // 두 요소를 교환
                $temp = $arr[$j];
                $arr[$j] = $arr[$j + 1];
                $arr[$j + 1] = $temp;
            }
        }
    }
    return $arr;
}

// 예제
$array = [5, 3, 8, 4, 2];
$sortedArray = bubbleSortDescending($array);

print_r($sortedArray);
// 출력: Array ( [0] => 8 [1] => 5 [2] => 4 [3] => 3 [4] => 2 )
?>

 

요약

1. 버블 정렬은 간단하고 구현하기 쉬운 정렬 알고리즘입니다.

2. 기본 방식은 모든 요소를 반복적으로 비교하며, 정렬이 점진적으로 이루어집니다.

3. 최적화된 버블 정렬은 교환이 없을 경우 루프를 종료하여 불필요한 연산을 줄입니다.

4. 배열의 데이터 유형(숫자, 문자열)에 따라 적절히 비교 방법을 선택할 수 있습니다.

5. 성능은 O(n²)로 느리기 때문에 작은 데이터셋에서만 사용됩니다.

 

With ChatGPT