Board Logo
« selection sort »

Welcome Guest. Please Login or Register.
Jan 18th, 2018, 3:51pm


Conforums Terms of Service | Membership Rules | Home | Search | Recent Posts | Notification | Format Your Message | Installation FAQ

This board is not meant for general discussion, it is meant for posting articles to help others.
For general discussions use the appropriate board, which best describes your problem area.

« Previous Topic | Next Topic »
Pages: 1  Notify Send Topic Print
 thread  Author  Topic: selection sort  (Read 2868 times)
tooanalytical
Senior Member
ImageImageImageImageImage


member is offline

Avatar




PM


Posts: 1739
xx selection sort
« Thread started on: May 31st, 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 31st, 2012, 11:02am by tooanalytical » User IP Logged

cassiope01
Senior Member
ImageImageImageImageImage


member is offline

Avatar




PM

Gender: Male
Posts: 669
xx Re: selection sort
« Reply #1 on: Jun 1st, 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) = size-i+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 size-1
    for j = 1 to size-i
        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 size-1
    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
 
User IP Logged

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


member is offline

Avatar




PM

Gender: Male
Posts: 1431
xx Re: selection sort
« Reply #2 on: Jun 1st, 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$(j-1)):p2$(j)=p2$(j-1):j=j-1:wend
    goto [tag1a]
[tag1]
    while (j>1) and (t$>p2$(j-1)):p2$(j)=p2$(j-1):j=j-1: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$(j-1)):p3$(j)=p3$(j-1):j=j-1:wend
    goto [tag2a]
[tag2]
    while (j>1) and (t$>p3$(j-1)):p3$(j)=p3$(j-1):j=j-1: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$(j-1)):p4$(j)=p4$(j-1):j=j-1:wend
    goto [tag3a]
[tag3]
    while (j>1) and (t$>p4$(j-1)):p4$(j)=p4$(j-1):j=j-1: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$(j-1)):p5$(j)=p5$(j-1):j=j-1:wend
    goto [tag4a]
[tag4]
    while (j>1) and (t$>p5$(j-1)):p5$(j)=p5$(j-1):j=j-1: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$(j-1) THEN exit while
            a$(j) = a$(j-1)
            j = j-1
        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$(i-1) 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 size-1
    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 size-1
    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 

User IP 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 Dual-Core Processor 2.10 GHz - 4.00 GB RAM (3.75 usable) - 64-bit OS
TyCamden
Global Moderator
ImageImageImageImageImage


member is offline

Avatar




PM

Gender: Male
Posts: 1431
xx Re: selection sort
« Reply #3 on: Jun 4th, 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 old-school, 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 NumberOfItems-1
        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 NumberOfItems-1
            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 NumberOfItems-1
        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 4th, 2012, 5:51pm by TyCamden » User IP 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 Dual-Core Processor 2.10 GHz - 4.00 GB RAM (3.75 usable) - 64-bit OS
tsh73
JB-Supporter


member is offline

Avatar




PM

Gender: Male
Posts: 3636
xx Re: selection sort
« Reply #4 on: Jun 5th, 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 NumberOfItems-1
        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$(n-len(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"
 
User IP 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
ImageImageImageImageImage


member is offline

Avatar




PM

Gender: Male
Posts: 1431
xx Re: selection sort
« Reply #5 on: Jun 5th, 2012, 11:22am »

on Jun 5th, 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) 

User IP 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 Dual-Core Processor 2.10 GHz - 4.00 GB RAM (3.75 usable) - 64-bit OS
Pages: 1  Notify Send Topic Print
« Previous Topic | Next Topic »

Conforums Terms of Service | Membership Rules | Home | Search | Recent Posts | Notification | Format Your Message | Installation FAQ

Donate $6.99 for 50,000 Ad-Free Pageviews!

| |

This forum powered for FREE by Conforums ©
Sign up for your own Free Message Board today!
Terms of Service | Privacy Policy | Conforums Support | Parental Controls