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:

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: 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..        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 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   )

 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.

 :