alice-teacher (no subject)

Thu May 19 16:19:24 EDT 2011

Eric,
Thank you for sending me your project. It looks like you are trying to implement a bubble sort. 

First of all you are complicating your life by trying to do this using the Alice list structure, when it probably would have been a better choice to use the Alice array structure. 

See the attached screen shot on how to create an array instead of a list in Alice.

The list structure is very good for maintaining a set of elements in which you may add, remove, or insert values, and it does a lot of the underlying operations for you, but it is not a very good choice for moving the elements into different positions within the list. You tried to work around this by creating the temporary list, and in fact, in doing this, you ended up trying to create a version of the selection sort.

Let me put into pseudocode what your code is doing.

1) first of all assume that the list "listNums" to be sorted contains the values {40, 30, 20, 10} and "tempList" is empty {}

2) using a loop you are going to look at every number in "listNums"

3) if the second value in listnums < first value (30 < 40) in listNums
	insert the second value into tempList
	remove second value from listNums
    or else
        insert the first value into tempList
        remove firstvalue from listNums

But here is the problem. You will insert either 30 into the templist, but it does not actually belong in the first position in this new list. You will also remove it from the listNums, so that listNums is now {40, 20, 10} and tempList is {30}. Also as the loop continues, you will now be comparing 40 and 20, so that 20 will be added to tempList, and removed from listNums, so that listNums is now {40, 10} and tempList is {30, 20}. You will then compare 40 and 10, adding it to the tempList {30, 20, 10} removing it from listNums {40}, and then 40 will be added to templist, so fianlly listNums is now {} and tempList is {30, 20, 10, 40}

You have successfully put 40 into its proper position, but you now need to loop through three more times to get 30, 20, and 10 into position. But the list structure really complicates this, and makes my head hurt trying to think about your next steps.

BTW, setting listNums so that it now refers to templist actually is working.

4) You check  the list, and if it is not sorted, you make one more pass through the list, but that will still not complete the task, and your code does in fact work on the revised templist {30, 20, 10, 40}

A better solution in this case, using the list would be to try a selection sort. The algorithm for this would be

	As long as listNums is not empty
		find the smallest element (which requires another loop)
		insert it at the end of tempList
		remove the current smallest
		cycle back to find the next smallest

I have attached a revised version of your program in which I have implemented this selection sort algorithm.

Some comments:

1) I am using the while loop structure, as opposed to "loop" or "for all in order". As I said before, using the list structure does not allow us to directly move values from one position to another in the list. We are forced to use insertions and removals, which requires a lot of extra bookkeeping. You were right to create a new list to insert values in their proper order. You just did not do this enough times. (The Alice array structure does allow you to directly "swap" values in the array, as it provides cleaner access to the index for setting values.)

2) As I am emptying one array to fill the other with the values in appropriate order, using a "While listNums is not empty", works well. "For all in order" also works well.

3) I have comments in the selection sort method to explain what is going on. Please feel free to let me know if you have questions.

4) In your testNumbers method I have added (though currently disabled) three "For all in order" structures that prints out the current values of the lists so you can see the lists after you run the sort. Also, in the details panel underneath the object tree, if you click on the properties tab, you can watch the listNums and tempList property variables as values are added and removed as the program is running.

Please let me know if you have any other questions.

All the best,
Don Slater

-------------- next part --------------
A non-text attachment was scrubbed...
Name: CreateArrayInAlice.png
Type: image/png
Size: 39556 bytes
Desc: not available
Url : https://lists.andrew.cmu.edu/mailman/private/alice-teachers/attachments/20110519/f3b81515/attachment-0002.png 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: selectionSortV2.a2w
Type: application/octet-stream
Size: 587604 bytes
Desc: not available
Url : https://lists.andrew.cmu.edu/mailman/private/alice-teachers/attachments/20110519/f3b81515/attachment-0001.obj 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: DetailsView.png
Type: image/png
Size: 77632 bytes
Desc: not available
Url : https://lists.andrew.cmu.edu/mailman/private/alice-teachers/attachments/20110519/f3b81515/attachment-0003.png 
-------------- next part --------------

On May 19, 2011, at 12:36 PM, Eric Lozaw wrote:

> yeah I did...I'll try again.  Let me know if it's attached or not.  
> 
> 
> Eric  
> 
> ________________________________________
> From: Don Slater [dslater at andrew.cmu.edu]
> Sent: Thursday, May 19, 2011 12:32 PM
> To: Eric Lozaw
> Subject: Re: alice-teacher (no subject)
> 
> Eric,
> Have you sent me the code to look at? If so, I have missed it?
> 
> Don Slater
> 
> On May 19, 2011, at 12:20 PM, Eric Lozaw wrote:
> 
>> Original question
>> I currently have this problem with putting a list of numbers into order.  Since you can't see the code I'm writing I'll try to explain as clear as possible.  In my program I take in a list of numbers with one method and I do one pass through and get it sorted correctly with another method. As it's being sorted the numbers are taken out of the original list and put into a temporary list. I follow the numbers and it is doing it correctly at this point. After the first pass I then set the original list to equal the temporary list and try to pass through the sort method again.  This is where it gets wierd.  On the second pass the sorting algorithm is trying to use the temporary list and not the list that is called upon in my method.
>> 
>> Response:
>> Not having a great deal of experience, but I had a similar problem once upon
>> a time in my college programming days. I think you need to either clear or
>> delete the temporary list, before doing the pass again.
>> 
>> Reply
>> I tried clearing the list...and it tried to sort a null set.
>> 
>> _______________________________________________
>> alice-teachers mailing list
>> alice-teachers at lists.andrew.cmu.edu
>> https://lists.andrew.cmu.edu/mailman/listinfo/alice-teachers
> <bubbleSort.a2w>