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

Published on 12 May 2024 09:40 PM
#Yabasic

How to resolve the algorithm Sorting algorithms/Shell sort step by step in the Yabasic 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 Yabasic programming language

Source code in the yabasic programming language

export sub shell_sort(x())
// Shell sort based on insertion sort

   local gap, i, j, first, last, tempi, tempj

   last = arraysize(x(),1)
   gap = int(last / 10) + 1
   while(TRUE)
	first = gap + 1
	for i = first to last
	   	tempi = x(i)
	    	j = i - gap
	    	while(TRUE)
			tempj = x(j)
			if tempi >= tempj then
		    		j = j + gap
		    		break
			end if
			x(j+gap) = tempj
			if j <= gap then
		    		break
			end if
			j = j - gap
	    	wend
	    	x(j) = tempi
	next i
	if gap = 1 then
	   	return
	else
	   	gap = int(gap / 3.5) + 1
	end if
   wend
end sub

if peek$("library") = "main" then

	clear screen
	
	ITEMS = 100
	dim numeros(ITEMS)
	
	for n = 1 to ITEMS
		numeros(n) = ran(ITEMS + 1)
	next n
	
	print time$
	shell_sort(numeros())
	print time$
	print "Press a key to see ordered numbers."
	inkey$
	
	for n = 1 to ITEMS
		print numeros(n),", ";
	next n

end if

You may also check:How to resolve the algorithm Order disjoint list items step by step in the Python programming language
You may also check:How to resolve the algorithm Long primes step by step in the Forth programming language
You may also check:How to resolve the algorithm Eertree step by step in the Objeck programming language
You may also check:How to resolve the algorithm Ternary logic step by step in the ALGOL 68 programming language
You may also check:How to resolve the algorithm Subtractive generator step by step in the ooREXX programming language