Быстрая сортировка в php [дубликат]

Одна вещь о быстрой сортировке php (asort, arsort и т. д.) заключается в том, что они обменивают ваши равные значения, то есть значения с разными ключами будут случайным образом менять позицию даже между разными прогонами. Удивительно, что код может производить другой порядок, используя одни и те же данные снова и снова. В конце концов, мне пришлось реализовать свой собственный быстрый вид, чтобы удалить эту аномалию.

Для справки здесь есть реализация PHP:

https://en.wikibooks.org/wiki/Algorithm_Implementation/Sorting/Quicksort#PHP

Придерживайтесь встроенной функцией сортировки. Quicksort - это простой алгоритм, но для получения хорошей производительности на компьютерах, которые на самом деле используются, требуется немного тонкости. Более чем вероятно, что встроенная функция уже оптимизирована, чем все, что вы могли бы написать за разумное время. (Вероятно, использование константного фактора из написания в C вместо PHP также полезно.)

Если вы сортируете так много элементов, что вы замедляете функцию сортировки, вы, вероятно, делаете что-то неправильно , (Это, в конце концов, PHP. Вы должны использовать язык общего назначения для интенсивной обработки данных. Будет проще писать код, и он будет работать быстрее.)

Ниже приведен класс для реализации Quick Sort в PHP -

            <?php
            class quickSort{
            /* low  --> Starting index,  high  --> Ending index */
                public $arr;
                public function __construct($arr){
                    $this->arr = $arr;
                }
                public function qsort($low,$high){
                    if($low===null || $high===null){    
                        return false;
                    }
                    if($low < $high){           
                        $pi = $this->partition($low,$high);
                        $this->qsort($low,$pi-1); /*before pivot*/
                        $this->qsort($pi+1,$high); /*before pivot*/
                    }
                }

                /* This function takes last element as pivot, places
                   the pivot element at its correct position in sorted
                    array, and places all smaller (smaller than pivot)
                   to left of pivot and all greater elements to right
                   of pivot */
                public function partition($low,$high){
                    if($low===null || $high===null){
                        return false;
                    }
                    $pivot = $this->arr[$high];
                    $i = $low-1; /*index of smaller element*/

                    for($j = $low; $j <= $high-1; $j++)
                    {
                        // If current element is smaller than or equal to pivot

                        if($this->arr[$j] <= $pivot)
                        {
                            $i++;    // increment index of smaller element
                            $this->swap($i,$j);         
                        }
                    }
                    //swap arr[i + 1] and arr[high])
                    $this->swap($i+1,$high);

                    return $i+1;    
                }

                public function swap($i,$j){
                    $p=$this->arr[$i];
                    $q=$this->arr[$j];
                    $this->arr[$i]=$q;
                    $this->arr[$j]=$p;      
                }
            }
            $arr = array(10, 80, 30, 90, 40, 50, 70);
            $obj = new quickSort($arr);
            $obj->qsort(0,6);
            print_r($obj->arr);


            ?>

Фактически я сделал это для точки данных на презентации, которую я собираю. Тест сортирует массив из 250 000 целых чисел, используя собственную функцию сортировки и реализацию алгоритма быстрой сортировки, написанного на php. Содержимое массива одинаково для обоих прогонов, данные рандомизированы, а время, указанное только для выполнения сортировки, а не для другой обработки, необходимой для вызова интерпретатора php.

Результаты:

  Native sort implementation:  1.379 seconds
PHP quicksort implementation: 30.615 seconds

Определенно использовать встроенную реализацию. Это должно быть для любого интерпретируемого языка.

Результаты для других языков, которые я тестировал с одинаковыми условиями, используя ту же самую реализацию на одном и том же оборудовании и ОС, обеспечивают интересное сравнение производительности и ставят результат PHP в перспективе:

               C: 0.107 seconds
            Java: 0.250 seconds
JavaScript (FF3): 4.401 seconds

Примечательно, что Chrome и Safari выполнили много быстрее для теста JavaScript, но я не включаю их здесь, потому что эти тесты были записаны в другой среде .

Просто для удовольствия, вот на месте версия quicksort в PHP, с которой я пришел. Трюк здесь состоит в том, чтобы передать массив, который будет отсортирован как ссылка.

function partition(&$arr,$leftIndex,$rightIndex)
{
    $pivot=$arr[($leftIndex+$rightIndex)/2];

    while ($leftIndex <= $rightIndex) 
    {        
        while ($arr[$leftIndex] < $pivot)             
                $leftIndex++;
        while ($arr[$rightIndex] > $pivot)
                $rightIndex--;
        if ($leftIndex <= $rightIndex) {  
                $tmp = $arr[$leftIndex];
                $arr[$leftIndex] = $arr[$rightIndex];
                $arr[$rightIndex] = $tmp;
                $leftIndex++;
                $rightIndex--;
        }
    }
    return $leftIndex;
}

function quickSort(&$arr, $leftIndex, $rightIndex)
{
    $index = partition($arr,$leftIndex,$rightIndex);
    if ($leftIndex < $index - 1)
        quickSort($arr, $leftIndex, $index - 1);
    if ($index < $rightIndex)
        quickSort($arr, $index, $rightIndex);
}