How to resolve the algorithm Sorting algorithms/Shell sort step by step in the PowerShell programming language

Published on 12 May 2024 09:40 PM
#Powershell

How to resolve the algorithm Sorting algorithms/Shell sort step by step in the PowerShell programming language

Table of Contents

Problem Statement

Sort an array of elements using the Shell sort algorithm, a diminishing increment sort. The Shell sort   (also known as Shellsort or Shell's method)   is named after its inventor, Donald Shell, who published the algorithm in 1959. Shell sort is a sequence of interleaved insertion sorts based on an increment sequence. The increment size is reduced after each pass until the increment size is 1. With an increment size of 1, the sort is a basic insertion sort, but by this time the data is guaranteed to be almost sorted, which is insertion sort's "best case". Any sequence will sort the data as long as it ends in 1, but some work better than others. Empirical studies have shown a geometric increment sequence with a ratio of about 2.2 work well in practice. [1] Other good sequences are found at the On-Line Encyclopedia of Integer Sequences.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Sorting algorithms/Shell sort step by step in the PowerShell programming language

Source code in the powershell programming language

Function ShellSort( [Array] $data )
{
	# http://oeis.org/A108870
	$A108870 = [Int64[]] ( 1, 4, 9, 20, 46, 103, 233, 525, 1182, 2660, 5985, 13467, 30301, 68178, 153401, 345152, 776591, 1747331, 3931496, 8845866, 19903198, 44782196, 100759940, 226709866, 510097200, 1147718700, 2582367076, 5810325920, 13073233321, 29414774973 )
	$datal = $data.length - 1
	$inci = [Array]::BinarySearch( $A108870, [Int64] ( [Math]::Floor( $datal / 2 ) ) )
	if( $inci -lt 0 )
	{
		$inci = ( $inci -bxor -1 ) - 1
	}
	$A108870[ $inci..0 ] | ForEach-Object {
		$inc = $_
		$_..$datal | ForEach-Object {
			$temp = $data[ $_ ]
			$j = $_
			for( ; ( $j -ge $inc ) -and ( $data[ $j - $inc ] -gt $temp ); $j -= $inc )
			{
				$data[ $j ] = $data[ $j - $inc ]
			}
			$data[ $j ] = $temp
		}
	}
	$data
}

$l = 10000; ShellSort( ( 1..$l | ForEach-Object { $Rand = New-Object Random }{ $Rand.Next( 0, $l - 1 ) } ) )

You may also check:How to resolve the algorithm Find common directory path step by step in the Java programming language
You may also check:How to resolve the algorithm Classes step by step in the Ruby programming language
You may also check:How to resolve the algorithm Number reversal game step by step in the COBOL programming language
You may also check:How to resolve the algorithm Hello world/Text step by step in the Ezhil programming language
You may also check:How to resolve the algorithm Quine step by step in the make programming language