Assignment 03-meansort

Anyone already done the question on mean sort. Any tips on the partitioning part and how it differs. Pseudocode will be appreciated. Thanks.

Do we need to submit the partition and swap functions? From the question I understand that we should only submit the meansort function. Am I right or I have misunderstood? It seems that everyone has been able to do this question without any problem as no one seem to respond.

i think people are still tryin to figure out how to do the question, like I am doing at the moment. they do say that the prog has to run though u do not have to submit the whole algorithm. ie the swap() and partition func.

I've done the code, I'm having qualms handing in my mergesort, as can be read in the thread I started "Aprehensive bout Assignment3".

OK...

The truth is there's very little you have to do to actually answer Question7, the code you need is already done, you just need to read through the book and then understand it, then after that you can "edit" the code.

Note how the quicksort chooses a pivot using: (first/last)/2, well all you have to do is replace that with code that calculates the average, which is trivial, just add up all the elements and divide by n (the no. of elements)...

you use the same "partitionList()" function with one notable difference, the pivot element doesn't necessary exist within the array, which means there be no need to copy the pivot element to the first index (list[0]). The comparisons and iterations are all the same...

Thanks for your help. I'll implement the code today.

No, I tried your recommendation, it did not work. You cannot just replace the pivot with the mean because then your index and smallindex will remain the same and nothing will happen ito sort. I have really tried couple of things even trying to locate a value near to the mean and using that as a pivot, but to implement that takes so much processing time, why bother! Maybe I am overlooking something. Please help!!

Sorry I should have qualified my response.
If you implement the partition function as is, and you have a value bigger than your pivot(mean) then it will not be removed from that position and be ignored for the duration of the program. (Which were designed to ignore the first element.) I got it to sort small lists of up to ten elements, but as soon as I make the list bigger, it throws one or two elements out of sequence.

Hi guys

Please remember that with meansort that both the partition and the recquicksort functions will change. The change in recquicksort is very small.You will need to hand in both these functions.

regards
Lazarus Aron

I have already hand in assignment 03. In the tutorial letter it is not mentionned that we should submit the partition function. It simply says give an explanation how the partition is done. In my opinion it is not the same. Have I miss something. Any clarification will be much appreciated. What should I do now, will I lose marks for not submitting the partition function. Thanks.

Hi

Mr Lazarus Aron thanks for the help with the mean sort. I sorted it out with your help. Just a question. When duplicates appear in the list, I get an access violation and the program terminates abnormally. Ok I fixed the problem, by adding code to the recMeanSort function as you suggested, but I do not understand what is the cause of the problem. I found during debug that this error occurred every time that first and last positions in the list had the same value i.e the duplicates. Can you please explain?

Sakkie

Sakkie,

Malik did show in a previous chapter how to prevent duplicates from being added to the list and its on the UNISA CD that came with ur books in the src folder (if you dont have time to type it all out), its got all the code examples from the textbook in there. under chap9??? i think, is the arrayList code. in the .h file is code that prevents duplicates being use. try that.

Hi Sakkie

When you have a list(or sublist) of the same number(eg. 5 5 5) then your mean will be that particular number (eg. 5).During partitioning the smallIndex will end up pointing to the last number in the list. So pivotLocation will be the same as last and your list will never split.Recursion will thus continue indefinitely and your program will crash. If pivotLocation is equal to last then you do not have to do the recursive calls because this means that the list is made up of the same number ie. it is already sorted.

regards

Thanks for the explanation. I am starting to see light at the end of the tunnel. I have handed in my assignment through MyUnisa.

Regards
Sakkie

I finally got this assignment in - I really hope it will still be marked as I put a lot of work into it.
A little frustrating at times but it genereally went quite well. BigOh is pretty much a BigNo for me.