Explaining this Algorithm
Firstly, sorry if im posting this in the wrong place.
Im currently doing my A2 Computing alevel, and on every paper a question on algorithms come up. I really dont understand them, for example this one:
MODULE XXX
Input numbers into a list
REPEAT
FOR index IN RANGE 1 to (list length -1) DO
IF list (index) < list (index +1) THEN
Interchange the contents of both elements
UNTIL no interchanges
Output the contents of each element in the list
END MODULE XXX
Could someone please explain to me what each line actually means.
Also if anyone knows a way that i could learn how to understand these sort of algorithms, e.g. a website that teaches you this kind of stuff, could you please let me know about it.
Im really stressed out, cos these questions are worth usually around 8 marks and the total marks is 60. so please help!
Re: Explaining this Algorithm
Quote:
Originally Posted by Desert Eagle
Could someone please explain to me what each line actually means.
Also if anyone knows a way that i could learn how to understand these sort of algorithms, e.g. a website that teaches you this kind of stuff, could you please let me know about it.
The pseudocode you posted is a (very poor) sorting algorithm.
I'm not sure what it is you don't understand, since it's all native English. The most complicated line:
FOR index IN RANGE 1 to (list length -1) DO
means "For each element in the list, in order, do the following:"
Re: Explaining this Algorithm
so if the numbers to be input into the list are 4, 2, 9, 7, 5, 1 and 3, state the contents of the list following the execution of the algorithm.
Re: Explaining this Algorithm
IF list (index) < list (index +1) THEN swap
So the intended order after the sort is from highest to lowest.
Re: Explaining this Algorithm
Quote:
Originally Posted by Desert Eagle
so if the numbers to be input into the list are 4, 2, 9, 7, 5, 1 and 3, state the contents of the list following the execution of the algorithm.
It will go like this:
Insert { 4, 2, 9, 7, 5, 1, 3 } into array. (How is not specified.)
1: 4
2: 2
3: 9
4: 7
5: 5
6: 1
7: 3
Begin main loop. (REPEAT...UNTIL)
Inner loop:
1: 4 is not < 2, so do nothing
2: 2 < 9, so swap #2 & #3
3: 2 < 7, so swap #3 & #4
4: 2 < 5, so swap #4 & #5
5: 2 is not < 1, so do nothing
6: 1 < 3, so swap 6 & 7
Result: { 4, 9, 7, 5, 2, 3, 1 }
Exchanges have happened, so REPEAT. (How we know this is not specified.)
Inner loop:
1: 4 < 9, so swap #1 & #2
2: 4 < 7, so swap #2 & #3
3: 4 < 5, so swap #3 & #4
4: 4 is not < 2, so do nothing
5: 2 < 3, so swap #5 & #6
6: 2 is not < 1, so do nothing
Result: { 9, 7, 5, 4, 3, 2, 1 }
Exchanges have happened, so REPEAT.
Inner loop:
1: 9 is not < 7, so do nothing
2: 7 is not < 5, so do nothing
3: 5 is not < 4, so do nothing
4: 4 is not < 3, so do nothing
5: 3 is not < 2, so do nothing
6: 2 is not < 1, so do nothing
Result: { 9, 7, 5, 4, 3, 2, 1 }
No exchanges were made, so exit outer loop. (REPEAT...UNTIL)
Output the sorted list. (How is not specified.)
Re: Explaining this Algorithm
[To Ellis Dee: Sorry to repeat all your work I just noticed. I had done the following and got called to breakfast and then finished up. I decided to post anyway as it might cover the material another way.]
Quote:
Originally Posted by Desert Eagle
Firstly, sorry if im posting this in the wrong place
You are right, this forum is not exactly what you are looking for. As Ellis Dee said, the algorithm you posted is not Visual Basic code. It is not any language known to us, so it is probably "pseudo code" meaning code written to show logic and using syntax dreamed up by the author.
You might be more at home in The QBasic Forum (see URL under my signature). The people there are more concerned with simple stuff.
Anyway, let's extract your pseudo-code statements:
MODULE XXX
END MODULE XXX
- Surely you have no question there
Input numbers into a list
- In QBasic, this says "input numbers into an array". An array is a list of variable values so that one can reference a given value easily. Here is an array loaded with the data you gave:
- list(1)=4
- list(2)=2
- list(3)=9
- list(4)=7
- list(5)=5
- list(6)=1
- list(7)=3
REPEAT
UNTIL no interchanges
- The instructions between these two statements will be repeated until no new interchange is made
FOR index IN RANGE 1 to (list length -1) DO
ENDFOR
- A variable called "index" will be given the value "1" and the instructions between these two statements will be executed, the "index" will be 2, etc. until it is one short of the size of the list
IF list (index) < list (index +1) THEN
Interchange the contents of both elements
ENDIF
Thus the instructions actually executed are
IF list(1) < list(2) THEN ...
but list(1)=4 and list(2)=2 according to your data so no interchange will occur
IF list(2) < list(3) THEN ...
but list(2)=2 and list(3)=9 and since 2<9, interchange will take place
So now we have
- list(1)=4
- list(2)=9 <----- these two values were swapped
- list(3)=2 <-----
- list(4)=7
- list(5)=5
- list(6)=1
- list(7)=3
So we keep going until we finish with list(6) and List(7).
And, since a swap occurred, we start over. Work it out manually to see what happens.
Output the contents of each element in the list
- Here it is done in QBasic, which you might have on your computer or can download at my link:
Code:
zList(1) = 4
zList(2) = 2
zList(3) = 9
zList(4) = 7
zList(5) = 5
zList(6) = 1
zList(7) = 3
DO
Interchange = 0
FOR i = 1 TO 6
IF zList(i) < zList(i + 1) THEN
SWAP zList(i), zList(i + 1)
Interchange = 1
END IF
NEXT i
LOOP UNTIL Interchange = 0
FOR i = 1 TO 7: PRINT zList(i); : NEXT i
Mac
http://www.network54.com/Index/10167
Re: Explaining this Algorithm
Quote:
Originally Posted by Ellis Dee
The pseudocode you posted is a (very poor) sorting algorithm.
Bubblesort :)
Re: Explaining this Algorithm
Quote:
Originally Posted by Logophobic
Bubblesort :)
First thing I thought when Dee said that :-)
Bubblesort isn't a poor sorting method, it's just a simple one
And Eagle, this is okay (in my opinion) as a forum to post the question in if you don't know what language it is and you are learning Visual Basic in class...however, you might find http://www.vbforums.com/forumdisplay.php?f=16 to be the right forum for your specific form of pseudocode...it's not really BASIC but it is made to look like BASIC :-)
Re: Explaining this Algorithm
Quote:
Originally Posted by Desert Eagle
Firstly, sorry if im posting this in the wrong place.
No problem, sometimes it is hard to be sure.
As this is not related to a particular programming language, I have moved the thread to our General Developer forum.
Re: Explaining this Algorithm
Quote:
Originally Posted by smUX
First thing I thought when Dee said that :-)
Bubblesort isn't a poor sorting method, it's just a simple one
Ah, it has a name. Bubblesort, eh? According to Wikipedia: (all emphasis mine)
Sorting Algorithms
Quote:
Bubble sort
Bubble sort is a straightforward and simplistic method of sorting data that is used in computer science education. [...] Although simple, this algorithm is highly inefficient and is rarely used except in education. A slightly better variant, cocktail sort, works by inverting the ordering criteria and the pass direction on alternating passes.
Bubble Sort
Quote:
Due to its simplicity, bubble sort is often used to introduce the concept of an algorithm, or a sorting algorithm, to introductory computer science students. However, some researchers such as Owen Astrachan have gone to great lengths to disparage bubble sort and its continued popularity in computer science education, recommending that it no longer even be taught.
The Jargon file, which famously calls bogosort "the archetypical perversely awful algorithm", also calls bubble sort "the generic bad algorithm". Donald Knuth, in his famous The Art of Computer Programming, concluded that "the bubble sort seems to have nothing to recommend it, except a catchy name and the fact that it leads to some interesting theoretical problems", some of which he discusses therein.
I stand by my characterization of bubblesort as "very poor".
Re: Explaining this Algorithm
Quote:
Originally Posted by Ellis Dee
I stand by my characterization of bubblesort as "very poor".
LOL @ carefully chosen 4-letter word "very". The one that come to mind to me starts with "p".
It is a disgrace to the teaching profession that it is presented. This simple sort is easier to code for arrays having less than 10,000 elements:
Code:
for i=1 to n-1
for j=i+1 to n: if a(i)<a(j) then swap a(i), a(j): next j
next i
And for larger ones, more completed sorts are indicated, not the stupid bubble sort which only has the benefit that if the file is almost already sorted it works fast. But extracting the out-of-order records from such a file and sorting them separately and merging is even better.
Whenever I hear some poor student say "bubble sort" I know he/she is cursed with an incompetent teacher.
IMHO
Mac
Re: Explaining this Algorithm
Unfortunately, its the poor sorting algorithms which you can easily incorporate into written exams, and since they have the narrow minded "its just the grade that matters" POV they all suffer... good thing we are past that phase in our careers hahahaha.
