Author 
Topic: selection sort (Read 2868 times) 

tooanalytical
Senior Member
member is offline
Posts: 1739


selection sort
« Thread started on: May 31^{st}, 2012, 11:00am » 

A search for the last 1500 days showed about three good examples of Selection Sort, and none of them in the Articles & Tutorials board.
This type of SORT uses two FOR loops to cut an array of data into two parts: a sorted part and an unsorted part. The code searches for the smallest (or largest) value in the set of unsorted data and exchanges with the lowest index position of the unsorted part of the data.
I ran this example several times and it showed as reliable.
Code:dim numbers(30)
for x=1 to 15
anyx=1+int(15*rnd(1))
let numbers(x)=anyx
next x
for x0=1 to 15
print x0;" ";numbers(x0)
next x0
'SORTING ALGORITHM
needExchange=0
for i=1 to 15
iOfLow=i
asIfLow=numbers(i)
for j=i+1 to 15
if numbers(j)<asIfLow then
asIfLow=numbers(j)
iOfLow=j
rem exchange item j with item i
rem in case condition was met.
needExchange=1
end if
next j 'this makes +1 added to j
if needExchange=1 then
temp=numbers(i)
numbers(i)=numbers(iOfLow)
numbers(iOfLow)=temp
needExchange=0
end if
next i
'HOW WELL DID SORTING WORK?
print "*****Results*****"
for x1=1 to 15
print x1;" ";numbers(x1)
next x1
END

« Last Edit: May 31^{st}, 2012, 11:02am by tooanalytical » 
Logged




cassiope01
Senior Member
member is offline
Gender:
Posts: 669


Re: selection sort
« Reply #1 on: Jun 1^{st}, 2012, 07:42am » 

I remember some post here with this kind of code :)
Code:size = 50
dim bubble(size)
dim selection(size)
print "Initial array: "
for i = 1 to size
bubble(i) = sizei+1
selection(i) = bubble(i)
print bubble(i); " ";
next i
print : print
' shuffle
print"shuffled"
For i = size to 1 Step 1
x = Int(Rnd(1) * i) + 1
temp = bubble(x)
bubble(x) = bubble(i)
bubble(i) = temp
selection(i) = bubble(i)
print bubble(i); " ";
Next i
print : print
'test bubble sort
for i = 1 to size1
for j = 1 to sizei
compareBubble = compareBubble+1
if bubble(j) > bubble(j+1) then ' SMALLEST to LARGEST
swapBubble = swapBubble+1
tmp = bubble(j)
bubble(j) = bubble(j+1)
bubble(j+1) = tmp
end if
next j
next i
'test selection sort
for i = 1 to size1
min = selection(i)
pos = i
for j = i+1 to size
compareSelect = compareSelect+1
if selection(j) < min then
pos = j
min = selection(j)
end if
next j
swapSelect = swapSelect+1
selection(pos) = selection(i)
selection(i) = min
next i
print "Bubble sort"
print compareBubble; " comparisons, "; swapBubble; " swaps."
for i = 1 to size
print bubble(i); " ";
next i
print : print
print "Selection sort"
print compareSelect; " comparisons, "; swapSelect; " swaps."
for i = 1 to size
print selection(i); " ";
next i
print


Logged

"It is better to mobilize its intelligence for stupid things, rather than mobilizing its stupidity for intelligent things."



TyCamden
Global Moderator
member is offline
Gender:
Posts: 1431


Re: selection sort
« Reply #2 on: Jun 1^{st}, 2012, 11:57am » 

I keep the following SORT programs on file for review in my pc:
For sorting words...
1.) TacSort
Code:' tacsort 1.0  09/11/10 compares tacsort to bubble sort and insert sort
' 1.1  09/12/10 no comparion to others sorts, tacsort only
' 1.2  09/12/10 reads until eof, then dimensions arrays based on input count
' this program no longer reads the first 5,000 but rather to eof.
' 1.3  9/13/10 ascending or descending
'
' tacsort splits your file in array a$, into 4 parts
' then runs 4 insert sorts and merges the parts back into the whole  p6$.
'
' this version was designed to sort an array of words, ascending or descending.
'
' who should use this sort? If you are sorting a small list which runs quickly,
' no sense in using tacsort. If you have a bubble sort that runs too long, you may want to swtich.
'
' bubble = 3:35 comments to tcoffin1@cfl.rr.com
' insert = 1:51 times are based on 5,000 records
' TACsort = :28
'
' ***** NOTE  lowhigh$, must be set properly for ascending or descending sort
' a  will sort a to z (lower to higher), z  will sort z to a (higher to lower)
' no need to change code, just the variable lowhigh$
'
lowhigh$="a":sort$="ascending":if lowhigh$="z" then sort$="descending"
if lowhigh$<>"a" and lowhigh$<>"z" then print " reset lowhigh varable to a or z":end
'
open "csv5000.csv" for input as #1
while eof(#1) = 0:input #1, w$:v=v+1:wend ' read for array size
close #1:lh$=lowhigh$
' for test comparisons only v=5000
dim a$(v),p2$(v),p3$(v),p4$(v),p5$(v),p6$(v) ' original, < 100, >99 <107, >106 <115, > 114, merged
open "csv5000.csv" for input as #1:for x=1 to v:input#1,w$:a$(x)=w$:next x
close #1:cls:print:print,"Tacsort 1.3  ";sort$:print:print " Splitting file ";time$();
for x=1 to v
w$=left$(a$(x),1):w=asc(w$):if w>114 then f5=f5+1:p5$(f5)=a$(x):goto [str_done]
if (w>106) and (w<115) then f4=f4+1:p4$(f4)=a$(x):goto [str_done]
if (w>99) and (w<107) then f3=f3+1:p3$(f3)=a$(x):goto [str_done]
if w<100 then f2=f2+1:p2$(f2)=a$(x)
[str_done]
next x
print " ";f2;" ";f3;" ";f4;" ";f5:print " TACsort 1 ";:n=f2
for i=2 TO n
t$=p2$(i):j=i:if lh$="z" then [tag1]
while (j>1) and (t$<p2$(j1)):p2$(j)=p2$(j1):j=j1:wend
goto [tag1a]
[tag1]
while (j>1) and (t$>p2$(j1)):p2$(j)=p2$(j1):j=j1:wend
[tag1a]
if j<>i then p2$(j)=t$
next i
print " TACsort 2 ";:n=f3
for i=2 TO n
t$=p3$(i):j=i:if lh$="z" then [tag2]
while (j>1) and (t$<p3$(j1)):p3$(j)=p3$(j1):j=j1:wend
goto [tag2a]
[tag2]
while (j>1) and (t$>p3$(j1)):p3$(j)=p3$(j1):j=j1:wend
[tag2a]
if j<>i then p3$(j)=t$
next i
print " TACsort 3 ";:n=f4
for i=2 TO n
t$=p4$(i):j=i:if lh$="z" then [tag3]
while (j>1) and (t$<p4$(j1)):p4$(j)=p4$(j1):j=j1:wend
goto [tag3a]
[tag3]
while (j>1) and (t$>p4$(j1)):p4$(j)=p4$(j1):j=j1:wend
[tag3a]
if j<>i then p4$(j)=t$
next i
print " TACsort 4 ",;:n=f5
for i=2 TO n
t$=p5$(i):j=i:if lh$="z" then [tag4]
while (j>1) and (t$<p5$(j1)):p5$(j)=p5$(j1):j=j1:wend
goto [tag4a]
[tag4]
while (j>1) and (t$>p5$(j1)):p5$(j)=p5$(j1):j=j1:wend
[tag4a]
if j<>i then p5$(j)=t$
next i
' for lowhigh$ = a
if lowhigh$="z" then [next_merge]
for x=1 to f2:p=p+1:p6$(p)=p2$(x):next x:for x=1 to f3:p=p+1:p6$(p)=p3$(x):next x
for x=1 to f4:p=p+1:p6$(p)=p4$(x):next x:for x=1 to f5:p=p+1:p6$(p)=p5$(x):next x
goto [end_sort]
'
[next_merge]
for x=1 to f5:p=p+1:p6$(p)=p5$(x):next x:for x=1 to f4:p=p+1:p6$(p)=p4$(x):next x
for x=1 to f3:p=p+1:p6$(p)=p3$(x):next x:for x=1 to f2:p=p+1:p6$(p)=p2$(x):next x
[end_sort]
print:print " Merge end ";time$();" records = ";p
open "csv5000sorted.csv" for output as #2
for y=1 to v
print #2, p6$(y)
next y
close #2
print " Sorted file created and saved."
end
2. Uncle Ben's large Sort:
Code:' UncleBen's sorting program for a large file of items...
open "csv5000.csv" for input as #1
while eof(#1) = 0:input #1, w$:v=v+1:wend ' read for array size
close #1:lh$=lowhigh$
' for test comparisons only v=5000
dim a$(v)
open "csv5000.csv" for input as #1:for x=1 to v:input#1,w$:a$(x)=w$:next x
close #1
start = time$("ms")
CALL QSort.a1 1, v
print "It took ";(time$("ms")  start) / 1000; " seconds"
print "The array contents are sorted?  "; IsSorted.a2( 1, v)
'for i = 1 to v : print a$(i) : next
open "csv5000sorted.csv" for output as #2
for y=1 to v
print #2, a$(y)
next y
close #2
print " sorted file created and saved."
END
SUB QSort.a1 Start, Finish
i = Start
j = Finish
x$ = a$(int((i+j)/2))
while i <= j
while a$(i) < x$
i = i + 1
wend
while x$ < a$(j)
j = j  1
wend
if i <= j THEN
temp$ = a$(i)
a$(i) = a$(j)
a$(j) = temp$
i = i + 1
j = j  1
END if
wend
if j  Start < 17 THEN
CALL InsertionSort.a4 Start, j
ELSE
CALL QSort.a1 Start, j
END if
if Finish  i < 17 THEN
CALL InsertionSort.a4 i, Finish
ELSE
CALL QSort.a1 i, Finish
END if
END SUB
SUB InsertionSort.a4 Start, Finish
for i = Start + 1 to Finish
value$ = a$(i)
j = i
while j > Start
if value$ >= a$(j1) THEN exit while
a$(j) = a$(j1)
j = j1
wend
a$(j) = value$
next i
END SUB
FUNCTION IsSorted.a2( Start, Finish)
IsSorted.a2 = 1
for i = Start + 1 to Finish
if a$(i) < a$(i1) THEN
IsSorted.a2 = 0
exit for
END if
next i
END FUNCTION
for NUMBERS:
3. sort example:
Code:size = 15
dim selection(size)
dim selection2(size)
print "Initial array: "
for i = 1 to size
selection(i) = int(rnd(1)*100) + 1
selection2(i) = selection(i)
print selection(i); " ";
next i
print : print
' selection sort  low to high
for i = 1 to size1
min = selection(i)
pos = i
for j = i+1 to size
compareSelect = compareSelect+1
if selection(j) < min then
pos = j
min = selection(j)
end if
next j
swapSelect = swapSelect+1
selection(pos) = selection(i)
selection(i) = min
next i
' selection sort  high to low
for i = 1 to size1
min = selection2(i)
pos = i
for j = i+1 to size
compareSelect = compareSelect+1
if selection2(j) > min then
pos = j
min = selection2(j)
end if
next j
swapSelect = swapSelect+1
selection2(pos) = selection2(i)
selection2(i) = min
next i
print "Selection sort  low to high"
print compareSelect; " comparisons, "; swapSelect; " swaps."
for i = 1 to size
print selection(i); " ";
next i
print
print
print "Selection sort  high to low"
print compareSelect; " comparisons, "; swapSelect; " swaps."
for i = 1 to size
print selection2(i); " ";
next i
print


Logged

TyCamden
Please give credit if you use code I post, no need to ask for permission.
Just BASIC 1.01, Windows 7 Home Premium version (2009), AMD Athelon II 320 DualCore Processor 2.10 GHz  4.00 GB RAM (3.75 usable)  64bit OS



TyCamden
Global Moderator
member is offline
Gender:
Posts: 1431


Re: selection sort
« Reply #3 on: Jun 4^{th}, 2012, 5:50pm » 

I recently had a need to sort words and found that my saved examples irritated me. The list of words was small, so I thought I would just setup a basic sort.
Then I found that the user would have a need to sort the data several different ways while running the program. The data is a list of items, and each item could fall within different groups.
The program would have to sort three different ways: alphabetically, alphabetically within each group, and by entry order.
I am oldschool, so the program handles everything with GOSUB's (not SUBS, and not FUNCTIONS). So, it is not the best way to do the job, but for me, it gets the job done.
The following is a demo of what happens in the program that I made...
Code:READ NumberOfGroups
READ NumberOfItems
DIM Groups$(NumberOfGroups)
DIM A$(NumberOfItems,3)
' A$(X,1) is the item Name
' A$(X,2) is the Group of the item
' A$(X,3) is the item Entry Order
DIM TempReSortA$(NumberOfItems,3)
GOSUB [setupData]
[DoAgain]
GOSUB [showData]
GOSUB [getSortChoice]
SELECT CASE choice
CASE 1
GOSUB [SortDataAlpha]
CASE 2
GOSUB [SortDataAlphaByGroup]
CASE ELSE
GOSUB [SortDataEntry]
END SELECT
GOTO [DoAgain]
' subroutines ................
[SortDataEntry]
' SORT BY ENTRY ORDER
[redoSortDataEntry]
SortChangeFlag = 0
FOR X = 1 to NumberOfItems1
IF VAL(A$(X,3)) > VAL(A$(X+1,3)) THEN
' switch em
FOR Y = 1 to 3
temp$ = A$(X,Y)
A$(X,Y) = A$(X+1,Y)
A$(X+1,Y) = temp$
NEXT Y
SortChangeFlag = 1
END IF
NEXT X
IF SortChangeFlag <> 0 THEN
GOTO [redoSortDataEntry]
END IF
RETURN
[SortDataAlphaByGroup]
' SORT ALPHABETICALLY WITHIN GROUPS
spotOfTheOrder = 1
REDIM TempReSortA$(NumberOfItems,3)
FOR X = 1 to NumberOfGroups
FOR Y = 1 to NumberOfItems
IF A$(Y,2) = Groups$(X) THEN
FOR Z = 1 to 3
TempReSortA$(spotOfTheOrder,Z) = A$(Y,Z)
NEXT Z
spotOfTheOrder = spotOfTheOrder + 1
END IF
NEXT Y
NEXT X
FOR X = 1 to NumberOfItems
FOR Y = 1 to 3
A$(X,Y) = TempReSortA$(X,Y)
NEXT Y
NEXT X
' Now sort the items
FOR X = 1 to NumberOfGroups
[sdabgAgain]
sdabgMoveFlag = 0
FOR Y = 1 to NumberOfItems1
IF ( A$(Y,2) = Groups$(X) ) AND ( A$(Y+1,2) = Groups$(X) ) THEN
' This item is in the currently sorting group
' and needs to be looked at
IF A$(Y,1) > A$(Y+1,1) THEN
' switch em
FOR Z = 1 to 3
temp$ = A$(Y,Z)
A$(Y,Z) = A$(Y+1,Z)
A$(Y+1,Z) = temp$
sdabgMoveFlag = 1
NEXT Z
END IF
END IF
NEXT Y
IF sdabgMoveFlag = 1 THEN
GOTO [sdabgAgain]
END IF
NEXT X
RETURN
[SortDataAlpha]
' SORT ALPHABETICALLY
[redoSortDataAlpha]
SortChangeFlag = 0
FOR X = 1 to NumberOfItems1
IF A$(X,1) > A$(X+1,1) THEN
' switch em
FOR Y = 1 to 3
temp$ = A$(X,Y)
A$(X,Y) = A$(X+1,Y)
A$(X+1,Y) = temp$
SortChangeFlag = 1
NEXT Y
END IF
NEXT X
IF SortChangeFlag <> 0 THEN
GOTO [redoSortDataAlpha]
END IF
RETURN
[getSortChoice]
PRINT "1  SORT ALPHABETICALLY"
PRINT "2  SORT ALPHABETICALLY WITHIN GROUPS"
PRINT "3  SORT BY ENTRY ORDER"
PRINT
INPUT "CHOICE ? "; choice
IF ( choice <> INT(choice) ) OR (choice < 1 ) OR (choice > 3 ) THEN
PRINT "INVALID CHOICE. TRY AGAIN."
PRINT
GOTO [getSortChoice]
END IF
RETURN
[showData]
PRINT
PRINT "DATA..."
PRINT
FOR X = 1 to NumberOfItems
PRINT A$(X,1);" [";A$(X,2);"]"
NEXT X
PRINT
RETURN
[setupData]
' Setup the data that would need to be manipulated.
FOR X = 1 TO NumberOfGroups
READ X$
Groups$(X) = X$
NEXT X
FOR X = 1 TO NumberOfItems
FOR Y = 1 to 3
READ X$
A$(X,Y) = X$
NEXT Y
NEXT X
RETURN
' Number of Groups
DATA 4
' Data for Groups
' Number of Items
DATA 10
DATA "Cars", "Books", "Spices", "People"
' Data for Items
DATA "Buick", "Cars", "1"
DATA "Hitler", "People", "2"
DATA "Cujo", "Books", "3"
DATA "Salt", "Spices", "4"
DATA "Lincoln", "People", "5"
DATA "The Bible", "Books", "6"
DATA "Hardy", "People", "7"
DATA "Pepper", "Spices", "8"
DATA "Toyota", "Cars", "9"
DATA "Laurel", "People", "10"

« Last Edit: Jun 4^{th}, 2012, 5:51pm by TyCamden » 
Logged

TyCamden
Please give credit if you use code I post, no need to ask for permission.
Just BASIC 1.01, Windows 7 Home Premium version (2009), AMD Athelon II 320 DualCore Processor 2.10 GHz  4.00 GB RAM (3.75 usable)  64bit OS



tsh73
JBSupporter
member is offline
Gender:
Posts: 3636


Re: selection sort
« Reply #4 on: Jun 5^{th}, 2012, 02:09am » 

To sort same data in a three ways, it is enough to change compare function. All other stuff stays the same: Code:READ NumberOfGroups
READ NumberOfItems
DIM Groups$(NumberOfGroups)
DIM A$(NumberOfItems,3)
' A$(X,1) is the item Name
' A$(X,2) is the Group of the item
' A$(X,3) is the item Entry Order
DIM TempReSortA$(NumberOfItems,3)
GOSUB [setupData]
[DoAgain]
GOSUB [showData]
GOSUB [getSortChoice]
'sort, as it was
[redoSort]
SortChangeFlag = 0
FOR X = 1 to NumberOfItems1
IF compare(X, choice) > 0 THEN
' switch em
FOR Y = 1 to 3
temp$ = A$(X,Y)
A$(X,Y) = A$(X+1,Y)
A$(X+1,Y) = temp$
NEXT Y
SortChangeFlag = 1
END IF
NEXT X
IF SortChangeFlag <> 0 THEN
GOTO [redoSort]
END IF
GOTO [DoAgain]
' subroutines ................
function compare(X, sortMode)
'compares X and X+1 item
'returns 1 if item(X)>item(X+1)
'sortMode
'PRINT "1  SORT ALPHABETICALLY"
'PRINT "2  SORT ALPHABETICALLY WITHIN GROUPS"
'PRINT "3  SORT BY ENTRY ORDER"
SELECT CASE sortMode
CASE 1
compare = (A$(X,1) > A$(X+1,1))
CASE 2
'compare = (A$(X,2)+A$(X,1) > A$(X+1,2)+A$(X+1,1)) 'sort by Group+Name.
'Actually should pad groups to same length:
compare = (pad$(A$(X,2),10)+A$(X,1) > pad$(A$(X+1,2),10)+A$(X+1,1))
CASE 3
compare = (VAL(A$(X,3)) > VAL(A$(X+1,3)))
END SELECT
end function
function pad$(a$,n)
pad$=a$+space$(nlen(a$))
end function
[getSortChoice]
PRINT "1  SORT ALPHABETICALLY"
PRINT "2  SORT ALPHABETICALLY WITHIN GROUPS"
PRINT "3  SORT BY ENTRY ORDER"
PRINT ""
PRINT "0  QUIT"
PRINT
INPUT "CHOICE ? "; choice
if choice =0 then end
IF ( choice <> INT(choice) ) OR (choice < 1 ) OR (choice > 3 ) THEN
PRINT "INVALID CHOICE. TRY AGAIN."
PRINT
GOTO [getSortChoice]
END IF
RETURN
[showData]
PRINT
PRINT "DATA..."
PRINT
FOR X = 1 to NumberOfItems
PRINT A$(X,1);" [";A$(X,2);"]"
NEXT X
PRINT
RETURN
[setupData]
' Setup the data that would need to be manipulated.
FOR X = 1 TO NumberOfGroups
READ X$
Groups$(X) = X$
NEXT X
FOR X = 1 TO NumberOfItems
FOR Y = 1 to 3
READ X$
A$(X,Y) = X$
NEXT Y
NEXT X
RETURN
' Number of Groups
DATA 4
' Data for Groups
' Number of Items
DATA 10
DATA "Cars", "Books", "Spices", "People"
' Data for Items
DATA "Buick", "Cars", "1"
DATA "Hitler", "People", "2"
DATA "Cujo", "Books", "3"
DATA "Salt", "Spices", "4"
DATA "Lincoln", "People", "5"
DATA "The Bible", "Books", "6"
DATA "Hardy", "People", "7"
DATA "Pepper", "Spices", "8"
DATA "Toyota", "Cars", "9"
DATA "Laurel", "People", "10"


Logged

Q: "And if I took your codes and compile them, and sell them for a profit"? A: Go ahead. I had my share of good then I coded it for fun, if you can make better use of it  please do. (enjoying JB 1.01 on WinXP, netbook and desktop)



TyCamden
Global Moderator
member is offline
Gender:
Posts: 1431


Re: selection sort
« Reply #5 on: Jun 5^{th}, 2012, 11:22am » 

on Jun 5^{th}, 2012, 02:09am, tsh73 wrote:To sort same data in a three ways, it is enough to change compare function. All other stuff stays the same:
...CODE... 

Nice !
And also the following line can be removed entirely...
Code:DIM TempReSortA$(NumberOfItems,3)


Logged

TyCamden
Please give credit if you use code I post, no need to ask for permission.
Just BASIC 1.01, Windows 7 Home Premium version (2009), AMD Athelon II 320 DualCore Processor 2.10 GHz  4.00 GB RAM (3.75 usable)  64bit OS



