php сортировка

В PHP есть замечательные функции для сортировки массивов данных, но речь пойдет не о них. В данной заметке я разместил примеры реализации алгоритмов сортировок на PHP, так сказать, что бы не отпускать далеко из головы. Подробно расписывать не буду, а буду приводить ссылки на Википедию. Кому надо добавляем в закладки ;)

Примеры сортировок взяты из PHP-песочницы http://phpfiddle.org

• Сортировка пузырьком на PHP
• Сортировка вставками на PHP
• Сортировка слиянием на PHP
• Быстрая сортировка на PHP
• Сортировка выбором на PHP
• Использование примеров сортировок на PHP

Сортировка пузырьком на PHP

Wiki: Сортировка пузырьком

//Сортировка пузырьком
function bubbleSort(array $arr) {
    $count = count($arr);
    if ($count <= 1) {
        return $arr;
    }

    for ($i = 0; $i < $count; $i++) {
        for ($j = $count - 1; $j > $i; $j--) {
            if ($arr[$j] < $arr[$j - 1]) {
                $tmp = $arr[$j];
                $arr[$j] = $arr[$j - 1];
                $arr[$j - 1] = $tmp;
            }
        }
    }

    return $arr;
}

Сортировка вставками на PHP

Wiki: Сортировка вставками

//Сортировка вставками
function insertSort(array $arr) {
    $count = count($arr);
    if ($count <= 1) {
        return $arr;
    }

    for ($i = 1; $i < $count; $i++) {
        $cur_val = $arr[$i];
        $j = $i - 1;

        while (isset($arr[$j]) && $arr[$j] > $cur_val) {
            $arr[$j + 1] = $arr[$j];
            $arr[$j] = $cur_val;
            $j--;
        }
    }

    return $arr;
}

Сортировка слиянием на PHP

Wiki: Сортировка слиянием

//Сортировка слиянием
function mergeSort(array $arr) {
    $count = count($arr);
    if ($count <= 1) {
        return $arr;
    }

    $left  = array_slice($arr, 0, (int)($count/2));
    $right = array_slice($arr, (int)($count/2));

    $left = mergeSort($left);
    $right = mergeSort($right);

    return merge($left, $right);
}

function merge(array $left, array $right) {
    $ret = array();
    while (count($left) > 0 && count($right) > 0) {
        if ($left[0] < $right[0]) {
            array_push($ret, array_shift($left));
        } else {
            array_push($ret, array_shift($right));
        }
    }

    array_splice($ret, count($ret), 0, $left);
    array_splice($ret, count($ret), 0, $right);

    return $ret;
}

Быстрая сортировка на PHP

Wiki: Быстрая сортировка

//Быстрая сортировка
function quickSort(array $arr) {
    $count= count($arr);
    if ($count <= 1) {
        return $arr;
    }

    $first_val = $arr[0];
    $left_arr = array();
    $right_arr = array();

    for ($i = 1; $i < $count; $i++) {
        if ($arr[$i] <= $first_val) {
            $left_arr[] = $arr[$i];
        } else {
            $right_arr[] = $arr[$i];
        }
    }

    $left_arr = quickSort($left_arr);
    $right_arr = quickSort($right_arr);

    return array_merge($left_arr, array($first_val), $right_arr);
}

Сортировка выбором на PHP

Wiki: Сортировка выбором

//Сортировка выбором
function selectSort(array $arr) {
    $count= count($arr);
    if ($count <= 1){
        return $arr;
    }

    for ($i = 0; $i < $count; $i++){
        $k = $i;

        for($j = $i + 1; $j < $count; $j++){
            if ($arr[$k] > $arr[$j]){
                $k = $j;
            }

            if ($k != $i){
                $tmp = $arr[$i];
                $arr[$i] = $arr[$k];
                $arr[$k] = $tmp;
            }
        }
    }

    return $arr;
}

Использование примеров сортировок на PHP

echo "<pre>";
echo "<br>", "Bubble Sorting - 1, 99, 3, 77, 5, 998, 7, 45, 32", "<br>";
$arr = array(1, 99, 3, 77, 5, 998, 7, 45, 32);
$reuslt = bubbleSort($arr);
print_r($reuslt);

echo "<br>", "Insert Sorting - 1, 88, 5, 77, 99, 98, 97, 55, 56, 52, 59, 37", "<br>";
$arr = array(1, 88, 5, 77, 99, 98, 97, 55, 56, 52, 59, 37);
$reuslt = insertSort($arr);
print_r($reuslt);

echo "<br>", "Merge Sorting - 6, 5, 3, 1, 8, 7, 9, 2, 4", "<br>";
$arr = array(6, 5, 3, 1, 8, 7, 9, 2, 4);
$reuslt = mergeSort($arr);
print_r($reuslt);

echo "<br>", "Quick Sorting - 1, 99, 87, 2, 5, 9, 1999, 899, 777", "<br>";
$arr = array(1, 99, 87, 2, 5, 9, 1999, 899, 777);
$reuslt = quickSort($arr);
print_r($reuslt);

echo "<br>", "Select Sorting - 11, 3, 51, 7, 99, 33, 55, 9", "<br>";
$arr = array(11, 3, 51, 7, 99, 33, 55, 9);
$reuslt = selectSort($arr);
print_r($reuslt);