QuickSort

Auteur: Button - 26 augustus 2010 - 15:37 - Gekeurd door: Koen - Hits: 3366 - Aantal punten: (0 stemmen)

Quicksort - het Quicksort sorteeralgoritme. Wordt gebruikt door php voor de functie sort(). Een implementatie van het Quicksort algoritme, daarom zelfs niet het meest efficiënte, maar een voorbeeld van hoe het geïmplementeerd kan worden.

Waarom dan gebruiken?

- Ter illustratie.
- Ter vergelijking met andere sorteeralgortmen (Insertion Sort, Bubble Sort, ...)
- ...

Wikipedia over QuickSort:
"QuickSort sorteert op basis van recursie en omwisseling. In een set gegevens van N elementen wordt ergens een spilwaarde gekozen (meestal gewoon de middelste). Dan wordt van de onderkant van de set gezocht naar een waarde die groter is dan de spil, en van de bovenkant naar een waarde die kleiner is dan de spil. Deze worden omgewisseld, en dit wordt herhaald tot de zoekpointers tot aan de spil komen. Dan zijn alle gegevens aan de ene kant kleiner dan de spil, en aan de andere kant groter. Door nu de QuickSort over deze twee deel-sets aan te roepen (recursie), worden deze ook weer voor-gesorteerd, net zolang tot de deelset nog maar uit 1 data-element bestaat, en de hele set gesorteerd is. "

Expected Case: O(n*log n)
Worst Case: O(n^2)

http://nl.wikipedia.org/wiki/Quicksort

Code:

php code - Bekijk de code zonder highlighting - Klap code in

<?php

/*
 *@description: implements quicksort algorithm
*/

function QuickSort($arr) {
	$arrLTP = $arrGTP = array(); // array less/greater than pivot
	$len = sizeof($arr);
	$pivot = 0; // we choose pivot as first element of array
	if ($len >= 1) {
		for ($i = 1; $i < $len; $i++) {
			if ($arr[$i] > $arr[$pivot]) {
				$arrGTP[] = $arr[$i];
			} else {
				$arrLTP[] = $arr[$i];
			}
		}
		if (!empty($arrGTP)) {
			$arrGTP = QuickSort($arrGTP);
		}
		if (!empty($arrLTP)) {
			$arrLTP = QuickSort($arrLTP);
		}
		$arrSorted = array_merge($arrLTP, array($arr[$pivot]), $arrGTP);
		
		return $arrSorted;
	} else {
		return array();
	}
}

/*
$quick = array(5,1,2,5,4,8,1,6,84,3,8,84,2,8);
$quicksort = Quicksort($quick);
foreach($quicksort as $v) {
	echo $v . " ";
}
*/
?>

<?php
 
/*
 *@description: implements quicksort algorithm
*/
 
function QuickSort($arr) {
	$arrLTP = $arrGTP = array(); // array less/greater than pivot
	$len = sizeof($arr);
	$pivot = 0; // we choose pivot as first element of array
	if ($len >= 1) {
		for ($i = 1; $i < $len; $i++) {
			if ($arr[$i] > $arr[$pivot]) {
				$arrGTP[] = $arr[$i];
			} else {
				$arrLTP[] = $arr[$i];
			}
		}
		if (!empty($arrGTP)) {
			$arrGTP = QuickSort($arrGTP);
		}
		if (!empty($arrLTP)) {
			$arrLTP = QuickSort($arrLTP);
		}
		$arrSorted = array_merge($arrLTP, array($arr[$pivot]), $arrGTP);
 
		return $arrSorted;
	} else {
		return array();
	}
}
 
/*
$quick = array(5,1,2,5,4,8,1,6,84,3,8,84,2,8);
$quicksort = Quicksort($quick);
foreach($quicksort as $v) {
	echo $v . " ";
}
*/
?>

Download code (.txt)

Stemmen

Niet ingelogd.

Reacties

Post een reactie

Geen reacties (0)