Inledning

Uppdaterad 2011-02-10 p.g.a. slarv i implementation som gjorde att resultatet inte alltid blev sorterat.

Quick sort börjar med att välja ett värde från vektorn. Detta värde brukar kallas pivot-värde. Pivot-värdet kan väljas slumpvis som i videoexemplet. Resterande värden jämförs sedan mot pivot-värdet och sorteras i två högar. En hög för mindre värden än pivot-värdet och en hög för större värden. När detta är gjort så har pivot-värdet hittat sin rätta plats i vektorn. Därefter upprepas sorteringen genom att välja ett nytt pivot-värde i någon hög av osorterade värden. På så vis delas vektorn ned i mindre och mindre delar.

Implementation

Quick sort anses vara en av de mer avancerade algoritmer att implementera. Därför är det extra viktigt att försöka visualisera algoritmen såsom vi försökt i videon ovan. Ett tips är att verkligen ta fram en kortlek och öva några gånger innan du ger dig på att förstå koden nedan. Visst kanske det låter dumt men det underlättar faktiskt!

Strategin i Quick Sort är att dela in datan i allt mindre delar. Denna teknik kallas ofta för divide and conquer eller "söndra och erövra" på svenska. Som videon visar så behandlas först hela datan genom att delas in i två delar; en lägre del och en högre del beroende på vilket pivot-värde som valts. Dessa två delar som uppstår bearbetas sedan efter samma metod. Detta upprepas om och om igen; välj pivot-värde, dela upp datan, upprepa.

Implementationen av quick sort är ett typexempel på en rekursiv funktion. Detta betyder att funktionen anropar sig själv. Det låter kanske konstigt men tänk nu på att vi skall upprepa samma metod på ett sätt som vi inte i förväg kan räkna ut.

Metoden nedan är deklarerad static då exemplet är taget från ett Console Application

static void QuickSort(int[] data, int left, int right)
{
	//Välj det tal som avgör indelningen i "högre" och "lägre"
	int pivot = data[(left + right) / 2];
	//Välj det område som skall bearbetas
	int leftHold = left;
	int rightHold = right;

	//Så länge vi har ett område kvar
	while (leftHold < rightHold)
	{
		//Hitta ett tal på vänster sida som skall ligga i den "högre" delen
		while ((data[leftHold] < pivot) && (leftHold <= rightHold)) leftHold++;
		//Hitta ett tal på höger sida som skall ligga i den "lägre" delen
		while ((data[rightHold] > pivot) && (rightHold >= leftHold)) rightHold--;

		//Om vi nu har ett område kvar så skall talen på 
		//vänster kant och höger kant byta plats
		if (leftHold < rightHold)
		{
			//Byta plats
			int tmp = data[leftHold];
			data[leftHold] = data[rightHold];
			data[rightHold] = tmp;
			//Minska området om vi flyttat två pivot-tal
			if (data[leftHold] == pivot && data[rightHold] == pivot)
				leftHold++;
		}
	}
	//Nu när området är bearbetat så skall "lägre" delen bearbetas
	//om sådan finns därefter detsamma med en eventuell "högre" del
	if (left < leftHold -1) QuickSort(data, left, leftHold - 1);
	if (right > rightHold + 1) QuickSort(data, rightHold + 1, right);
}

Vi har valt att låta metoden QuickSort() anropas med två extra parametrar utöver datan som skall sorteras. left är början på vektorn dvs. 0 när vi använder metoden och right sista positionen i vektorn dvs. data.Length - 1. Anledningen att parametrarna måste finnas är att metoden anropas sig själv rekursivt i koden, då med andra värden på left och right.

Vi skapar inga nya "lägre" och "högre" vektorer av tal så som kanske videon ser ut att göra. Vi behöver bara byta plats på tal från vänster och höger sida på det område som bearbetas så att tal under pivot-värdet ligger i början (vänster/left) och tal över pivot-värdet ligger i slutet (höger/right) i området. Tal som har samma värde som pivot-värdet kommer automatiskt att hamna mellan dessa delar i vektorn.

Läs kommentarerna noga i koden och testa gärna med att stega igenom algoritmen i Visual Studio.

Prestanda

För att mäta prestandan på algoritmen så har vi konstruerat ett Console Application som slumpar fram 1000, 10000 och sist 100000 heltal. Talen skickas först osorterade till algoritmen för att mäta generell prestanda. Därefter skickas den sorterade datan en gång till genom algoritmen för att mäta prestandan under andra förutsättningar.

Testerna som gjorts har körts på en något äldre maskin så bli inte förvånad om du får mycket bättre tider vid en jämförelse.

Testprogram

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace QuickSort
{
    class Program
    {
        static void QuickSort(int[] data, int left, int right)
        {
            //Välj det tal som avgör indelningen i "högre" och "lägre"
            int pivot = data[(left + right) / 2];
            //Välj det område som skall bearbetas
            int leftHold = left;
            int rightHold = right;

            //Så länge vi har ett område kvar
            while (leftHold < rightHold)
            {
                //Hitta ett tal på vänster sida som skall ligga i den "högre" delen
                while ((data[leftHold] < pivot) && (leftHold <= rightHold)) leftHold++;
                //Hitta ett tal på höger sida som skall ligga i den "lägre" delen
                while ((data[rightHold] > pivot) && (rightHold >= leftHold)) rightHold--;

                //Om vi nu har ett område kvar så skall talen på 
                //vänster kant och höger kant byta plats
                if (leftHold < rightHold)
                {
                    //Byta plats
                    int tmp = data[leftHold];
                    data[leftHold] = data[rightHold];
                    data[rightHold] = tmp;
                    //Minska området om vi flyttat två pivot-tal
                    if (data[leftHold] == pivot && data[rightHold] == pivot)
                        leftHold++;
                }
            }
            //Nu när området är bearbetat så skall "lägre" delen bearbetas
            //om sådan finns därefter detsamma med en eventuell "högre" del
            if (left < leftHold -1) QuickSort(data, left, leftHold - 1);
            if (right > rightHold + 1) QuickSort(data, rightHold + 1, right);
        }

        static int[] GenerateData(int size)
        {
            Random rnd = new Random();
            int[] data = new int[size];

            for (int i = 0; i < data.Length; i++)
                data[i] = rnd.Next(data.Length);

            return data;
        }

        static void Main(string[] args)
        {
            int[] sizes = new int[] { 1000, 10000, 100000 };

            for (int i = 0; i < sizes.Length; i++)
            {
                Console.WriteLine("Skapar slumpad data av längd " + sizes[i]);
                int[] data = GenerateData(sizes[i]);

                Console.WriteLine("Sorterar slumpad data");
                DateTime startTid = DateTime.Now;
                QuickSort(data, 0, data.Length - 1);
                TimeSpan deltaTid = DateTime.Now - startTid;
                Console.WriteLine("Det tog {0:0.00} ms att sortera.\n", deltaTid.TotalMilliseconds);

                Console.WriteLine("Sorterar redan sorterad data");
                startTid = DateTime.Now;
                QuickSort(data, 0, data.Length - 1);
                deltaTid = DateTime.Now - startTid;
                Console.WriteLine("Det tog {0:0.00} ms att sortera.\n", deltaTid.TotalMilliseconds);
            }
        }
    }
}

Resultat

Då testprogrammet använder DateTime för att mäta tiden blir resultatet av tider under 5 ms opålitliga. Alla resultat < 5 ms får anses som snabba.

Vi kommer att göra en del jämförelser med resultat från Bubble Sort och Insertion Sort .

Analys

Bästa fall och medelfall

Quick sort har samma prestanda i bästa fallet som i medelfallet vilket är O(n log n). log n delen i ordo-funktionen kommer sig av att algoritmen delar in områden i mindre delar hela tiden. Vi kan ta ett räkneexempel för att visa på sambandet.

Ta siffran 64 och dela den på 2. Hur många gånger kan du göra det?

Vi testar; 32, 16, 8, 4, 2, 1 ... alltså 6 gånger. Detta kan beräknas som log₂ 64 = 6. För varje nivå dvs. 1 vektor med 64 tal, 2 vektorer med 32 tal, 4 vektorer med 16 tal, etc. etc så måste vi göra jämförelser. Därför skulle vi kunna beskriva antalet beräkningar i en Quick Sort med 64 * log₂ 64 i detta exempel.

I verkligheten har vi ett annat problem, nämligen att välja ett bra pivot-värde för varje nivå. Det mest optimala är att försöka dela området i två lika delar. På så vis redurcerar vi antalet nivåer/delningar som behöver göras. Eftersom vi inte vet något om datan så väljs pivot-värdet slumpvis.

I bästa fallet så kan både Bubble Sort och Insertion Sort vara snabbare än Quick Sort. Men det räcker med att ett litet tal ligger fel för att Bubble Sort direkt skall hamna i sitt sämsta fall. Insertion Sort tåler en viss grad av "mindre osortering" och ändå prestera bra. Quick Sort har bättre förutsättningar om datan redan är sorterad (med det sätt vi väljer pivot-värde) genom att inga tal behöver byta plats. Detta gör Quick Sort någon faktor bättre i prestanda gentemot medelfallet.

Det intressanta är att titta på just medelfallet. Här ser vi att det endast tar 11 ms att sortera 100000 i slumpad data!!

Quick sort är som generell sorteringsalgoritm oslagbar! Den är i fallet med 100000 data ca 577 gånger snabbare än Insertion Sort och 2313 gånger snabbare än Bubble Sort! Ökar vi mängden data så sticker både Bubble Sort och Insertion Sort iväg kvadratiskt i tid! Quick Sort ökar endast logaritmiskt i tid.

Sämsta fall

Quick Sort har faktiskt ett sämsta fall som liknar Bubble Sort och Insertion Sort, dvs. O(n²). För att locka fram det sämsta fallet i Quick Sort så måste vi konsekvent välja det absolut sämsta pivot-värdet varje gång! Chansen att detta inträffar är astronimisk om vi jobbar med slumpvis data. Om vi jobbar med redan sorterad data så kan vi ändra i algoritmen för att locka fram ett sämsta fall.

Genom att ängra på rad 4 (valet av pivot-värde) i algoritmen till

			//Välj det tal som avgör indelningen i "högre" och "lägre"
            int pivot = data[left];
			...

Så blir nu valet av pivot-värde riktigt dåligt för redan sorterad data. Detta skapar n nivåer i logaritmen då varje område endast delas i 1 tal + resten. Det optimala hade varit att dela i lika delar. Prestandan blir nu O(n²).

Vi körde ett test med sämsta fallet och fick ett resultat på 4328 ms för 100000 data.

Jämförelser med andra algoritmer

Tid är angiven i millisekunder (1s = 1000ms). Ett resultat på 0 indikerar inte att tiden verkligen var 0 ms utan snarare att det gick för snabbt för att mätas med vår metod.