Computer Science Canada

sorting procedures
Author:  zylum [ 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

%insertionSort (numbers, 10)
%selectionSort (numbers, 10)
%bubbleSort (numbers, 10)
%mergeSort (numbers, 1, 10)
quickSort (numbers, 1, 10)

put "\n\nsorted:" : 12 ..
for i : 1 .. 10
    put numbers (i) : 5 ..
end for


-zylum
Author:  Catalyst [ Wed Mar 10, 2004 9:26 pm ]
Post 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
Author:  Delos [ Fri Mar 12, 2004 12:57 pm ]
Post subject: 
Ah, sorting...how we love thee.

Number sorts are good...how about word sorts? Hehehe...have fun with those...
Author:  Tony [ Fri Mar 12, 2004 3:54 pm ]
Post subject: 
Confused 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
Author:  zylum [ Fri Mar 12, 2004 6:04 pm ]
Post subject: 
yeah so for the sorts listed above, turn all variable types form int to string. well almost all...

-zylum
Author:  the_short1 [ Sun Mar 14, 2004 6:45 pm ]
Post 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.. WinkWinkWink Very Happy Very Happy Very Happy Very Happy Very Happy whiole the clas was toiling away
Author:  SuperGenius [ Mon Mar 15, 2004 3:06 pm ]
Post subject: 
so if I wanted to sort an array of string I could just use a bubble sort?
Author:  zylum [ Mon Mar 15, 2004 3:10 pm ]
Post subject: 
yup, but in the procedure the arguments need to be string not int...

-zylum
Author:  SuperGenius [ Mon Mar 15, 2004 8:42 pm ]
Post 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.
Author:  GlobeTrotter [ Sat Mar 12, 2005 10:28 pm ]
Post 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)
Author:  Mr. T [ Mon Mar 28, 2005 12:47 am ]
Post subject: 
can u gimme examples of progs that u would need to use sorting (aside from high score lists)
Author:  Weelkid_29 [ Mon Jan 23, 2006 8:05 pm ]
Post subject: 
i need help sorting strings alphabetically
Author:  blaster009 [ Mon Jan 23, 2006 8:33 pm ]
Post 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 Smile
Author:  person [ Tue Jan 24, 2006 8:06 pm ]
Post subject: 
no offense, but bubble and selection sort kinda sux
Author:  Clayton [ Wed Jan 25, 2006 8:17 am ]
Post 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 Laughing Laughing Laughing )
Author:  nemesest [ Thu Mar 02, 2006 8:38 pm ]
Post subject: 
Hi.

I am wondering if someone can help me explain what this does:

procedure swap (var list : array 1 .. * of int, i, j : int)

what does "*" do and what are i and j?

thank you.
Author:  nemesest [ Thu Mar 02, 2006 9:19 pm ]
Post subject: 
Quote:
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

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

%main proggy

%create random data
var numbers : array 1 .. 5000 of int

for i : 1 .. 5000
numbers (i) := i
end for

insertionSort (numbers)

for i : 1 .. 5000
end for

drawfill (1, 50, 50, 50)


Also, borrowing the author's code, would that be a fair test? I have found that the reversed numbers are faster than ordered numbers? Is this right?
Author:  Delos [ Thu Mar 02, 2006 9:47 pm ]
Post subject: 
nemesest wrote:
Hi.

I am wondering if someone can help me explain what this does:

procedure swap (var list : array 1 .. * of int, i, j : int)

what does "*" do and what are i and j?

thank you.


The '*'s indicate that the upper bounds of the array are not known at compilation time. They are dynamic. This is because the array being passed to the procedure may be of various lengths.
i and j are simply parameters - in this case specifying which subset of the array is to be sorted.

As for using the code - technically zylum posted this up as a service to other users. However, if you do use it you really should cite him as the creator/coder.
My personal view is that if you are not able to understand most, if not all, of the code, then you shouldn't be using it. If you were using this on an assignment, for instance, you might get asked what a particular set of lines means...that could be troublesome.
Author:  nemesest [ Sat Mar 04, 2006 9:34 am ]
Post subject: 
I'm sorry for asking so many questions but

Quote:
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


What is the purpose of the underlined code?

Quote:
i += 1


And what does + do?

As for using the creator's code I am only using it for myself. I learned insertion, bubble, and selection sort at school, so I wanted to look at other sorts.
Author:  Cervantes [ Sat Mar 04, 2006 11:36 am ]
Post subject: 
He's declaring a constant. A constant is just like a variable, except it cannot be changed. The temp constant is storing the value of list (j) so that its value isn't lost when we go to shift things around.

+ is the addition operator. += is a combination of the addition (+) and assignment (:=) operators.
code:

var x := 5
x += 7      % this is the same as 'x := x + 7'
put x


We can do this with other operators, such as -, *, /, mod...
Author:  StealthArcher [ Mon Sep 17, 2007 10:19 pm ]
Post subject: 
person @ Tue Jan 24, 2006 7:06 pm wrote:
no offense, but bubble and selection sort kinda sux


Bubble sort is better than almost anything, when finding one discrepancy in a pile of data.


Namely you have a list of 10000 words, only one is out of place, bsort will do it the fastest.
Author:  Clayton [ Tue Sep 18, 2007 7:10 am ]
Post subject:  RE:sorting procedures
Dude... this thing is over a year old...

Also, bubble sort is incredibly slow when compared to many other sorts. Period.
Author:  rdrake [ Tue Sep 18, 2007 11:45 am ]
Post subject:  Re: RE:sorting procedures
Clayton @ Tue Sep 18, 2007 7:10 am wrote:
Also, bubble sort is incredibly slow when compared to many other sorts. Period.
It may be slower in almost every case, but it's fast when it only has to make one pass.
Author:  Clayton [ Tue Sep 18, 2007 4:11 pm ]
Post subject:  RE:sorting procedures
And how many times is that going to happen? Sure bubble sort is fast when you have to go through once, but it's not going to happen all that often. You're almost always better off going with something else like a quick sort.
Author:  StealthArcher [ Tue Sep 18, 2007 6:05 pm ]
Post subject:  Re: sorting procedures
Unless you dont know how to write it.

(case-in-point myself 4 months ago...)
Author:  Dragsz [ Sat Mar 07, 2015 9:50 pm ]
Post subject:  RE:sorting procedures
Is there any way to do this without procedure? I haven't learned that yet
Author:  Nathan4102 [ Sat Mar 07, 2015 10:29 pm ]
Post subject:  RE:sorting procedures
I mean you could, but you shouldn't. Look up some tutorials on procedures and functions, they're really easy to work with and it'll make everything so much easier.

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy