﻿ Nicklas Gavelin - Insertion sort, Bucket sort and Merge sort

# Insertion sort, Bucket sort and Merge sort

Published on Tuesday, April 3, 2012

I will shortly walk you through three different sorting functions that is easily implemented in PHP. As PHP isn’t really the optimal language for sorting or such I suggest implementing a C solution or similar to gain optimal advantage of the language itself. Let’s start with the code. Code and explanation after the break.

## Insertion Sort

Okay, so this below is the insertion sort, it takes an array reference (this will lead to that the array will change outside the function call).

For starters we take the length of the array to \$array_length (pretty trivial). It then continues with a loop that will continue as long as our index \$i is below the array length. In the loop we set a temporary variable to the value of the index \$i of the array. Then we calculate a new new index \$j which is \$i – 1. The rest you can probably figure out, the loop walks through every index and switches the index places if the value is above \$temp_var and then does the procedure all over again. Happy coding ^^.

``````function insertionSort(&\$array) {
\$array_length= count(\$array);
for(\$i= 1; \$i< \$array_length; \$i++) {
\$temp_var= \$array[\$i];
\$j= \$i- 1;

\$new= \$array[\$j];
while(\$new> \$temp_var) {
\$array[\$j+ 1] = \$new;
\$array[\$j] = \$temp_var;
\$new= \$array[--\$j];
}
}
}
``````

## Merge sort

Code is pretty self explaining, read and thou shall understand!

``````class Mergesort {
/**
This gets called upon creation
\$array is a pointer to the array that has been sent into the class upon creation

Example use:
\$arr = array(1,6,1,2,775,43,75);
\$t = new Mergesort(\$arr, 0, count(\$arr) - 1);
**/
function mergeSort(&\$array, \$start, \$end) { // Pointer to array, start of array, end of array
if(\$start < \$end) { // If start is smaller than end, we have something to do
// Calculation(s)
\$half = floor((\$start + \$end) / 2); // Get how many elements the half is, floor it to get an integer

// RECURSION!
\$this->mergeSort(\$array, \$start, \$half); // Mergesort the lower half
\$this->mergeSort(\$array, \$half + 1, \$end); // Mergesort the upper half, notice!: we have already sent in element \$half, therefor we take \$half+1
// End recursion

\$this->mergeArray(\$array, \$start, \$end, \$half); // Merge the sorted arrays
}
}

/**
We want to merge the array
**/
function mergeArray(&\$array, \$start, \$end, \$half) {
\$length = \$end - \$start + 1;
\$temp = array();

\$k = 0;
for(\$i = \$start; \$i <= \$half; \$i++)
\$temp[\$k++] = \$array[\$i];

for(\$j = \$end; \$j >= \$half; \$j--)
\$temp[\$k++] = \$array[\$j];

\$j = \$length - 1; \$k = \$start;
\$i = 0;
while(\$i <= \$j) {
if(\$temp[\$i] <= \$temp[\$j])
\$array[\$k++] = \$temp[\$i++];
else
\$array[\$k++] = \$temp[\$j--];
}
}
}
``````

## Bucket sort

``````function bucketSort(&\$arr) {
\$start = microtime(true);

\$size = count(\$arr);
\$num_buckets = floor(sqrt(\$size));

\$min = \$max = \$arr;
for(\$i = 1; \$i < \$size; \$i++) {
\$tal = \$arr[\$i];
if(\$tal < \$min)
\$min = \$tal;
else if(\$tal > \$max)
\$max = \$tal;
}

\$diff = \$max - \$min + 1;
\$buckets = array_fill(0, \$num_buckets + 1, array());

for(\$i = 0; \$i < \$size; \$i++) {
\$a = \$arr[\$i];
array_push(\$buckets[floor(((\$a - \$min)* \$num_buckets)/\$diff)], \$a);
}
\$arr = array();

for(\$i = 0; \$i < \$num_buckets; \$i++)
insertionSort(\$buckets[\$i]);

foreach(\$buckets as \$bucket)
\$arr = array_merge_recursive(\$arr, \$bucket);

echo "Bucket-sort: " . (microtime(true) - \$start)*1000 . " ms";
}
``````
comments powered by Disqus