Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 RegisterRegister   
 sorting procedures
Index -> Programming, Turing -> Turing Submissions
Goto page 1, 2  Next
View previous topic Printable versionDownload TopicRate TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
zylum




PostPosted: 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
Sponsor
Sponsor
Sponsor
sponsor
Catalyst




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




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




PostPosted: Fri Mar 12, 2004 3:54 pm   Post subject: (No 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
Latest from compsci.ca/blog: Tony's programming blog. DWITE - a programming contest.
zylum




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




PostPosted: 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.. WinkWinkWink Very Happy Very Happy Very Happy Very Happy Very Happy whiole the clas was toiling away
SuperGenius




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




PostPosted: 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
SuperGenius




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




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




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




PostPosted: Mon Jan 23, 2006 8:05 pm   Post subject: (No subject)

i need help sorting strings alphabetically
blaster009




PostPosted: 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 Smile
person




PostPosted: Tue Jan 24, 2006 8:06 pm   Post subject: (No subject)

no offense, but bubble and selection sort kinda sux
Clayton




PostPosted: 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 Laughing Laughing Laughing )
Display posts from previous:   
   Index -> Programming, Turing -> Turing Submissions
View previous topic Tell A FriendPrintable versionDownload TopicRate TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 1 of 2  [ 27 Posts ]
Goto page 1, 2  Next
Jump to:   


Style:  
Search: