5.4.4 Data Representation, Data Structures and Data Manipulation
OCR Computing AS and A Level Discussion Board: 2509 - Systems Software, Architecture, Databases and Paradigms: 5.4.4 Data Representation, Data Structures and Data Manipulation
Please help me with this part of the syllabus.
"Explain the difference between the sort/merge methods insertion, quick sort, and merging, highlighting the characteristics, advantages and disadvantages of each;"
While I think I understand insertion and merging, and a bit of quick sort, i do not understand the "highlighting the characteristics, advantages and disadvantages of each;" part of it since there seems to be no text materials devoted to it.
This part therefore seems to be poorly covered in the textbooks. I would appreciate if someone would help me with this.
Thanking in advance
BG
The best guide to this area of the syllabus is the Bradley text book (chapter 19 in the 4th edition).
"highlighting the characteristics" means explain how they work. The easiest way to do this is a simple worked example.
The insert sort algorithm is relatively easy to program and debug, but relatively slow for large data sets.
The quick sort algorithm makes use of recursion, so is more complex to program and debug. However it is a lot faster than the insert sort, so is a good choice for large data sets.
Does this help?
Thank you very much.
It does help, however I still do not understand what are the advantages and disadvantage of merging compared to insert and quick sort.
Another area I am concerned about is will they ask us to write alogrithms for it in any language or just in simple pesudocode?
I do understand most of them, but some of them are extremely hard to understand, for example, the insertion sort for tree structures. I have Dave's Cooper book, First edition, which is excellent, however it does not explain what are the current nodes, and how can it go " till null" in tree structures. I am sure that the second edition of his book would have improved this area a bit, but I do not have the money to buy all the newest books! Could you please clarify to me what are current node, and how can it repeat till null in the "insertion sort for tree structures" as well. I would be most grateful for your help.
Thank you again
BG
I'm not sure you can talk about advantages and disadvantages between merging and sorting, because they're different things!
Exam questions will never ask for algorithms in a language. Pseudocode is fine.
Perhaps Dave will answer your other question ...
If you say that they are different things, how can the syllabus put them all on one line!
Anyway, we'll wait for D Cooper to answer my other question....
Thanks a lot anyway.
BG
You're right! There is a much clearer example, step-by-step with diagrams, in the second edition!
Start by looking at this excellent site (not mine!!) here (but only at the beginning bit on constructing a binary tree, not the traversing a tree section - it's not part of the syllabus (probably)):
http://www.theteacher99.btinternet.co.uk/theteacher/newalevel/index4_5_3.htm
In the insertion algorithm, the current node is a variable that holds a data item in a tree. You need to look at the current node because you have to decide whether to branch left or right underneath it, when deciding where to put a new data item.
1) Imagine you have a data item X to insert into a binary tree structure.
2) You have to write an algorithm.
3) The current node must initially be set to the root node i.e. the top of the tree.
4) You must decide whether to branch left or right underneath this current node.
5) Let's say you do a test, comparing the data you want to insert with the current node.
6) You decide to branch left, You branch left and find there is another node (piece of data) already in that position. That piece of data then becimes the current node.
7) You do another test, to see if you should branch left or right again.
8) Let us suppose you have to branch left again.
9) This position then becomes the current node. This time, however, imagine the the current node is null, i.e. there isn't any data in that position.
10) That's where you insert your data item X.
That's the gist of it. You ought to rewrite the above so that you put the tests in a REPEAT loop until you find a null position. You should also think about what to do if you are trying to insert a data item into an empty tree and include that special case in the algorithm.
Perhaps you could ask your teacher to go through inserting and deleting data items in a tree structure on the whiteboard. It is fairly straightforward once you have worked through some examples.
Hope that helps and good luck. I'm off on my hols tomorrow!
DC
Thank you so much!
Enjoy your holidays tommorow!
As you know, I have the first edition of the book theteacher.info(Dave Cooper's) - I can't seem to find an algorithm for quick sort. I am sure, the second edition would have it. Could someone please be kind enough to write one out for me, or we don't really need to know the algorithm for it?
Thanks a lot again, and have a ncie weekend
Maybe, Dave Cooper will answer your question after he returns from his holiday (see previous comments on this conversation!)
i also need to know about this algorithim - i also have the first edition of the book.....and it does not say anything about quick sort algorithim!
Quicksort is not in the textbook. I've often wondered what kind of question you could reasonably be asked about this, since describing quicksort in English would be quite a time-consuming and difficult task. (I also think this about functional languages).
However, the links on page 162 of the first edition and page 157 of the second edition will lead you to everything you need to know. In addition, type in 'quicksort' in Google and you will get more links than you know what to do with. What you need to then do is be prepared to sit down for a morning and work through the examples you find. By the way, there is also a very good (ten page!!) example in Bradley, fourth edition, starting on page 408.
PS.
If you can summarise quicksort in a nice easily understood set of steps, with a nice example, in about a page, then let me know and I'll include it in the third edition next year. I have tried a number of times to teach this with different pupils and have failed miserably so took the view that including it in the book would just confuse rather than enlighten!
Do any teachers have any ideas / suggestions?
Good luck!
You have comforted my nerves!
At least we just have to know the basic of it, like in the bradley book, there is quite a good summary of quicksort at the back of that section (Page 422)
So, I guess if we learn it properly, then we should be OK....
Thanks again
BG
Hi!
Looking at the specimen paper, of this module - i.e. module 2509, if you look at the last question - the very last question, 9, it has 2 parts a + b. Q9(a), is easy to do, but Q9(b), is more difficult. I don't understand the question - it is reffering to insertion sort or was it referring to adding data to a linked list?
Thanking you in advance
Authentication ErrorYour username/password combination was invalid, or you do not have permission to post to this topic. You may revise your username and password using the form at the bottom of this page.
Authentication ErrorYour username/password combination was invalid, or you do not have permission to post to this topic. You may revise your username and password using the form at the bottom of this page.
Authentication ErrorYour username/password combination was invalid, or you do not have permission to post to this topic. You may revise your username and password using the form at the bottom of this page.
Authentication ErrorYour username/password combination was invalid, or you do not have permission to post to this topic. You may revise your username and password using the form at the bottom of this page.
Authentication ErrorYour username/password combination was invalid, or you do not have permission to post to this topic. You may revise your username and password using the form at the bottom of this page.
Authentication ErrorYour username/password combination was invalid, or you do not have permission to post to this topic. You may revise your username and password using the form at the bottom of this page.
Authentication ErrorYour username/password combination was invalid, or you do not have permission to post to this topic. You may revise your username and password using the form at the bottom of this page.
Authentication ErrorYour username/password combination was invalid, or you do not have permission to post to this topic. You may revise your username and password using the form at the bottom of this page.
|