Assignment 2 Q2 & Q3

Hi All,
Should we use diagrams to show the solutions or the codings?

I've used a table for the one I've answered so far.

It just seems to me more a "track this" kind of problem than a "solve it". ("Solving" in this case involves regurgitation, whereas tracking can give some hands on appreciation of why a fuss is made about the algorithms.)

If I'm wrong, I hope I find that out soon.

Question 2 - I first added a description and stepped through the algorithm. I also added my source code and output. I think it is better to add as much as you can, especially if you are in doubt.

My output look as follows:

Language: C++
*******************************************
Binary search algorithm for all types
*******************************************
 
5 6 8 12 15 21 25 31
=========================
Searcing for the integer 27
=========================
Element not found!
=========================
Searcing for the integer 15
=========================
The element was found at position 5 in the array.
 
Process returned 0 (0x0)   execution time : 0.044 s
Press any key to continue.

Question 3 - What I did wat write the code and inserted cout statements throughout to display the changes in the array. I think the trick lies in identifying where to put the cout statements so as to show how the array changes. I am not sure whether this is correct, but it does show how the array changes.

My final output looks something like this.

Language: C++
********************************************
Sort algorithms sorting an array of integers
********************************************
===============
Insertion sort.
===============
Unsorted array - 18 15 11 4 2 9 10 5 3 12 6 7
 
18 15 11 4 2 9 10 5 3 12 6 7
Shuffle 15 into place : 15 18 11 4 2 9 10 5 3 12 6 7
15 18 11 4 2 9 10 5 3 12 6 7
15 18 18 4 2 9 10 5 3 12 6 7
Shuffle 11 into place : 11 15 18 4 2 9 10 5 3 12 6 7
11 15 18 4 2 9 10 5 3 12 6 7
11 15 18 18 2 9 10 5 3 12 6 7
11 15 15 18 2 9 10 5 3 12 6 7
Shuffle 4 into place : 4 11 15 18 2 9 10 5 3 12 6 7
4 11 15 18 2 9 10 5 3 12 6 7
4 11 15 18 18 9 10 5 3 12 6 7
4 11 15 15 18 9 10 5 3 12 6 7
4 11 11 15 18 9 10 5 3 12 6 7
Shuffle 2 into place : 2 4 11 15 18 9 10 5 3 12 6 7
2 4 11 15 18 9 10 5 3 12 6 7
2 4 11 15 18 18 10 5 3 12 6 7
2 4 11 15 15 18 10 5 3 12 6 7
Shuffle 9 into place : 2 4 9 11 15 18 10 5 3 12 6 7
2 4 9 11 15 18 10 5 3 12 6 7
2 4 9 11 15 18 18 5 3 12 6 7
2 4 9 11 15 15 18 5 3 12 6 7
Shuffle 10 into place : 2 4 9 10 11 15 18 5 3 12 6 7
2 4 9 10 11 15 18 5 3 12 6 7
2 4 9 10 11 15 18 18 3 12 6 7
2 4 9 10 11 15 15 18 3 12 6 7
2 4 9 10 11 11 15 18 3 12 6 7
2 4 9 10 10 11 15 18 3 12 6 7
Shuffle 5 into place : 2 4 5 9 10 11 15 18 3 12 6 7
2 4 5 9 10 11 15 18 3 12 6 7
2 4 5 9 10 11 15 18 18 12 6 7
2 4 5 9 10 11 15 15 18 12 6 7
2 4 5 9 10 11 11 15 18 12 6 7
2 4 5 9 10 10 11 15 18 12 6 7
2 4 5 9 9 10 11 15 18 12 6 7
2 4 5 5 9 10 11 15 18 12 6 7
Shuffle 3 into place : 2 3 4 5 9 10 11 15 18 12 6 7
2 3 4 5 9 10 11 15 18 12 6 7
2 3 4 5 9 10 11 15 18 18 6 7
Shuffle 12 into place : 2 3 4 5 9 10 11 12 15 18 6 7
2 3 4 5 9 10 11 12 15 18 6 7
2 3 4 5 9 10 11 12 15 18 18 7
2 3 4 5 9 10 11 12 15 15 18 7
2 3 4 5 9 10 11 12 12 15 18 7
2 3 4 5 9 10 11 11 12 15 18 7
2 3 4 5 9 10 10 11 12 15 18 7
Shuffle 6 into place : 2 3 4 5 6 9 10 11 12 15 18 7
2 3 4 5 6 9 10 11 12 15 18 7
2 3 4 5 6 9 10 11 12 15 18 18
2 3 4 5 6 9 10 11 12 15 15 18
2 3 4 5 6 9 10 11 12 12 15 18
2 3 4 5 6 9 10 11 11 12 15 18
2 3 4 5 6 9 10 10 11 12 15 18
Shuffle 7 into place : 2 3 4 5 6 7 9 10 11 12 15 18
 
Sorted array(Insertion Sort) - 2 3 4 5 6 7 9 10 11 12 15 18
============================================================
 
===========
Quick sort.
===========
Unsorted array - 18 15 11 4 2 9 10 5 3 12 6 7
 
Move Pivot : 9 15 11 4 2 18 10 5 3 12 6 7
Swap 15 & 7: 9 7 11 4 2 18 10 5 3 12 6 15
Swap 11 & 6: 9 7 6 4 2 18 10 5 3 12 11 15
Swap 18 & 3: 9 7 6 4 2 3 10 5 18 12 11 15
Swap 10 & 5: 9 7 6 4 2 3 5 10 18 12 11 15
Move Pivot back : 5 7 6 4 2 3 9 10 18 12 11 15
Move Pivot : 6 7 5 4 2 3 9 10 18 12 11 15
Swap 7 & 3: 6 3 5 4 2 7 9 10 18 12 11 15
Move Pivot back : 2 3 5 4 6 7 9 10 18 12 11 15
Move Pivot : 3 2 5 4 6 7 9 10 18 12 11 15
Move Pivot back : 2 3 5 4 6 7 9 10 18 12 11 15
Move Pivot : 2 3 5 4 6 7 9 10 18 12 11 15
Move Pivot back : 2 3 4 5 6 7 9 10 18 12 11 15
Move Pivot : 2 3 4 5 6 7 9 12 18 10 11 15
Swap 18 & 11: 2 3 4 5 6 7 9 12 11 10 18 15
Move Pivot back : 2 3 4 5 6 7 9 10 11 12 18 15
Move Pivot : 2 3 4 5 6 7 9 10 11 12 18 15
Move Pivot : 2 3 4 5 6 7 9 10 11 12 18 15
Move Pivot back : 2 3 4 5 6 7 9 10 11 12 15 18
 
Sorted array(Quick Sort) - 2 3 4 5 6 7 9 10 11 12 15 18
============================================================
===========
Merge sort.
===========
Unsorted array - 18 15 11 4 2 9 10 5 3 12 6 7
 
18 15 11 4 2 9 10 5 3 12 6 7
15 18 11 4 2 9 10 5 3 12 6 7
11 15 18 4 2 9 10 5 3 12 6 7
11 15 18 2 4 9 10 5 3 12 6 7
11 15 18 2 4 9 10 5 3 12 6 7
2 4 9 11 15 18 10 5 3 12 6 7
2 4 9 11 15 18 5 10 3 12 6 7
2 4 9 11 15 18 3 5 10 12 6 7
2 4 9 11 15 18 3 5 10 6 12 7
2 4 9 11 15 18 3 5 10 6 7 12
2 4 9 11 15 18 3 5 6 7 10 12
 
Sorted array(Merge Sort) - 2 3 4 5 6 7 9 10 11 12 15 18
============================================================
 
 
Process returned 0 (0x0)   execution time : 0.167 s
Press any key to continue.

Chris Botha

=============================
Far and away the best prize that life has to offer is the chance to work hard at work worth doing.
Theodore Roosevelt

Dear Students

Please do not answer these questions (2 & 3) by running them on your machines. We want to see if you understand the algorithms and can go through them on without any computer assistance.

Kind Regards,
COS211X Lecturers

Oops

Yes, oops. The assignment questions are very ambiguous. Question 2 states that you should describe but Question 3 never mentions that. It just says sort ...

This being a programming class, I naturally assumed that meant coding.

Chris Botha

=============================
Far and away the best prize that life has to offer is the chance to work hard at work worth doing.
Theodore Roosevelt

Submission time. For Q2 and 3 it was said not to submit code (or code output), so I am wondering what format the answer should be in?

It stated that we should show the array whenever a change is made to it.

So I simply made an open office spreadsheet and showed the array whenever a change was made. Trust that's right because they clearly mentioned in this forum that they don't want us to code it

Spyre Wrote:
-------------------------------------------------------
> It stated that we should show the array whenever a
> change is made to it.
>
> So I simply made an open office spreadsheet and
> showed the array whenever a change was made. Trust
> that's right because they clearly mentioned in
> this forum that they don't want us to code it


me too! except i used my genuine pirate copy of office 2010.

hahahaha, and I'm sure you're far better off than me. This open office has frozen up on my numerous times and lost me hours of work I had to redo.

Well I'm only doing this tonight (had an unexpected illness, wife had a little baby, and I had another unexpected medical problem). Busy giving a break down in words describing how it works with a visual indication.

Its too my own benefit to able to describe it. I work in an office where not everybody has learnt about sorting and often have to explain to the other junior developers.

--------------------------------------------------------------
Don't Assume Everything is a Nail Just Because You Have a Really Big Hammer

Wow! You're cutting it fine! But then I suppose babies and medical problems don't really leave many other options.

I don't know whether I got it right, but the way I went about it (one move at a time, looking what goes where, and rearranging my array to show the new positions of each data element) required mainly just patience.

I must be weird or something, but I get a little kick out of seeing how they all move around and find their places (well according to what I imagine those to be, anyway).

So Steady on There Cap'n! As long as you just chug along, step for step, you'll see all the pretty patterns appearing, and then you'll be done.

(A tip -- assuming I'm right, of course -- you have to subdivide "subarrays of two" at some point. I got stuck by leaving the smaller arrays "unsorted". Mine's long gone, so I can't remember in more detail than that. (Besides which saying any more probably amounts to "sharing the answer" - for which one gets to share the mark).

@slow_eddy, last two months where hectic, time travel hectic. (Had a vasectomy, then the sick for 3 weeks, then a baby, and then last week my one testicle developed an infection - its still the size of a tennis ball and doc said I must rest)

--------------------------------------------------------------
Don't Assume Everything is a Nail Just Because You Have a Really Big Hammer

Cool, finished the assignment. Glad I did as I would only have fooled myself. I now eventually understand quick sort & merge sort.

Makes a big difference to visualise them.

--------------------------------------------------------------
Don't Assume Everything is a Nail Just Because You Have a Really Big Hammer

Oh dear, UNISA portal is 404 right now ... no problem, just upload in the morning

--------------------------------------------------------------
Don't Assume Everything is a Nail Just Because You Have a Really Big Hammer

Eina!

I would offer my sympathy, but normally when one's in that kind of pain one dreams of murdering all the people who offer sympathy, so I won't.

Yes, I reckon getting us to walk through it is probably the best way of explaining it. Probably we don't need a text book so much as an animation showing the process. If there finally really does come a point where books and multimedia truly converge, I reckon the books will be shorter, and a lot of the difficult stuff will become plainer. There are some things one just shouldn't describe/ explain using words.

Thanks slow_eddy, I've been asked in the office not to talk about it anymore - the guys are pop bang to get vasectomies now

But back to the module, agree with you. I failed last year and purposely did not do the supps as I want to understand the content. No use in just passing. I'm going to visualise all the other stuff and keep it to help our juniors out when we have show-'n-tell at work.

Advantage with our office policy is that we share knowledge. Only half the guys/girls in the office have studied and their is at times a knowledge void. We have a knowledge repo where we dump our readmes and scanned docs/images.

Also on Fridays we have geek fests and its great fun to stand around the white board and explain things to each other. We are also encouraged to play around with other languages so I'm going to learn how to do the merge & quicksort in erlang.

--------------------------------------------------------------
Don't Assume Everything is a Nail Just Because You Have a Really Big Hammer

At the moment I've got a policy of leaving all my fails behind me, and trying to push ahead with other things instead. However, if this one hammers me (which it could very well do), I'll have to do it again. Some of the stuff we do is core, and this course is one of those.

I'll be treating with due respect when the smoke clears, but right now I'm busy drowning in Numerical Methods (and to a lesser extent MAT261), so my most important course is on a bit of a back burner. When I'm done there, maybe I'll try to follow the example of the third year crew and attempt the self assessment assignment right here, on the "whiteboard". We'll see.

(This other course definitely gets to just lie there, dead, if I don't survive it. And if I even get 50 on the nose I'll dance on the bloody roof, drinking whiskey and swearing at the neighbours, all night long).

We use functional languages at work and lists is a very important part of it. Was chatting with our senior dev about it during lunch. While what we are learning is not gospel, he puts it nicely as its like the Bible, a good guide on how to do things well.

--------------------------------------------------------------
Don't Assume Everything is a Nail Just Because You Have a Really Big Hammer

Well that's good to hear. Yes, I think this course is a pretty much near to the foundations of it all, eh? With the higher level language, the theoretical side comes out cleaner and clearer than with machine language.

Memory lapse here. Procedural? That's basically Lisp, right? Or am I getting the terminology all mangled?

We use erlang which is a functional language. Boss is always joking about switching to Haskal

--------------------------------------------------------------
Don't Assume Everything is a Nail Just Because You Have a Really Big Hammer

Hmm. I've read about both of those - and more than just casual glance's worth, too. However, it's all gone in one ear and out the other - to the point where I mix them up with Lisp (which is a Functional language, right? -- everything in parentheses upon parentheses, just like function compositions in maths.)

So then Erlang would emphasize that point of difference between a "function" and a "procedure"? - or is this a case of an old word getting a new use?

Procedure: void MyFunction(...)

Function: type MyFunction(...) , [type != void]

?????

Ah.. you're talking Delphi there, right?

It's alarming how dimly that little bell rings for me...