-----------------------------------

zylum

Wed Mar 10, 2004 9:14 pm


sorting procedures

-----------------------------------

here's a small list i have compiled of simple sorting algorithms...

%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 (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) = mid
                i += 1
            end loop
            loop
                exit when a (j)  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

Fri Mar 12, 2004 12:57 pm



-----------------------------------

Ah, sorting...how we love thee.

Number sorts are good...how about word sorts?  Hehehe...have fun with those...


-----------------------------------

Tony

Fri Mar 12, 2004 3:54 pm



-----------------------------------

:? sorting words is the same as numbers cuz you can compare them alphabetically... or to be more accurate, ASCII values of characters

if "tony" > "dan" then
put "score"
else
put "boo"
end if



-----------------------------------

zylum

Fri Mar 12, 2004 6:04 pm



-----------------------------------

yeah so for the sorts listed above, turn all variable types form int to string. well almost all...

-zylum


-----------------------------------

the_short1

Sun Mar 14, 2004 6:45 pm



-----------------------------------

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.. ;););) :D :D :D :D :D whiole the clas was toiling away


-----------------------------------

SuperGenius

Mon Mar 15, 2004 3:06 pm



-----------------------------------

so if I wanted to sort an array of string I could just use a bubble sort?


-----------------------------------

zylum

Mon Mar 15, 2004 3:10 pm



-----------------------------------

yup, but in the procedure the arguments need to be string not int...

-zylum


-----------------------------------

SuperGenius

Mon Mar 15, 2004 8:42 pm



-----------------------------------

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

Sat Mar 12, 2005 10:28 pm



-----------------------------------

Here's a program that compares the sorting times of those originally posted.


%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 (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)