There are 14 algorithms presented:
- quickSort
- countingSort
- combSort
- heapSort
- mergeSort
- shellSort
- selectionSort
- insertSort
- gnomeSort
- combinedBubbleSort
- cocktailSort
- bubbleSort
- oddEvenSort
- bubbleSortWithFlag
Algorithms are not alphabetically ordered, but in order of their performance speed descending when sorting an array of 8 thousand elements.
The following arrays dimensions, used for sorting, are presented:
- 1
- 100
- 200
- 400
- 600
- 800
- 1000
- 5000
- 10000
- 15000
- 20000
- 25000
- 30000
Each measurement was performed with different array filling, which is passed to sorting function.
- In the first case the array has been filled by random values with a (1, n) interval, in which n — is an array dimension.
- In the second case the array has been filled by random values with a (1, PHP_INT_MAX) interval, in which PHP_INT_MAX — is maximum variable value of INT type in the current system. In my system it’s 2^63 or approx 9.2233720368548E+18
Each measurement has been performed three times and an arithmetic mean has been taken
Arrays of up to 1000 elements
All sorting functions are involved in this category.
![](/uploads/images/00/00/01/2014/05/09/372715.png)
![](/uploads/images/00/00/01/2014/05/09/a311c4.png)
Arrays of up to 30 thousand elements
In this case 5 the fastest algorithms are involved: counting, quick, comb, heap and merge sorts.
![](/uploads/images/00/00/01/2014/05/09/ba8976.png)
![](/uploads/images/00/00/01/2014/05/09/e5cbdd.png)
Arrays of up to 200 thousand elements
In this case the same 5 algorithms are involved: counting, quick, comb, heap and merge sorts.
![](/uploads/images/00/00/01/2014/05/09/62ffb3.png)
![](/uploads/images/00/00/01/2014/05/09/bdb51d.png)
Arrays of up to 2 million elements
In the last round of 2 million elements two algorithms were involved: count sort and quick sort.
![](/uploads/images/00/00/01/2014/05/09/e882b7.png)
![](/uploads/images/00/00/01/2014/05/09/cf4799.png)
Summary
QuickSort is rightfully considered quite a good algorithm. CountingSort is really good at small value ranges; otherwise it can’t manage due to low memory. Cocktail sort proved to be a bad choice for random values. Bubble sort and its modifications are not applicable to practical use.
Source code of all algorithms + results: https://drive.google.com/file/d/0B63HSL7JD630VWdSSFgwdHR5RkU/edit?usp=sharing
While a fun exercise, use the built in sort function. Building a sort function in interpreted PHP code will never be faster than the C variant that sort() employs.
2 comments
Upload image