Rosetta Code

Sorting algorithms/Bubble sort: Difference between revisions

Page Discussion

Sorting algorithms/Bubble sort (view source)

Revision as of 01:29, 14 April 2010

646 bytes added ,  14 years ago
→‎{{header|Icon}}
m (fix tags)
Line 654:
END</lang>
 
=={{header|Icon and Unicon}}==
While bubble sort is a basic algorithm it also illustrates a difference in the way Icon handles types. The built-in operators for comparing data types make a syntactic distinction between numeric and string types. Consequently, when writing something like a bubble sort you must (a) write two versions, (b) have the sort figure it out dynamically as in this example. In practice this is unnecessary as there are built-in sort functions for basic data types and records.
<lang Icon>procedure bubblesort(X,op) #: simple bubble sort
local i,sorted
 
==={{header|Icon}}===
op := case op of { # select how to sort
"<<"|">>"|"<<="|">>="|"<"|">"|"<="|">=": proc(op,2)
"string": proc("<<",2)
"numeric": proc("<",2)
&null: if type(X[1]) == "string" then proc("<<",2)
else proc("<",2)
default: runerr(123,op)
}
 
While bubble sort is a basic algorithm it also illustrates a difference in the way Icon handles types. Built-in
while /sorted := 1 do # the sort
operators for comparing data types make a syntactic distinction between numeric and string types, and sorting
every i := 2 to *X do
structured and user-defined types requires custom code. The following code
if op(X[i],X[i-1]) then {
allows the user to specify the type of comparison to use but handles integer
X[i-1] :=: X[i]
or string lists automatically.
sorted := &null
<lang icon>invocable all
}
return X
end</lang>
 
procedure bubblesort(X,op) #: simple bubble sort
This code will demonstrate the bubble sort using arguments supplied as arguments. The last sort call on a string rather than a list illustrates how many Icon operators work on different types. The example could be made more general to deal with coercion of types like cset to sting (admittedly an uninteresting example as csets are already sorted).
local i,sorted
<lang Icon>procedure main(l2) #: demo bubblesort
op := case op of { # select how to sort
"string": "<<"
"numeric": "<"
&null: if type(X[1]) == "string" then "<<" else "<"
default: op
}
op := proc(op, 2) | runerr(123, image(op))
while /sorted := "yes" do # the sort
every i := 2 to *X do
if op(X[i],X[i-1]) then {
X[i-1] :=: X[i]
sorted := &null
}
return X
end</lang>
 
This code demonstrates the bubble sort using arguments supplied as arguments. The last sort
l1 := copy(l2) # list of strings
call on a string rather than a list illustrates how many Icon operators work on different types.
l2[1] := numeric(l2[1]) # force list with leading numeric
The example could be made more general to deal with coercion of types like cset to string
(admittedly an uninteresting example as csets are already sorted).
<lang icon>procedure main(l1) #: demo bubblesort
writes("Sorting : ")
writex(l1)
displaysort(copy(l1)) # default string sort
displaysort(copy(l1),"numeric") # explicit numeric sort
displaysort(copy(l1),"string") # explicit string sort
displaysort(copy(l1),"<<") # descending string sort
displaysort(copy(l1),"<") # descending numeric sort
displaysort(copy(l1),cmp) # ascending custom comparison
displaysort(copy(l1),"cmp") # ascending custom comparison
 
displaysort(copy(l1)) # defaultwrites("Sorting string: sort")
writex("qwerty")
displaysort(copy(l2)) # default numeric sort
displaysort(copy(l2),"stringqwerty") # explicit string # sort characters in a string
end
displaysort(copy(l1),"numeric") # explicit numeric sort
displaysort(copy(l2),"<<") # descending string sort
displaysort(copy(l2),"<") # descending numeric sort
 
procedure cmp(a,b)
displaysort("qwerty") # sort characters in a string
return a > b # Imagine a complex comparsion test here!
end
 
procedure displaysort(X,op) #: show bubblesort behavior
write writes("--- bubblesort ---with op = ",left(image(op)||":",15))
writex(bubblesort(X,op))
write("op = ",image(op))
writex("before = ",X)
writex("after = ",bubblesort(X,op))
write()
return
end
 
procedure writex(tag,X) #: helper for displaysort
if type(X) == "string" then write(image(X))
writes(\tag)
else {
if type(X) == "string" then write(image(X))
writes("[")
else {
every writes("[ ",image(!X))
every writes write(" ]",image(!X))
write(" ]") }
}
return
end</lang>
 
Sample output:
<pre>--- >bubblesort ---3 1 4 1 5 9 2 6 3
Sorting : [ "3" "1" "4" "1" "5" "9" "2" "6" "3" ]
op = "<<"
before--- bubblesort with op = &null: [ 3"1" "41" "52" "63" "223" "14" "75" "6" "9" ]
after--- bubblesort with op = "numeric": [ "1" "221" "2" "3" "43" "54" "65" "76" "9" ]
--- bubblesort with op = "string": [ "1" "1" "2" "3" "3" "4" "5" "6" "9" ]
--- bubblesort with op = "<<": [ "1" "1" "2" "3" "3" "4" "5" "6" "9" ]
--- bubblesort with op = "<": [ "1" "1" "2" "3" "3" "4" "5" "6" "9" ]
--- bubblesort with op = procedure cmp: [ "9" "6" "5" "4" "3" "3" "2" "1" "1" ]
--- bubblesort with op = "cmp": [ "9" "6" "5" "4" "3" "3" "2" "1" "1" ]
Sorting string: "qwerty"
--- bubblesort with op = &null: "eqrtwy"
-></pre>
 
==={{header|Unicon}}===
--- bubblesort ---
op = "<"
before = [ 3 "4" "5" "6" "22" "1" "7" "9" ]
after = [ "1" 3 "4" "5" "6" "7" "9" "22" ]
 
The Icon solution also works in Unicon.
--- bubblesort ---
op = &null
before = "qwerty"
after = "eqrtwy"
</pre>
 
=={{header|J}}==
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/7378"