I'm lost - Sorting

Tallguy · **Posted:** Fri Feb 06, 2009 10:17 am

Hey guys, its been a while since I was programming and i'm back in class.

I always found the concept of sorting to be difficult so i'm asking if anyonme could explain the code below.

Turing:

%Alex van der Mout

var number : int
put "How many numbers are there? " ..
get number

var list : array 1 .. number of int
put "What are the numbers?"
for i : 1 .. number
get list (i)
end for

put "The numbers in order are . . . "
var sortlist : array 1 .. number of int
for i : 1 .. number
var smallest := 999
var where : int
for j : 1 .. number
if list (j) < smallest then
smallest := list (j)
where := j
end if
end for
sortlist (i) := smallest
list (where) := 999
end for

for i : 1 .. number
put sortlist (i)
end for

I understand the arrays and getting the numbers and all, i don't get how to to sort them, i got this code from turing help.

Can anyone please explain this in a simple way? Thanks.

Mod Edit: Syntax tags, not quote tags!

code:

[syntax="turing"]Code Here[/syntax]

DemonWasp · **Posted:** Fri Feb 06, 2009 10:50 am

Here's a hint: the program works as long as you don't enter any numbers over 998. If you enter 999, 1000, or anything higher, it fails because "where" is never assigned.

The sorting algorithm implemented is a fairly simple sort. All it does is finds the lowest number over and over and over again, putting it into a new array. If you take a careful look at the inside of the first for loop, you'll see it trying to find the lowest number still in the list: it assumes the smallest number will be less than 999, and if it sees anything smaller than 999, it takes that as its new "smallest" and keeps searching. Once it's found what it thinks is the smallest in the array, it moves that to the sorted array and puts in the flag value of 999 in the array.

The problem comes in if you have, say, 5000 in your array. The algorithm will never find 5000 as the smallest because it keeps setting things to 999, which is decidedly less than 5000(!). So when it's moved all the other numbers outside, it freaks out because the "where" variable never got set to anything, so it has no value.

If you just change the 999 to maxint in both cases it works for any integer up to the maximum of 2^31-1 (the most you can represent in a signed 32-bit integer, which is what Turing uses by default).

Aside: this method of sorting is quite inefficient, as it consumes O ( N ^ 2 ) computation time and O ( N ) additional space. Not a problem in this case, but if you have more than 1000 numbers it could easily take essentially forever.

P.S. Don't forget to use [ syntax ] tags or at the very least some [ code ] tags.

Zren · **Posted:** Fri Feb 06, 2009 9:43 pm

I just learned another sorting algorithm the other day that works for no matter how high it is. It's basically the same as yours except a few different things.
Forgive me if I'm wrong explaning this, this is how I interpreted it.

Turing:

procedure bubbleSort( a : array)

% You list of numbers
const TOTALNUM := 15
const FIRST := 0
const LAST := TOTALNUM - 1

var list : array FIRST .. LAST of int % 15 numbers

for i : FIRST .. LAST
% Assign values to list
list (i) := Rand.Int (0, maxint div 2)

% Output to screen [For Example]
put i : 3, ": ", list (i) : 15
end for

% Sort the specified list

/* We need to run through the all the list items 1 less
* than the total. Since it only takes that many moves to
* move from the top to the bottom or vice versa.
*/
for pass : FIRST .. (LAST - 1)

/* We need to run through the all the list items 1 less
* than the total againt though this time is more crucial
* since this variable is being used to affect our list.
* Since we're going to be checking the first and second,
* then second and third...etc. We don't need to do this
* as many times as their is numbers since on the last one
* it will compare the last number +1 and throw an out of
* bounds error.
*/
for element : FIRST .. (LAST - 1)
/* Here is where we actually compare the two, in order
* to sort the list from lowest to highest, we'd move the
* higher number down in the list. So we check to see if
* list item a is lower than b.
*/
if (list (element) > list (element + 1)) then
/* If so we swap a and b */
var temp : int := list (element)
list (element) := list (element + 1)
list (element + 1) := temp
end if
end for
end for

for i : FIRST .. LAST
locate (i + 1, 30)

% Output to screen [For Example]
put i : 3, ": ", list (i) : 15
end for

DarkRider · **Posted:** Sat Feb 07, 2009 12:08 pm

To make bubble sort more efficient I would suggest only checking the values that need to be checked and not the entire list:

Turing:

/*
* Same as what Zren posted except it only interates through
* the parts of the list that are needed. The algorithm knows
* that the last item in the list is already sorted so it does
* not need to check that item.
*/

proc Bubble (var List : array 1 .. * of int)
var Ending := upper (List)
var Buffer : int
var Swapped := false
loop
Swapped := false
for i : 1 .. Ending
if i + 1 <= Ending and List (i) > List (i + 1) then
Buffer := List (i)
List (i) := List (i + 1)
List (i + 1) := Buffer
Swapped := true
end if
end for
exit when not Swapped
Ending -= 1
end loop
end Bubble

You could also use a variant on bubble sort called "ripple" sort. Instead of just checking the list from beginning to ending you could also check the list from ending to beginning:

Turing:

/*
* Very similar to what Zren posted. It varies on the traditional
* bubble sort by not only interating down the list but also up
* the list. On the first pass of the list is checking for a value
* that is the greatest and moves it to the end of the list. On
* the second pass of the list it is checking for a value that is
* the least and moves it to the front of the list. Like bubble
* sort the algorithm knows that the least and greatest value are
* already in place and does not need to check them. The Beginning
* and Ending variables are adjusted to suit.
*/

proc Ripple (var List : array 1 .. * of int)
var Beginning := 1
var Ending := upper (List)
var Buffer : int
var Swapped := false
loop
Swapped := false
for i : 1 .. Ending
if i + 1 <= Ending and List (i) > List (i + 1) then
Buffer := List (i)
List (i) := List (i + 1)
List (i + 1) := Buffer
Swapped := true
end if
end for
exit when not Swapped
Ending -= 1
Swapped := false
for decreasing i : Ending .. Beginning
if i + 1 >= Beginning and List (i) > List (i + 1) then
Buffer := List (i)
List (i) := List (i + 1)
List (i + 1) := Buffer
Swapped := true
end if
end for
exit when not Swapped
Beginning += 1
end loop
end Ripple

If anyone needs a more in-depth explanation of those two algorithms please let me know and I'll explain them better. For other more efficient algorithms check out this Wikipedia article. It lists a bunch of possible sorting algorithms that could be used, and explains how they can be implemented. You could also check out this thread that contains a bunch of already implemented algorithms using Turing.

Tallguy · **Posted:** Mon Feb 09, 2009 12:03 pm

Hey thanks for the feed back, i found this one that works with my program....

Like this is my assignment

Quote:

/*1. Create a program which prompts the user for a student's name and their mark in a test
which is marked out of 67. Use a sentinel to determine the end of input. Output the marks
in chart form (Name and Mark) in the order input as a percent. Sort the data in
descending order according to marks and redisplay the sorted list in chart form. Save as
lastname_array#1.t.*/

now i got everything except that i don't know how to connect ttwo arrays so that there linked like 1a =2a 1b=2b etc. this is what i got so far

Turing:

/*Alex van der mout*/
setscreen ("graphics:350,500") %set the screen to a specfic size
drawfillbox (0, 0, maxx, maxy, 12) %draws a
color (0) %TEXT COLOR
colorback (12) %TEXT COLOR BACKGROUND

var num : int %variable for the number of students
put "How many students are there?" %prompts user for amount of students
get num %gets how amny students there are
put "" %enter a space between commands
put "Enter student name, and grade out of 67" %prompts user to enter student nam & mark

var grades : array 1 .. num of real %two arrays that get marks/name for how many students there are
var names : array 1 .. num of string
var percent : array 1 .. num of real %array for determining the percent grade of each mark

for i : 1 .. num %ccontinues the loop from 1 to how many students there are-
put "Name: " ..
get names (i) : * %gets name one, then name two etc
put "Mark: " ..
get grades (i) %gets grade one, then grade teo
if grades (i) > 67 then %if the user enters a grade higher then 67(the max) then do the following
grades (i) := 0 %set the grade entered back to zero
put "Grade higher then 67, not valid enter grade again"
put "Mark: " ..
get grades (i) %re-get the invalid mark
end if
percent (i) := grades (i) / 67 * 100 %changes all the grades to percent by dividing by 67 and multiplying by 100
put ""
end for

cls %clear the screen

for i : 1 .. num %this section puts the marks in percent form with the students name
put names (i), " has a ", round (percent (i)), "% on the test."
end for

put ""
put "From lowest mark to highest, the class has the following..."

var random : boolean := true
for decreasing last : num .. 1
for i : 1 .. num - 1
if percent (i) > percent (i + 1) then
random := false
const temp := percent (i)
percent (i) := percent (i + 1)
percent (i + 1) := temp
end if
end for
exit when random
end for

for i : 1 .. num
put round (percent (i)), "%"
end for

how do i link the two arrays together? does anyone know what i'm talking about? the name and marks have to correspond

DemonWasp · **Posted:** Mon Feb 09, 2009 1:01 pm

You're talking about "associated arrays". All you need to do is ensure that the swaps you do in your sorting method swap values in both arrays in the same manner. Wherever you would swap locations i and j of array1, you need to ALSO swap locations i and j of array2. This will keep the associations correct.

If you plan to continue with programming, I would recommend looking into Turing's records. Instead of having array1, array2, array3 and so on, you could have array of objects that each have fields 1, 2, and 3. It may not sound like much of a difference, but it's actually a huge improvement in readability, among other things.

Tallguy · **Posted:** Mon Feb 09, 2009 1:05 pm

i would, but i have to use arrays for this assignment...

DemonWasp · **Posted:** Mon Feb 09, 2009 3:24 pm

That's exactly it, you use arrays of records, instead of arrays of the basic types (int, char, real, string, etc)

So instead of:

code:

var field1 : array 1..num of int
var field2 : array 1..num of string

you'd have

code:

type thing
record
field1 : int
field2 : string
end record

var things : array 1..num of thing

Either way, I did tell you how to solve the problem with your existing primitive-arrays.

Tallguy · **Posted:** Wed Feb 11, 2009 8:35 am

Thanks DemonWasp, i was going to do it the way you mention, but wasn't allowed to do so.....(don't ask)
Thanks all of you for helping me in this assignment, posted below is my finised code.......

Insectoid · **Posted:** Fri Feb 13, 2009 12:32 pm

After a bit, sorting becomes rather easy. One day it will 'click' and you will wonder why you didn't see the answer before. I personally prefer ripple or 'swap' sorting, as it's really fast to code, albeit slow to run.

	Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB Username: Password: Register
Wiki Blog Search Turing Chat Room Members