[Tutor] bubble sort function
Dear group, I'm having a bit of trouble with understanding why my bubble sort implementation doesn't work. I've got the following function to perform a bubble sort operation on a list of numbers: def bubble_sort_ascending(unsorted): """ Sorts a list of numbers into ascending order """ iterations = 0 size = len(unsorted) - int(1) for i in range(0, size): unsorted[i] = float(unsorted[i]) while unsorted[i] > unsorted[i+1]: # Use a tuple assignment in order to swap the value of two variables unsorted[i], unsorted[i+1] = unsorted[i+1], unsorted[i] iterations += 1 sorted_vec = unsorted[:] # copy unsorted which is now sorted print "\nIterations completed: %s\n" %(iterations) return sorted_vec Example: mylist = [4, 1, 7, 19, 13, 22, 17, 14, 23, 21] When I call it as such bubble_sort_ascending(mylist), it returns the list only partially sorted with 5 iterations reported, i.e. [1, 4.0, 7.0, 13, 19.0, 17, 14, 22.0, 21, 23.0] and I have to call it again for the the sorting operation to complete. Is there something I am missing in my code? Why does it not sort the entire list at once and just count all completed iterations? Any help appreciated. Many thanks, Spyros ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] bubble sort function
Spyros Charonis Wrote in message: > > Dear group, > I'm having a bit of trouble with understanding why my bubble sort > implementation doesn't work. I've got the following function to perform a > bubble sort operation on a list of numbers: > def bubble_sort_ascending(unsorted): > """ Sorts a list of numbers into ascending order """ >iterations = 0 >size = len(unsorted) - int(1) >for i in range(0, size): > unsorted[i] = float(unsorted[i]) Why are you converting some of your values to float? You should either convert them all before you start, or not bother at all. > while unsorted[i] > unsorted[i+1]: How do you think this while statement will ever run more than once? Think about what do yoy hope this loop will do and change it so that it will accomplish that. Hint, you'll need a second index variable. > # Use a tuple assignment in order to swap the value of two > variables > unsorted[i], unsorted[i+1] = unsorted[i+1], unsorted[i] > iterations += 1 > sorted_vec = unsorted[:] # copy unsorted which is now > sorted I can't see how this accomplishes anything. Certainly if you do want to copy the whole list, you should either do it before you start, or when you finish. > print "\nIterations completed: %s\n" %(iterations) >return sorted_vec Standard python practice is to either modify the original list, or to return a new list, modified from the original. You're trying to do both. > Example: mylist = [4, 1, 7, 19, 13, 22, 17, 14, 23, 21] > > When I call it as such bubble_sort_ascending(mylist), it returns the list > only partially sorted with 5 iterations reported, i.e. > [1, 4.0, 7.0, 13, 19.0, 17, 14, 22.0, 21, 23.0] > and I have to call it again You're likely it needed only two passes. It could have taken about 9. > for the the sorting operation to complete. Is there something I am missing in > my code? Why does it not sort the entire list A sort of this type needs at least two nested loops. You only have one. > at once and just count all completed iterations? You are not counting iterations, just exchanges. -- DaveA ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor
[Tutor] I apologize
I accidentally sent my last email from my work email. I recently added my gmail account to MS exchange and I forget I have to change where I send the mail from now that I have two accounts in exchange. Sorry for any confusion. ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] bubble sort function
On 15/11/14 16:46, Spyros Charonis wrote: def bubble_sort_ascending(unsorted): iterations = 0 size = len(unsorted) - int(1) Don't convert 1 to an int - it already is. for i in range(0, size): This will result in 'i' going from zero to len()-2. Is that what you want? unsorted[i] = float(unsorted[i]) Comparing ints to floats or even comparing two floats is notoriously error prone due to the imprecision of floating point representation. You probably don't want to do the conversion. And if you must do it, why do you only do it once, outside the while loop? while unsorted[i] > unsorted[i+1]: unsorted[i], unsorted[i+1] = unsorted[i+1], unsorted[i] iterations += 1 I assume you intended to end the loop body here? But the following lines are indented so are included in the loop. Also because you never change 'i' the loop can only ever run once. So really you could use a an if statement instead of the while loop? Finally, iterations is really counting swaps. Is that what you want it to count or os it actually loop iterations? If so which? The for loop or the while loop or the sum of both? sorted_vec = unsorted[:] print "\nIterations completed: %s\n" %(iterations) return sorted_vec Since you never alter sorted_vec there is no point in creating it. Just return unsorted - which is now sorted... and I have to call it again for the the sorting operation to complete. Is there something I am missing in my code? Why does it not sort the entire list at once and just count all completed iterations? There are several things missing or broken, the few I've pointed out above will help but the algorithm seems suspect to me. You need to revisit the core algorithm I suspect. BTW I assume this is just a learning exercise since the default sorting algorithm will virtually always be better than bubble sort for any real work! -- Alan G Author of the Learn to Program web site http://www.alan-g.me.uk/ http://www.flickr.com/photos/alangauldphotos ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] bubble sort function
Thank you Alan, When I initiated the loop with the condition: for i in range(len(unsorted)): Python raised an IndexError saying I had gone out of bounds. Hence the change to: for i in range(0, size) Yes, I actually the loop only consists of: while unsorted[i] > unsorted[i+1]: # Use a tuple assignment in order to swap the value of two variables unsorted[i], unsorted[i+1] = unsorted[i+1], unsorted[i] iterations += 1 Sorry about that. the *iterations* update and sorted_vec assignment are outside of the loop body. This is indeed just a learning exercise, I am aware that lists have sort() and reverse() methods. I'm in the process of learning a bit about data structures & algorithms using Python as my implementation language. On Sat, Nov 15, 2014 at 7:02 PM, Alan Gauld wrote: > On 15/11/14 16:46, Spyros Charonis wrote: > > def bubble_sort_ascending(unsorted): >> iterations = 0 >> size = len(unsorted) - int(1) >> > > Don't convert 1 to an int - it already is. > > for i in range(0, size): >> > > This will result in 'i' going from zero to len()-2. > Is that what you want? > > unsorted[i] = float(unsorted[i]) >> > > Comparing ints to floats or even comparing two floats > is notoriously error prone due to the imprecision of > floating point representation. You probably don't want > to do the conversion. > > And if you must do it, why do you only do it once, > outside the while loop? > > while unsorted[i] > unsorted[i+1]: >>unsorted[i], unsorted[i+1] = unsorted[i+1], unsorted[i] >>iterations += 1 >> > > I assume you intended to end the loop body here? > But the following lines are indented so are included > in the loop. > > Also because you never change 'i' the loop can only > ever run once. So really you could use a an if > statement instead of the while loop? > > Finally, iterations is really counting swaps. Is that what you want it to > count or os it actually loop iterations? If so which? The for loop or the > while loop or the sum of both? > > sorted_vec = unsorted[:] >>print "\nIterations completed: %s\n" %(iterations) >> return sorted_vec >> > > Since you never alter sorted_vec there is no point in creating it. > Just return unsorted - which is now sorted... > > > and I have to call it again for the the sorting operation to complete. >> Is there something I am missing in my code? Why does it not sort the >> entire list at once and just count all completed iterations? >> > > There are several things missing or broken, the few I've pointed > out above will help but the algorithm seems suspect to me. You need > to revisit the core algorithm I suspect. > > BTW I assume this is just a learning exercise since the default > sorting algorithm will virtually always be better than bubble > sort for any real work! > > -- > Alan G > Author of the Learn to Program web site > http://www.alan-g.me.uk/ > http://www.flickr.com/photos/alangauldphotos > > > ___ > Tutor maillist - Tutor@python.org > To unsubscribe or change subscription options: > https://mail.python.org/mailman/listinfo/tutor > ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] Help understanding classes
Thank you Alan and Danny. It amazes me at the lengths you guys, as well as everyone else who contributes, will go to to help explain things to us; it is greatly appreciated! Alan, I decided to dumb down the learning classes just a little. By this I mean, I am not using Tkinter to learn classes. I am using one of the examples from your website, which I did change it just a little. I figured, I am having a hard time wrapping my head around classes and Tkinter would just add to the confusion. So, I have the below code. When I run this from terminal, it obviously prints "This is a test." If I may, break the code down and ask questions as it pertains to the code? # class Message: def __init__(self, aString): self.text = aString def printIt(self): print self.text m = Message("This is a test") m.printIt() ## With the first part... class Message: def __init__(self, aString): self.text = aString Will I always use "_init_" when defining the first function in a class? I noticed on your website, you created a class where you did not use "_init_" (see below). Was this because you did not define a function? class BalanceError(Exception): value = "Sorry you only have $%6.2f in your account" I noticed that I can change "text" to anything and I still get the same results by running the code; I changed them to "blah" just as a test. When I define a function in a class, will I always use "self" as the first entry in the parenthesis? On the next part... m = Message("This is a test") m.printIt() I noticed I cannot run "printIt()" unless I make it an object i.e. "m = Message("This is a test")...?" I noticed I could change "m = Message("This is a test")" to "m = Message(raw_input())," which works. What if I wanted to create a function in Message that receives text from another function and then prints that text instead of the text from "m = Message("This is a test")...; can I pass or return values to another function inside a class? The"self" is really throwing me off, when I think about creating different functions that do misc things just to practice. For example, I have a function that kills a Linux program. I just don't see how to rethink that function to where it could be defined in a class? def kill_proc(process1): i = psutil.Popen(["ps", "cax"], stdout=PIPE) for proc in psutil.process_iter(): if proc.name(process1): proc.kill() Would it be something like...? class processKiller: def _init_(self): def kill_proc(self, process1): i = psutil.Popen(["ps", "cax"], stdout=PIPE) for proc in psutil.process_iter(): if proc.name(process1): proc.kill() Then outside of the class, call it like so...? p = processKiller() p.proc.kill() Again, I am just practicing, trying to wrap my head around classes and understand how to create and use them. Oh yeah, Alan I preordered your new book maybe a month or so ago. Any word on when it will be released and shipped? Again, thanks. ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] Help understanding classes
On 15/11/14 18:19, Bo Morris wrote: With the first part… class Message: def __init__(self, aString): self.text = aString Will I always use “_init_” when defining the first function in a class? It can go anywhere in the class definition. it is just another method of the class. But because it is where the initialization of the class data happens, it is logical and conventional to have it first. But there is no rule about it. I noticed on your website, you created a class where you did not use “_init_” (see below). Was this because you did not define a function? class BalanceError(Exception): value = "Sorry you only have $%6.2f in your account” Any class where you do not need to initialize any data can do without an __init__(). In this case it's just a subclass of the built in exception class - a new bespoke error type - so has no need of an init() I noticed that I can change “text” to anything and I still get the same results by running the code; I changed them to “blah” just as a test. text is just a name. Its a variable inside the class. In this case its where the message text is stored. Remember, classes are trying to model real concepts. a message has text so it has to be stored somewhere and an attribute called text is as good as anything. When I define a function in a class, will I always use “self” as the first entry in the parenthesis? Its a convention that is best observed. Pythoin doesn't actually care, you can use any name. The first parameter will allways refer to the instance calling the method. Other names sometimes seen are 'this' and 'object' but in Python self is the convention. m = Message("This is a test") m.printIt() I noticed I cannot run “printIt()” unless I make it an object i.e. “m = Message("This is a test”)…?” Because printIt() is a method of the class. You must have an instance to call a method. That's what makes it a method rather than an ordinary function. I noticed I could change "m = Message("This is a test”)” to "m = Message(raw_input()),” which works. Because the init expects a string. it doesn't matter how you create the string, it canbe a literal, a variable or using raw_ijnput. So long sas the result is a string it will work(Actually because of pythons flexible approach to types it can be other things too... m = Message(42) m.printit() will print 42. But thats because the print will convert it to a string for you. What if I wanted to create a function in Message that receives text from another function and then prints that text instead of the text from “m = Message("This is a test”)…; can I pass or return values to another function inside a class? Of course, methods are just functions, they can have any kind of parameter that an ordinary function can have. methods can call other methods (using the self. prefix) and methods can be called by external functions provided that function has an object of the right type to call it on. The”self” is really throwing me off, when I think about creating different functions that do misc things just to practice. methods shouldn't do miscellaneous things. Thats what modules andv functions are for(sort of). Methods should define the behaviour of an object type. Try to think of an object and what you can do with that object. Write methods that do those things. For example, I have a function that kills a Linux program. I just don’t see how to rethink that function to where it could be defined in a class? You could have a program class. It starts, it stops, it ends. It may produce output. In fact we already have a class that does this, its the Popen class in the subprocess module. You can learn a lot about OOOP by looking at the classes defined in the standard library and seeing what methods (and attributes) they define. def kill_proc(process1): i = psutil.Popen(["ps", "cax"], stdout=PIPE) for proc in psutil.process_iter(): if proc.name(process1): proc.kill() Would it be something like…? class processKiller: class names should be nouns. Everytime you have a verb name it probably means you are just writing a function. The classic case is a xxxManager class, that's usually wrong. So you want class Process: def _init_(self): You might want a command string in the init. That would let you start the process before you can kill it. You might want to store the PID in the process object self.pid = def kill_proc(self, process1): self will be process1 so you don't need to pass it as a parameter. i = psutil.Popen(["ps", "cax"], stdout=PIPE) You shouldn't need this if you start the process in init() since you can get the pid at that stage. for proc in psutil.process_iter(): if proc.name(process1): proc.kill() Then outside of the class, call it like so…? p = processKiller() p.proc.kill() So I'd suggest p = Process('top') p.kill() Oh yeah
Re: [Tutor] I apologize
Below was the post that was sent from the wrong email. Not sure if the first post went through, so in the event it did not, I will post again; if it was posted twice, I apologize for the redundancy. Subject: Re: Help understanding classes Thank you Alan and Danny. It amazes me at the lengths you guys, as well as everyone else who contributes, will go to to help explain things to us; it is greatly appreciated! Alan, I decided to dumb down the learning classes just a little. By this I mean, I am not using Tkinter to learn classes. I am using one of the examples from your website, which I did change it just a little. I figured, I am having a hard time wrapping my head around classes and Tkinter would just add to the confusion. So, I have the below code. When I run this from terminal, it obviously prints “This is a test.” If I may, break the code down and ask questions as it pertains to the code? # class Message: def __init__(self, aString): self.text = aString def printIt(self): print self.text m = Message("This is a test") m.printIt() ## With the first part… class Message: def __init__(self, aString): self.text = aString Will I always use “_init_” when defining the first function in a class? I noticed on your website, you created a class where you did not use “_init_” (see below). Was this because you did not define a function? class BalanceError(Exception): value = "Sorry you only have $%6.2f in your account” I noticed that I can change “text” to anything and I still get the same results by running the code; I changed them to “blah” just as a test. When I define a function in a class, will I always use “self” as the first entry in the parenthesis? On the next part… m = Message("This is a test") m.printIt() I noticed I cannot run “printIt()” unless I make it an object i.e. “m = Message("This is a test”)…?” I noticed I could change "m = Message("This is a test”)” to "m = Message(raw_input()),” which works. What if I wanted to create a function in Message that receives text from another function and then prints that text instead of the text from “m = Message("This is a test”)…; can I pass or return values to another function inside a class? The”self” is really throwing me off, when I think about creating different functions that do misc things just to practice. For example, I have a function that kills a Linux program. I just don’t see how to rethink that function to where it could be defined in a class? def kill_proc(process1): i = psutil.Popen(["ps", "cax"], stdout=PIPE) for proc in psutil.process_iter(): if proc.name(process1): proc.kill() Would it be something like…? class processKiller: def _init_(self): def kill_proc(self, process1): i = psutil.Popen(["ps", "cax"], stdout=PIPE) for proc in psutil.process_iter(): if proc.name(process1): proc.kill() Then outside of the class, call it like so…? p = processKiller() p.proc.kill() Again, I am just practicing, trying to wrap my head around classes and understand how to create and use them. Oh yeah, Alan I preordered your new book maybe a month or so ago. Any word on when it will be released and shipped? Again, thanks. Bo ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] bubble sort function
On Sat, Nov 15, 2014 at 04:46:26PM +, Spyros Charonis wrote: > Dear group, > > > I'm having a bit of trouble with understanding why my bubble sort > implementation doesn't work. I've got the following function to perform a > bubble sort operation on a list of numbers: It doesn't work because it is completely wrong. Sorry to be harsh, but sometimes it is easier to throw broken code away and start again than it is to try to diagnose the problems with it. Let's start with the unoptimized version of bubblesort given by Wikipedia: https://en.wikipedia.org/wiki/Bubble_sort#Implementation procedure bubbleSort( A : list of sortable items ) n = length(A) repeat swapped = false for i = 1 to n-1 inclusive do /* if this pair is out of order */ if A[i-1] > A[i] then /* swap them and remember something changed */ swap( A[i-1], A[i] ) swapped = true end if end for until not swapped end procedure Let's translate that to Python: def bubbleSort(alist): n = len(alist) swapped = True while swapped: swapped = False for i in range (1, n-1): # if this pair is out of order if alist[i-1] > alist[i]: # swap them and remember something changed alist[i-1], alist[i] = alist[i], alist[i-1] swapped = True Let's add something to print the partially sorted list each time we go through the loop: def bubbleSort(alist): print("Unsorted: %r" % alist) n = len(alist) swapped = True count = swaps = 0 while swapped: count += 1 swapped = False for i in range (1, n): # if this pair is out of order if alist[i-1] > alist[i]: # swap them and remember something changed swaps += 1 alist[i-1], alist[i] = alist[i], alist[i-1] swapped = True print("Iteration %d, %d swaps; list: %r" % (count, swaps, alist)) And now let's try it: py> mylist = [2, 4, 6, 8, 1, 3, 5, 7, 9, 0] py> bubbleSort(mylist) Unsorted: [2, 4, 6, 8, 1, 3, 5, 7, 9, 0] Iteration 1, 5 swaps; list: [2, 4, 6, 1, 3, 5, 7, 8, 0, 9] Iteration 2, 9 swaps; list: [2, 4, 1, 3, 5, 6, 7, 0, 8, 9] Iteration 3, 12 swaps; list: [2, 1, 3, 4, 5, 6, 0, 7, 8, 9] Iteration 4, 14 swaps; list: [1, 2, 3, 4, 5, 0, 6, 7, 8, 9] Iteration 5, 15 swaps; list: [1, 2, 3, 4, 0, 5, 6, 7, 8, 9] Iteration 6, 16 swaps; list: [1, 2, 3, 0, 4, 5, 6, 7, 8, 9] Iteration 7, 17 swaps; list: [1, 2, 0, 3, 4, 5, 6, 7, 8, 9] Iteration 8, 18 swaps; list: [1, 0, 2, 3, 4, 5, 6, 7, 8, 9] Iteration 9, 19 swaps; list: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] Iteration 10, 19 swaps; list: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] Now you can inspect the working code and compare it to the non-working code below and see what is different: > def bubble_sort_ascending(unsorted): > """ Sorts a list of numbers into ascending order """ >iterations = 0 > size = len(unsorted) - int(1) >for i in range(0, size): > unsorted[i] = float(unsorted[i]) > while unsorted[i] > unsorted[i+1]: > # Use a tuple assignment in order to swap the value of > two variables > unsorted[i], unsorted[i+1] = unsorted[i+1], unsorted[i] > iterations += 1 > sorted_vec = unsorted[:] # copy unsorted which is now > sorted > print "\nIterations completed: %s\n" %(iterations) >return sorted_vec -- Steven ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] Help understanding classes
On Sat, Nov 15, 2014 at 06:19:56PM +, Bo Morris wrote: > Thank you Alan and Danny. It amazes me at the lengths you guys, as well as > everyone else who contributes, will go to to help explain things to us; it > is greatly appreciated! > > Alan, I decided to dumb down the learning classes just a little. By > this I mean, I am not using Tkinter to learn classes. I am using one > of the examples from your website, which I did change it just a > little. I figured, I am having a hard time wrapping my head around > classes and Tkinter would just add to the confusion. Good plan! Before I get to your example, let's dumb things down even more. What is the *simplest possible* class we can create? class MyClass(object): pass That's pretty simple. (Actually, we can make it even shorter by removing the word "object", but that makes it more complicated because it will work differently in Python 2 and 3, so let's not do that.) What do those two lines of code do? The header "class MyClass(object)" tells Python to define a new class called MyClass. The body is the line "pass", which is just a placeholder to tell Python that there's nothing else there. (Otherwise the compiler will complain.) MyClass inherits from "object". object is a special built-in name which Python already knows about. The "object" class defines some extremely basic behaviour, such as knowing how to print itself, and so our MyClass inherits that behaviour. Classes on their own usually aren't very interesting. There's not a lot of work you can do with them, normally you work with *instances*. The relationship between a class and its instances is similar to that between a kind of thing and a specific example of that thing. E.g.: class: Dog instances: Lassie, Rin-Tin-Tin, Snowy, Hooch, Ol' Yella class: President of the USA instances: Barrack Obama, George Bush Jr, George Washington class: Tool subclasses: Screwdriver, Spanner, Hammer, etc. instances: this red handled screwdriver, that 3" spanner etc. Instances get their behaviour from their class; their class get their behaviour either from code you program, or code they inherit from the superclasses. MyClass is a subclass of object, so object is a superclass of MyClass. I can create an instance of MyClass, and then print it: py> obj = MyClass() py> print(obj) <__main__.MyClass object at 0xb7b52f6c> How did `obj` know what to print when I never wrote any code to handle printing MyClass instances? It inherited that code from the superclass `object`, which already knows how to convert itself into a string, which print can then use: py> str(obj) '<__main__.MyClass object at 0xb7b52f6c>' So far, every MyClass instance is indistinguishable except by their "identity", their ID number which you can see written in hex in that string display or by calling id(): py> id(obj) 3082104684 py> hex(id(obj)) '0xb7b52f6c' [Aside: every single object in Python has an ID. It's usually going to be a cryptic multi-digit number, but some implementations will instead use an incrementing counter so that IDs will be 1, 2, 3, 4, ... ] We can associate some data with individual instances. That makes them distinguishable, and useful. What makes the ints 17 and 23 different is their *state*, that is the internal data (whatever that is!) which distinguishes the instance with value 17 from the instance with value 23. So far, our MyClass instances don't have any state, but we can give them some. Let's create a couple of instances of MyClass: py> a = MyClass() py> b = MyClass() py> a.colour = 'red' py> a.size = 23 py> b.colour = 'green' py> b.size = 42 py> if a.size >= b.size: ... print("the %s instance is bigger" % a.colour) ... else: ... print("the %s instance is bigger" % b.colour) ... the green instance is bigger The colour and size attributes count as examples of per-instance state. In a nutshell, that is what classes are all about: classes control the state of the instances, and define their behaviour. > So, I have the below code. When I run this from terminal, it obviously > prints "This is a test." If I may, break the code down and ask > questions as it pertains to the code? > > # > class Message: > def __init__(self, aString): > self.text = aString > > def printIt(self): > print self.text > > m = Message("This is a test") > m.printIt() > > ## > > With the first part... > class Message: > def __init__(self, aString): > self.text = aString > > Will I always use "_init_" when defining the first function in a > class? I noticed on your website, you created a class where you did > not use "_init_" (see below). Was this because you did not define a > function? Note that there are *two* underscores __init__ not one _init_. Such "dunder" (Double leading and trailing UNDERscore) methods normally have special meaning to Python, or are reserved for future use. __init__ is one such s