How to resolve the algorithm Sorting algorithms/Gnome sort step by step in the BASIC programming language
Published on 12 May 2024 09:40 PM
How to resolve the algorithm Sorting algorithms/Gnome sort step by step in the BASIC programming language
Table of Contents
Problem Statement
Gnome sort is a sorting algorithm which is similar to Insertion sort, except that moving an element to its proper place is accomplished by a series of swaps, as in Bubble Sort. The pseudocode for the algorithm is:
Implement the Gnome sort in your language to sort an array (or list) of numbers.
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Sorting algorithms/Gnome sort step by step in the BASIC programming language
Source code in the basic programming language
arraybase 1
global array
dim array(15)
a = array[?,]
b = array[?]
for i = a to b
array[i] = int(rand * 100)
next i
print "unsort ";
for i = a to b
print rjust(array[i], 4);
next i
call gnomeSort(array)
print chr(10); " sort ";
for i = a to b
print rjust(array[i], 4);
next i
end
subroutine gnomeSort (array)
i = array[?,] + 1
j = i + 1
while i <= array[?]
if array[i - 1] <= array[i] then
i = j
j += 1
else
temp = array[i - 1]
array[i - 1] = array[i]
array[i] = temp
i -= 1
if i = array[?,] then
i = j
j += 1
end if
end if
end while
end subroutine
DEF PROC_GnomeSort1(Size%)
I%=2
J%=2
REPEAT
IF data%(J%-1) <=data%(J%) THEN
I%+=1
J%=I%
ELSE
SWAP data%(J%-1),data%(J%)
J%-=1
IF J%=1 THEN
I%+=1
J%=I%
ENDIF
ENDIF
UNTIL I%>Size%
ENDPROC
100 RANDOMIZE TIMER
110 DIM array(18)
120 ' Init Array
130 FOR i = 0 TO UBOUND(array)
140 array(i) = INT(RND(1)*98)+1
150 NEXT i
160 PRINT "unsort: "; : GOSUB 200
170 GOSUB 260 : ' gnomeSort
180 PRINT " sort: "; : GOSUB 200
190 END
200 ' Write Array
210 FOR i = 0 TO UBOUND(array)
220 PRINT array(i);
230 NEXT i
240 PRINT
250 RETURN
260 ' gnomeSort
270 i = 1
280 j = i+1
290 WHILE i <= UBOUND(array)
300 IF array(i-1) <= array(i) THEN
310 i = j : j = j+1
320 ELSE
330 t = array(i-1) : array(i-1) = array(i) : array(i) = t : ' swap
340 i = i-1
350 IF i = 0 THEN i = j : j = j+1
360 ENDIF
370 WEND
380 RETURN
' version 21-10-2016
' compile with: fbc -s console
' for boundry checks on array's compile with: fbc -s console -exx
Sub gnomesort(gnome() As Long)
' sort from lower bound to the highter bound
' array's can have subscript range from -2147483648 to +2147483647
Dim As Long lb = LBound(gnome)
Dim As Long ub = UBound(gnome)
Dim As Long i = lb +1, j = lb +2
While i < (ub +1)
' replace "<=" with ">=" for downwards sort
If gnome(i -1) <= gnome(i) Then
i = j
j += 1
Else
Swap gnome(i -1), gnome(i)
i -= 1
If i = lb Then
i = j
j += 1
End If
End If
Wend
End Sub
' ------=< MAIN >=------
Dim As Long i, array(-7 To 7)
Dim As Long a = LBound(array), b = UBound(array)
Randomize Timer
For i = a To b : array(i) = i : Next
For i = a To b ' little shuffle
Swap array(i), array(Int(Rnd * (b - a +1)) + a)
Next
Print "unsort ";
For i = a To b : Print Using "####"; array(i); : Next : Print
gnomesort(array()) ' sort the array
Print " sort ";
For i = a To b : Print Using "####"; array(i); : Next : Print
' empty keyboard buffer
While Inkey <> "" : Wend
Print : Print "hit any key to end program"
Sleep
End
Public Sub Main()
Dim siCount As Short
Dim siCounti As Short = 1
Dim siCountj As Short = 2
Dim siToSort As Short[] = [249, 28, 111, 36, 171, 98, 29, 448, 44, 147, 154, 46, 102, 183, 24]
Print "To sort: - ";
GoSub Display
While siCounti < siToSort.Count
If siToSort[siCounti - 1] <= siToSort[siCounti] Then
siCounti = siCountj
Inc siCountj
Else
Swap siToSort[siCounti - 1], siToSort[siCounti]
Dec siCounti
If siCounti = 0 Then
siCounti = siCountj
Inc siCountj
Endif
Endif
Wend
Print "Sorted: - ";
GoSub Display
Return
'--------------------------------------------
Display:
For siCount = 0 To siToSort.Max
Print Format(Str(siToSort[siCount]), "####");
If siCount <> siToSort.max Then Print ",";
Next
Print
Return
End
100 REM GnomeSrt.bas
110 RANDOMIZE TIMER 'remove it for Just BASIC
120 DIM ARRAY(18)
130 ' Init Array
140 FOR I = 0 TO 18
150 LET ARRAY(I) = INT(RND(1)*98)+1
160 NEXT I
170 PRINT "unsort: "; : GOSUB 210
180 GOSUB 270 : REM gnomeSort
190 PRINT " sort: "; : GOSUB 210
200 END
210 ' Write Array
220 FOR I = 0 TO 18
230 PRINT ARRAY(I);
240 NEXT I
250 PRINT
260 RETURN
270 ' gnomeSort
280 LET I = 1
290 LET J = I+1
300 WHILE I <= 18
310 IF ARRAY(I-1) <= ARRAY(I) THEN LET I = J : LET J = J+1 : GOTO 330
320 IF ARRAY(I-1) > ARRAY(I) THEN LET T = ARRAY(I-1) : LET ARRAY(I-1) = ARRAY(I) : LET ARRAY(I) = T : LET I = I-1 : IF I = 0 THEN LET I = J : LET J = J+1
330 WEND
340 RETURN
100 PROGRAM "GnomeSrt.bas"
110 RANDOMIZE
120 NUMERIC ARRAY(-5 TO 12)
130 CALL INIT(ARRAY)
140 CALL WRITE(ARRAY)
150 CALL GNOMESORT(ARRAY)
160 CALL WRITE(ARRAY)
170 DEF INIT(REF A)
180 FOR I=LBOUND(A) TO UBOUND(A)
190 LET A(I)=RND(98)+1
200 NEXT
210 END DEF
220 DEF WRITE(REF A)
230 FOR I=LBOUND(A) TO UBOUND(A)
240 PRINT A(I);
250 NEXT
260 PRINT
270 END DEF
280 DEF GNOMESORT(REF A)
290 LET I=LBOUND(A)+1:LET J=I+1
300 DO WHILE I<=UBOUND(A)
310 IF A(I-1)<=A(I) THEN
320 LET I=J:LET J=J+1
330 ELSE
340 LET T=A(I-1):LET A(I-1)=A(I):LET A(I)=T
350 LET I=I-1
360 IF I=LBOUND(A) THEN LET I=J:LET J=J+1
370 END IF
380 LOOP
390 END DEF
100 CLS
110 U = 8
120 DIM A(U+1)
130 FOR I = 0 TO U
140 A(I) = INT(RND(1)*98)
150 NEXT I
160 PRINT "unsort: "; : GOSUB 200
170 GOSUB 260 : REM gnomeSort
180 PRINT " sort: "; : GOSUB 200
190 END
200 REM Write Array
210 FOR I = 0 TO U
220 PRINT A(I);
230 NEXT I
240 PRINT
250 RETURN
260 REM gnomeSort
270 I = 1
280 J = I+1
290 IF I <= U THEN IF A(I-1) <= A(I) THEN I = J : J = J+1 : GOTO 290
300 IF I > U THEN RETURN
310 IF A(I-1) > A(I) THEN T = A(I-1) : A(I-1) = A(I) : A(I) = T : I = I-1 : IF I = 0 THEN I = J : J = J+1
320 GOTO 290
10 REM Rosetta Code problem: https://rosettacode.org/wiki/Sorting_algorithms/Gnome_sort
20 REM by Jjuanhdez, 10/2023
100 RANDOMIZE
110 LET U = 8
120 DIM A(9)
130 FOR I = 0 TO U
140 LET A(I) = INT(RND*98)
150 NEXT I
160 PRINT "UNSORT: ";
170 GOSUB 220
180 GOSUB 280
190 PRINT " SORT: ";
200 GOSUB 220
210 STOP
220 REM WRITE ARRAY
230 FOR I = 0 TO U
240 PRINT A(I);
250 NEXT I
260 PRINT
270 RETURN
280 REM GNOMESORT
290 LET I = 1
300 LET J = I+1
310 IF I <= U THEN 350
320 IF I > U THEN 190
330 IF A(I-1) > A(I) THEN 400
340 GOTO 310
350 IF A(I-1) <= A(I) THEN 370
360 GOTO 320
370 LET I = J
380 LET J = J+1
390 GOTO 310
400 LET T = A(I-1)
410 LET A(I-1) = A(I)
420 LET A(I) = T
430 LET I = I-1
440 IF I = 0 THEN 460
450 GOTO 310
460 LET I = J
470 LET J = J+1
480 GOTO 310
490 END
SUB gnomeSort (a() AS LONG)
DIM i AS LONG, j AS LONG
i = 1
j = 2
WHILE (i < UBOUND(a) + 1)
IF (a(i - 1) <= a(i)) THEN
i = j
INCR j
ELSE
SWAP a(i - 1), a(i)
DECR i
IF 0 = i THEN
i = j
INCR j
END IF
END IF
WEND
END SUB
FUNCTION PBMAIN () AS LONG
DIM n(9) AS LONG, x AS LONG
RANDOMIZE TIMER
OPEN "output.txt" FOR OUTPUT AS 1
FOR x = 0 TO 9
n(x) = INT(RND * 9999)
PRINT #1, n(x); ",";
NEXT
PRINT #1,
gnomeSort n()
FOR x = 0 TO 9
PRINT #1, n(x); ",";
NEXT
CLOSE 1
END FUNCTION
Procedure GnomeSort(Array a(1))
Protected Size = ArraySize(a()) + 1
Protected i = 1, j = 2
While i < Size
If a(i - 1) <= a(i)
;for descending SORT, use >= for comparison
i = j
j + 1
Else
Swap a(i - 1), a(i)
i - 1
If i = 0
i = j
j + 1
EndIf
EndIf
Wend
EndProcedure
RANDOMIZE TIMER 'RANDOMIZE for True BASIC
DIM array(-5 TO 12)
CALL iniciarray(array())
PRINT "unsort: ";
CALL escritura(array())
CALL gnomeSort(array())
PRINT
PRINT " sort: ";
CALL escritura(array())
END
SUB escritura (array())
FOR i = LBOUND(array) TO UBOUND(array)
PRINT array(i);
NEXT i
PRINT
END SUB
SUB gnomeSort (array())
LET i = LBOUND(array) + 1
LET j = i + 1
DO WHILE i <= UBOUND(array)
IF array(i - 1) <= array(i) THEN
LET i = j
LET j = j + 1
ELSE
LET T = array(i - 1)
LET array(i - 1) = array(i)
LET array(i) = T
LET i = i - 1
IF i = LBOUND(array) THEN
LET i = j
LET j = j + 1
END IF
END IF
LOOP
END SUB
SUB iniciarray (array())
FOR i = LBOUND(array) TO UBOUND(array)
LET array(i) = (RND * 98) + 1
NEXT i
END SUB
dim a(0 to n-1) as integer
'...more code...
sort:
i = 1
j = 2
while(i < ubound(a) - lbound(a))
if a(i-1) <= a(i) then
i = j
j = j + 1
else
swap a(i-1), a(i)
i = i - 1
if i = 0 then
i = j
j = j + 1
end if
end if
wend
100 CLS
110 LET U = 8
120 ARRAY A
130 FOR I = 0 TO U
140 LET A(I) = INT(RAND(1)*98)
150 NEXT I
160 PRINT "UNSORT: ";
170 GOSUB 220
180 GOSUB 280
190 PRINT " SORT: ";
200 GOSUB 220
210 STOP
220 REM WRITE ARRAY
230 FOR I = 0 TO U
240 PRINT A(I); " ";
250 NEXT I
260 PRINT
270 RETURN
280 REM GNOMESORT
290 LET I = 1
300 LET J = I+1
310 IF I <= U THEN 350
320 IF I > U THEN 190
330 IF A(I-1) > A(I) THEN 400
340 GOTO 310
350 IF A(I-1) <= A(I) THEN 370
360 GOTO 320
370 LET I = J
380 LET J = J+1
390 GOTO 310
400 LET T = A(I-1)
410 LET A(I-1) = A(I)
420 LET A(I) = T
430 LET I = I-1
440 IF I = 0 THEN 460
450 GOTO 310
460 LET I = J
470 LET J = J+1
480 GOTO 310
490 END
dim A(18)
[initArray]
for i = 0 to 18
A(i) = int(rnd(1)*98)+1
next i
print "unsort: ";
gosub [writeArray]
gosub [gnomeSort]
print " sort: ";
gosub [writeArray]
end
[writeArray]
for i = 0 to 18
print A(i); " ";
next i
print
return
[gnomeSort]
i = 1
j = i+1
while i <= 18
if A(i-1) <= A(i) then
i = j
j = j+1
else
t = A(i-1) : A(i-1) = A(i) : A(i) = t
i = i-1
if i = 0 then i = j : j = j+1
end if
wend
return
RANDOMIZE !RAMDOMIZE TIMER en QBASIC
DIM array(-5 TO 12)
CALL iniciarray(array())
PRINT "unsort: ";
CALL escritura(array())
CALL gnomeSort(array())
PRINT
PRINT " sort: ";
CALL escritura(array())
END
SUB escritura (array())
FOR i = LBOUND(array) TO UBOUND(array)
PRINT array(i);
NEXT i
PRINT
END SUB
SUB gnomeSort (array())
LET i = LBOUND(array) + 1
LET j = i + 1
DO WHILE i <= UBOUND(array)
IF array(i - 1) <= array(i) THEN
LET i = j
LET j = j + 1
ELSE
LET T = array(i - 1)
LET array(i - 1) = array(i)
LET array(i) = T
LET i = i - 1
IF i = LBOUND(array) THEN
LET i = j
LET j = j + 1
END IF
END IF
LOOP
END SUB
SUB iniciarray (array())
FOR i = LBOUND(array) TO UBOUND(array)
LET array(i) = (RND * 98) + 1
NEXT i
END SUB
PRINT "Gnome sort:"
n = FUNC (_InitArray)
PROC _ShowArray (n)
PROC _Gnomesort (n)
PROC _ShowArray (n)
PRINT
END
_Gnomesort PARAM (1) ' Gnome sort
LOCAL (2)
b@=1
c@=2
DO WHILE b@ < a@
IF @(b@-1) > @(b@) THEN
PROC _Swap (b@, b@-1)
b@ = b@ - 1
IF b@ THEN
CONTINUE
ENDIF
ENDIF
b@ = c@
c@ = c@ + 1
LOOP
RETURN
_Swap PARAM(2) ' Swap two array elements
PUSH @(a@)
@(a@) = @(b@)
@(b@) = POP()
RETURN
_InitArray ' Init example array
PUSH 4, 65, 2, -31, 0, 99, 2, 83, 782, 1
FOR i = 0 TO 9
@(i) = POP()
NEXT
RETURN (i)
_ShowArray PARAM (1) ' Show array subroutine
FOR i = 0 TO a@-1
PRINT @(i),
NEXT
PRINT
RETURN
Private Function gnomeSort(s As Variant) As Variant
Dim i As Integer: i = 1
Dim j As Integer: j = 2
Dim tmp As Integer
Do While i < UBound(s)
If s(i) <= s(i + 1) Then
i = j
j = j + 1
Else
tmp = s(i)
s(i) = s(i + 1)
s(i + 1) = tmp
i = i - 1
If i = 0 Then
i = j
j = j + 1
End If
End If
Loop
gnomeSort = s
End Function
Public Sub main()
Debug.Print Join(gnomeSort([{5, 3, 1, 7, 4, 1, 1, 20}]), ", ")
End Sub
dim array(15)
a = 0
b = arraysize(array(),1)
print "unsort: ";
for i = a to b
array(i) = int(ran(98))+1
print array(i), " ";
next i
print "\n sort: ";
gnomeSort(array())
for i = a to b
print array(i), " ";
next i
print "\n"
end
sub gnomeSort(array())
local ub, ul, i, j, temp
lb = 0 : ub = arraysize(array(),1)
i = lb +1 : j = lb +2
while i <= ub
// replace "<=" with ">=" for downwards sort
if array(i -1) <= array(i) then
i = j
j = j + 1
else
temp = array(i -1)
array(i -1) = array(i)
array(i) = temp
i = i - 1
if i = lb then
i = j
j = j + 1
fi
fi
wend
end sub
You may also check:How to resolve the algorithm Tonelli-Shanks algorithm step by step in the D programming language
You may also check:How to resolve the algorithm Ternary logic step by step in the Python programming language
You may also check:How to resolve the algorithm Factorial step by step in the C programming language
You may also check:How to resolve the algorithm Binary digits step by step in the PHP programming language
You may also check:How to resolve the algorithm Flow-control structures step by step in the MUMPS programming language