Costruire Quicksort con php

Question

Di recente ho letto di quicksort e si chiedeva se sarebbe intelligente per costruire la mia propria funzione per sistemare le cose con Quicksort o se sarebbe inefficent. Cosa ne pensi è costruito in funzione sort di meglio di una funzione di selfbuilt Quicksort?

Answer 1

http://php.net/sort

  

Nota: Come la maggior parte di smistamento PHP   funzioni, sort () utilizza un   attuazione »Quicksort.

Le funzioni PHP di base saranno implementate in C, invece di PHP, in modo che dovrebbe essere generalmente significativamente più veloce di qualsiasi cosa si può scrivere se stessi in PHP. Ci saranno casi in cui è più veloce di scrivere il proprio, ma credo che queste sarebbero quando si dispone di un caso molto specifico e si può fare il vostro proprio ottimizzazioni specifiche per questo. Penso che sia improbabile che sia il caso qui.

Answer 2

In realtà ho fatto questo per un punto dati su una presentazione sto mettendo insieme. Il test ordina un array di 250.000 interi utilizzando la funzione di ordinamento nativa e un'implementazione dell'algoritmo quicksort scritto in php. I contenuti della matrice sono esattamente la stessa per entrambi i funzionamenti, i dati sono randomizzati, e il tempo riportato è solo per eseguire l'ordinamento, non altre elaborazioni necessario invocare l'interprete php.

Risultati:

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

utilizzare Sicuramente l'implementazione nativa. Questo dovrebbe essere il caso per qualsiasi linguaggio interpretato.

I risultati per le altre lingue che ho provato con le stesse condizioni che utilizzano la stessa implementazione sullo stesso hardware e il sistema operativo, forniscono un confronto delle prestazioni interessante e mettere il risultato in prospettiva PHP:

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

In particolare, Chrome e Safari eseguito molto più veloce per il test JavaScript, ma non comprendono quelli qui perché questi test sono stati registrati in un ambiente diverso.

Answer 3

Stick con la funzione di ordinamento built-in. Quicksort è un semplice algoritmo, ma per ottenere buone prestazioni su computer che si trovano effettivamente in uso richiede un po 'di finezza. E 'più che probabile che la funzione built-in è già più ottimizzato di ogni altra cosa si può scrivere in un ragionevole lasso di tempo. (La costante fattore accelerazione di essere scritto in C, invece di PHP è probabilmente anche utile.)

Se si ordina così tanti elementi che si sono rallentati dalla funzione di ordinamento, si sono probabilmente facendo qualcosa di sbagliato. (Questo è PHP, dopo tutto. Si dovrebbe usare un linguaggio general-purpose per l'elaborazione ad alta intensità di dati. Sarà più facile scrivere il codice, e sarà correre più veloce.)

Answer 4

Per riferimento c'è un'implementazione PHP qui:

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

Answer 5

Una cosa del genere php rapido (asort, arsort, ecc) è che pasticcio tuoi valori uguali, vale a dire che i valori con chiavi diverse potranno scambiare in modo casuale posizione, anche tra diverse esecuzioni. Sorprendente che il codice può produrre un ordine diverso utilizzando ripetutamente gli stessi dati. Alla fine ho dovuto implementare il mio quick sort per rimuovere questa anomalia.

Answer 6

Solo per divertimento, qui è una versione sul posto di quicksort in PHP mi è venuta. Il trucco è quello di passare la matrice di essere filtrate come riferimento.

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);
}

Answer 7

Di seguito riportiamo la classe per implementare il quick sort in 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);


            ?>