PHP Searching and Sorting Algorithm: Shell sort

PHP Searching and Sorting Algorithm: Exercise-5 with Solution

Write a PHP program to sort a list of elements using Shell sort.

According to Wikipedia "Shell sort or Shell's method, is an in-place comparison sort. It can be seen as either a generalization of sorting by exchange (bubble sort) or sorting by insertion (insertion sort). The method starts by sorting pairs of elements far apart from each other, then progressively reducing the gap between elements to be compared. Starting with far apart elements can move some out-of-place elements into position faster than a simple nearest neighbor exchange."

An example run of Shellsort with gaps 5, 3 and 1 is shown below.

The first pass, 5-sorting, performs insertion sort on separate subarrays (a1, a6, a11), (a2, a7, a12), (a3, a8), (a4, a9), (a5, a10). For instance, it changes the subarray (a1, a6, a11) from (62, 17, 25) to (17, 25, 62). The next pass, 3-sorting, performs insertion sort on the subarrays (a1, a4, a7, a10), (a2, a5, a8, a11), (a3, a6, a9, a12). The last pass, 1-sorting, is an ordinary insertion sort of the entire array (a1,..., a12). As the example illustrates, the subarrays that Shellsort operates on are initially short; later they are longer but almost ordered. In both cases insertion sort works efficiently. Shellsort is unstable: it may change the relative order of elements with equal values. It is an adaptive sorting algorithm in that it executes faster when the input is partially sorted.

Shell Sort

Shellsort with gaps 23, 10, 4, 1 in action.

Sample Solution:

PHP Code :

<?php
// Function to perform shell sort on the given array
function shell_Sort($my_array)
{
	// Initialize the gap size
	$x = round(count($my_array) / 2);
	
	// Loop until the gap size becomes 0
	while ($x > 0)
	{
		// Traverse through the array elements with the current gap
		for ($i = $x; $i < count($my_array); $i++)
		{
			// Store the current element in a temporary variable
			$temp = $my_array[$i];
			$j = $i;
			
			// Move elements of the array that are greater than temp by an interval of gap size
			// to positions ahead of their current position
			while ($j >= $x && $my_array[$j - $x] > $temp)
			{
				$my_array[$j] = $my_array[$j - $x];
				$j -= $x;
			}
			
			// Insert the temporary variable (stored element) at its correct position
			$my_array[$j] = $temp;
		}
		
		// Reduce the gap size for the next iteration
		$x = round($x / 2.2);
	}
	
	// Return the sorted array
	return $my_array;
}

// Test array to be sorted
$test_array = array(3, 0, 2, 5, -1, 4, 1);

// Display the original array
echo "Original Array :\n";
echo implode(', ', $test_array);

// Sort the array using shell sort
$sorted_array = shell_Sort($test_array);

// Display the sorted array
echo "\nSorted Array:\n";
echo implode(', ', $sorted_array) . PHP_EOL;
?>

Output:

Original Array :                                                    
3, 0, 2, 5, -1, 4, 1                                                
Sorted Array :                                                      
-1, 0, 1, 2, 3, 4, 5 

Explanation:

In the exercise above,

• The "shell_Sort()" function takes an array '$my_array' as input and performs the shell sort algorithm on it. It first initializes the gap size '$x' to approximately half the size of the input array.
• Shell Sort Algorithm:
• Inside the while loop, the algorithm iterates over the array elements with the current gap size '$x'.
• For each element at index '$i', it compares the element with the element '$x' positioned behind it.
• If the element at index $j - $x is greater than the current element ($temp), it shifts the elements to the right until it finds the correct position for the current element.
• After finding the correct position, it inserts the current element at that position.
• The gap size $x is reduced for each iteration until it becomes 0, signifying the end of the sorting process.
• Test Array and Output:
• The script defines a test array '$test_array' with unsorted elements.
• It echoes the original array using 'implode' to concatenate array elements into a string separated by commas.
• It then calls the "shell_Sort()" function to sort the array and assigns the sorted result to '$sorted_array'.
• Finally, it echoes the sorted array using 'implode' to display the sorted elements separated by commas.
• Finally the output displays the original array and the sorted array.

Flowchart :

PHP Code Editor:

Have another way to solve this solution? Contribute your code (and comments) through Disqus.

Previous: Write a PHP program to sort a list of elements using Selection sort.
Next: Write a PHP program to sort a list of elements using Bubble sort.