Posted: Wed Mar 10, 2004 9:14 pm Post subject: sorting procedures
here's a small list i have compiled of simple sorting algorithms...
code:
%swap and shift procedures
procedure swap (var list : array 1 .. * of int, i, j : int)
const temp := list (i)
list (i) := list (j)
list (j) := temp
end swap
procedure shift (var list : array 1 .. * of int, i, j : int)
const temp := list (j)
for decreasing k : j .. i + 1
list (k) := list (k - 1)
end for
list (i) := temp
end shift
%insertion sort
procedure insertionSort (var list : array 1 .. * of int)
for j : 2 .. upper(list)
var i := 1
loop
exit when i = j or list (i) >= list (j)
i += 1
end loop
shift (list, i, j)
end for
end insertionSort
%selection sort
procedure selectionSort (var list : array 1 .. * of int)
for i : 1 .. upper(list) - 1
var locationOfSmallest := i
for j : i + 1 .. upper(list)
if list (j) <= list (locationOfSmallest) then
locationOfSmallest := j
end if
end for
swap (list, i, locationOfSmallest)
end for
end selectionSort
%bubble sort
procedure bubbleSort (var list : array 1 .. * of int)
for j : 1 .. upper(list) - 1
const last := upper(list) - j + 1
for k : 1 .. last - 1
if list (k) > list (k + 1) then
swap (list, k, k + 1)
end if
end for
end for
end bubbleSort
%merge sort
procedure merge (var list : array 1 .. * of int, first, middle, last : int)
var temp : array 1 .. last of int
var point1 := first
var point2 := middle + 1
var point3 := first
loop
exit when point3 > last
if point1 < middle + 1 and (point2 > last or list (point1) < list (point2)) then
temp (point3) := list (point1)
point1 := point1 + 1
else
temp (point3) := list (point2)
point2 := point2 + 1
end if
point3 += 1
end loop
for i : first .. last
list (i) := temp (i)
end for
end merge
procedure mergeSort (var list : array 1 .. * of int, first, last : int)
if last > first then
const middle := (first + last) div 2
mergeSort (list, first, middle)
mergeSort (list, middle + 1, last)
merge (list, first, middle, last)
end if
end mergeSort
%quick sort
procedure quickSort (var list : array 1 .. * of int, left, right : int)
var pivotPlace : int
swap (list, left, (left + right) div 2)
var lastSmall := left
for i : left + 1 .. right
if list (i) <= list (left) then
lastSmall += 1
swap (list, lastSmall, i)
end if
end for
swap (list, left, lastSmall)
pivotPlace := lastSmall
if left < pivotPlace - 1 then
quickSort (list, left, pivotPlace - 1)
end if
if pivotPlace + 1 < right then
quickSort (list, pivotPlace + 1, right)
end if
end quickSort
%main proggy
%create random data
var numbers : array 1 .. 10 of int
put "unsorted:" : 10 ..
for i : 1 .. 10
numbers (i) := Rand.Int (1, 1000)
put numbers (i) : 5 ..
end for
put "\n\nsorted:" : 12 ..
for i : 1 .. 10
put numbers (i) : 5 ..
end for
-zylum
Sponsor Sponsor
Catalyst
Posted: Wed Mar 10, 2004 9:26 pm Post subject: (No subject)
to add to this:
heres a qSort that retains an associated index array (proves to be useful)
code:
procedure qSort (var a : array 1 .. * of real, var b : array 1 .. * of int, l, h : int)
if l < h then
var aH : real
var bH : int
var i : int := l;
var j : int := h
var mid : real := a (l)
loop
loop
exit when a (i) >= mid
i += 1
end loop
loop
exit when a (j) <= mid
j -= 1
end loop
if i <= j then
aH := a (i)
a (i) := a (j)
a (j) := aH
bH := b (i)
b (i) := b (j)
b (j) := bH
i += 1
j -= 1
end if
exit when i > j
end loop
qSort (a, b, l, j)
qSort (a, b, i, h)
end if
end qSort
and heres a shell sort
code:
proc Shell (var numbers : array 0 .. * of real, arraysize : int)
var j, increment : int
var temp, temp2 : real
increment := 3
loop
locate (1, 1)
put increment
if increment > 0 then
for i : 0 .. arraysize
j := i
temp := numbers (i)
loop
if (j >= increment) and (numbers (j - increment) > temp) then
numbers (j) := numbers (j - increment);
j := j - increment;
else
exit
end if
end loop
numbers (j) := temp
end for
if (increment / 2 not= 0) then
increment := increment div 2;
elsif (increment = 1) then
increment := 0
else
increment := 1
end if
else
exit
end if
end loop
end Shell
Delos
Posted: Fri Mar 12, 2004 12:57 pm Post subject: (No subject)
Ah, sorting...how we love thee.
Number sorts are good...how about word sorts? Hehehe...have fun with those...
Tony
Posted: Fri Mar 12, 2004 3:54 pm Post subject: (No subject)
sorting words is the same as numbers cuz you can compare them alphabetically... or to be more accurate, ASCII values of characters
code:
if "tony" > "dan" then
put "score"
else
put "boo"
end if
Posted: Fri Mar 12, 2004 6:04 pm Post subject: (No subject)
yeah so for the sorts listed above, turn all variable types form int to string. well almost all...
-zylum
the_short1
Posted: Sun Mar 14, 2004 6:45 pm Post subject: (No subject)
yea sorting programsd are fun... ive had to make a couple in my day.... and to convert from oen to another is ez...
if word > bigword then
bigword = word
so realy u can convert all the strings to int to make it work for umbers.... i did that... saved me a lot of type for assignments.. one week in our questions we had to make a word sort.. enxt week one of our questions was to make a number sort... as soon as the teacher said that... i said... what do i do now.. im done.. whiole the clas was toiling away
SuperGenius
Posted: Mon Mar 15, 2004 3:06 pm Post subject: (No subject)
so if I wanted to sort an array of string I could just use a bubble sort?
zylum
Posted: Mon Mar 15, 2004 3:10 pm Post subject: (No subject)
yup, but in the procedure the arguments need to be string not int...
-zylum
Sponsor Sponsor
SuperGenius
Posted: Mon Mar 15, 2004 8:42 pm Post subject: (No subject)
cool.... I was going to add a high score list to my connect 4 game which rules by the way, but then I didnt becuase I didnt know how, so mabye I will now.
GlobeTrotter
Posted: Sat Mar 12, 2005 10:28 pm Post subject: (No subject)
Here's a program that compares the sorting times of those originally posted.
code:
%swap and shift procedures
procedure swap (var list : array 1 .. * of int, i, j : int)
const temp := list (i)
list (i) := list (j)
list (j) := temp
end swap
procedure shift (var list : array 1 .. * of int, i, j : int)
const temp := list (j)
for decreasing k : j .. i + 1
list (k) := list (k - 1)
end for
list (i) := temp
end shift
%insertion sort
procedure insertionSort (var list : array 1 .. * of int)
for j : 2 .. upper (list)
var i := 1
loop
exit when i = j or list (i) >= list (j)
i += 1
end loop
shift (list, i, j)
end for
end insertionSort
%selection sort
procedure selectionSort (var list : array 1 .. * of int)
for i : 1 .. upper (list) - 1
var locationOfSmallest := i
for j : i + 1 .. upper (list)
if list (j) <= list (locationOfSmallest) then
locationOfSmallest := j
end if
end for
swap (list, i, locationOfSmallest)
end for
end selectionSort
%bubble sort
procedure bubbleSort (var list : array 1 .. * of int)
for j : 1 .. upper (list) - 1
const last := upper (list) - j + 1
for k : 1 .. last - 1
if list (k) > list (k + 1) then
swap (list, k, k + 1)
end if
end for
end for
end bubbleSort
%merge sort
procedure merge (var list : array 1 .. * of int, first, middle, last : int)
var temp : array 1 .. last of int
var point1 := first
var point2 := middle + 1
var point3 := first
loop
exit when point3 > last
if point1 < middle + 1 and (point2 > last or list (point1) < list (point2)) then
temp (point3) := list (point1)
point1 := point1 + 1
else
temp (point3) := list (point2)
point2 := point2 + 1
end if
point3 += 1
end loop
for i : first .. last
list (i) := temp (i)
end for
end merge
procedure mergeSort (var list : array 1 .. * of int, first, last : int)
if last > first then
const middle := (first + last) div 2
mergeSort (list, first, middle)
mergeSort (list, middle + 1, last)
merge (list, first, middle, last)
end if
end mergeSort
%quick sort
procedure quickSort (var list : array 1 .. * of int, left, right : int)
var pivotPlace : int
swap (list, left, (left + right) div 2)
var lastSmall := left
for i : left + 1 .. right
if list (i) <= list (left) then
lastSmall += 1
swap (list, lastSmall, i)
end if
end for
swap (list, left, lastSmall)
pivotPlace := lastSmall
if left < pivotPlace - 1 then
quickSort (list, left, pivotPlace - 1)
end if
if pivotPlace + 1 < right then
quickSort (list, pivotPlace + 1, right)
end if
end quickSort
%main proggy
%create random data
var numbers : array 1 .. 500 of int
var timeUsed : array 0 .. 5 of int
var speed : array 1 .. 5 of int
sysclock (timeUsed (0))
for i : 1 .. upper (numbers)
numbers (i) := Rand.Int (1, 1000)
end for
insertionSort (numbers)
sysclock (timeUsed (1))
for i : 1 .. upper (numbers)
numbers (i) := Rand.Int (1, 1000)
end for
selectionSort (numbers)
sysclock (timeUsed (2))
for i : 1 .. upper (numbers)
numbers (i) := Rand.Int (1, 1000)
end for
bubbleSort (numbers)
sysclock (timeUsed (3))
for i : 1 .. upper (numbers)
numbers (i) := Rand.Int (1, 1000)
end for
mergeSort (numbers, lower (numbers), upper (numbers))
sysclock (timeUsed (4))
for i : 1 .. upper (numbers)
numbers (i) := Rand.Int (1, 1000)
end for
quickSort (numbers, lower (numbers), upper (numbers))
sysclock (timeUsed (5))
for i : 1 .. 5
speed (i) := timeUsed (i) - timeUsed (i - 1)
end for
put "Insertion Sort: ", speed(1)
put "Selection Sort: ", speed(2)
put "Bubble Sort: ", speed(3)
put "Merge Sort: ", speed(4)
put "Quick Sort: ", speed(5)
Mr. T
Posted: Mon Mar 28, 2005 12:47 am Post subject: (No subject)
can u gimme examples of progs that u would need to use sorting (aside from high score lists)
Weelkid_29
Posted: Mon Jan 23, 2006 8:05 pm Post subject: (No subject)
i need help sorting strings alphabetically
blaster009
Posted: Mon Jan 23, 2006 8:33 pm Post subject: (No subject)
It's really not difficult...Turing handles String comparisons just like it does integer comparisons. Just change the data types to strings.
Here's my sorting algorithms:
code:
% Swap Procedure
proc swap (var swapArray : array 0 .. * of int, swapNumOne : int, swapNumTwo : int)
var tempNum : int
tempNum := swapArray (swapNumOne)
swapArray (swapNumOne) := swapArray (swapNumTwo)
swapArray (swapNumTwo) := tempNum
end swap
% Bubble Sort - Only NINE lines!
proc bubbleSort (var sortArray : array 0 .. * of int)
for i : lower (sortArray) .. upper (sortArray)
for j : lower (sortArray) + 1 .. upper (sortArray)
if sortArray (j) <= sortArray (j - 1) then
swap (sortArray, j, j - 1)
end if
end for
end for
end bubbleSort
% Selection Sort - Only ELEVEN lines!
proc selectSort (var sortArray : array 0 .. * of int)
var sortNum : int := lower (sortArray)
for i : lower (sortArray) .. upper (sortArray)
for j : lower (sortArray) .. upper (sortArray) - i
if sortArray (j) >= sortArray (sortNum) or j = lower (sortArray) then
sortNum := j
end if
end for
swap (sortArray, sortNum, upper (sortArray) - i)
end for
end selectSort
I'm quite proud of my Bubble Sort
person
Posted: Tue Jan 24, 2006 8:06 pm Post subject: (No subject)
no offense, but bubble and selection sort kinda sux
Clayton
Posted: Wed Jan 25, 2006 8:17 am Post subject: (No subject)
Pwned wrote:
can u gimme examples of progs that u would need to use sorting (aside from high score lists)
mostly databases, records, ect. they can be used quite a bit, especially for a teacher b/c they have to go through hundreds of marks (too bad for them )
Register
Wiki
Blog
Search
Turing
Chat Room
Members
sorting words is the same as numbers cuz you can compare them alphabetically... or to be more accurate, ASCII values of characters
