Selection Sort (C)
We already know Java and C++. Why learn Python?
Using Python to Implement Algorithms
Tyler Moore
Python has far less overhead than Java/C++ for the programmer.
Python is closer to psuedo-code on the English-pseudocode-code
spectrum than Java or C/C++, but it actually executes!
CSE 3353, SMU, Dallas, TX
Lecture 2
Python is handy for data manipulation and transformation, and
anything ¡±quick and dirty.¡±
Python is very powerful, thanks to all those extension modules.
Some slides created by or adapted from Dr. Kevin Wayne. For more information see
2 / 33
Python Resources
Selection Sort (C)
1
Download from for all major platforms
2
I¡¯ve written an online tutorial:
Think Python by Allen Downey:
3
Videos from Khan academy:
science/computer-science-subject/computer-science
8
4
5
6
7
9
10
3 / 33
s e l e c t i o n s o r t ( int s [ ] , int n)
{
int i , j ;
i n t min ;
f o r ( i =0; i >> s p o r t s =[ ¡¯ f o o t b a l l ¡¯ , ¡¯ t e n n i s ¡¯ , ¡¯ i c e h o c k e y ¡¯ , ¡¯ l a c r o s s e ¡¯ ,
¡¯ f i e l d h o c k e y ¡¯ , ¡¯ b a s k e t b a l l ¡¯ , ¡¯ b a s e b a l l ¡¯ , ¡¯ swimming ¡¯ ]
Indices start at 0. You can get a range of values by including two
2 >>> i n o r o u t =[ ¡¯ o u t ¡¯ , ¡¯ b o t h ¡¯ , ¡¯ i n ¡¯ , ¡¯ o u t ¡¯ , ¡¯ o u t ¡¯ , ¡¯ i n ¡¯ , ¡¯ o u t ¡¯ , ¡¯ i n ¡¯ ]
numbers separated by a colon. If you use one number and a colon,
3 >>> l e n ( s p o r t s ) #b u i l t ?i n f u n c t i o n c om p u te s t h e l e n g t h o f l i s t s
will give you the rest of the list.
4 8
5 >>> s p o r t s l o c=z i p ( s p o r t s , i n o r o u t ) #b u i l t ?i n f u n c t i o n c o m b i n e s l i s t e l e m e n t ?w i s e
You can access the end of the list by using negative numbers
6 >>> s p o r t s l o c
7 [ ( ¡¯ f o o t b a l l ¡¯ , ¡¯ out ¡¯ ) , ( ¡¯ t e n n i s ¡¯ , ¡¯ both ¡¯ ) , ( ¡¯ i c e hockey ¡¯ , ¡¯ i n ¡¯ ) ,
1 >>> s p o r t s [ 2 ]
( ¡¯ l a c r o s s e ¡¯ , ¡¯ out ¡¯ ) , ( ¡¯ f i e l d hockey ¡¯ , ¡¯ out ¡¯ ) , ( ¡¯ b a s k e t b a l l ¡¯ , ¡¯ i n ¡¯ ) ,
2 ¡¯ i c e hockey ¡¯
( ¡¯ b a s e b a l l ¡¯ , ¡¯ o u t ¡¯ ) , ( ¡¯ swimming ¡¯ , ¡¯ i n ¡¯ ) ]
3 >>> s p o r t s [ 1 : 3 ]
8 >>> r a n d o m l i s t =[ ¡¯ f o o t b a l l ¡¯ , 3 , 6 . 7 , ¡¯ ham ¡¯ ] # l i s t e l e m e n t s don ¡¯ t h a v e t o be t h e same
4 [ ¡¯ t e tn y
np
i s e¡¯ , ¡¯ i c e h o c k e y ¡¯ ]
5
6
7
8
9
10
11
12
>>> s p o r t s [ 2 : ]
[ ¡¯ i c e h o c k e y ¡¯ , ¡¯ l a c r o s s e ¡¯ , ¡¯ f i e l d h o c k e y ¡¯ , ¡¯ b a s k e t b a l l ¡¯ , ¡¯ b a s e b a l l ¡¯ , ¡¯ swimming ¡¯ ]
>>> s p o r t s [ : 2 ]
[ ¡¯ football ¡¯ , ¡¯ tennis ¡¯ ]
>>> s p o r t s [ ?2]
¡¯ baseball ¡¯
>>> s p o r t s [ ? 2 : ]
[ ¡¯ b a s e b a l l ¡¯ , ¡¯ swimming ¡¯ ]
9 / 33
Modifying a list
it
10 / 33
Tuples and sets
>>> b a r = [ ¡¯ b ¡¯ , ¡¯ a ¡¯ , ¡¯ j ¡¯ , ¡¯ h ¡¯ , ¡¯ l ¡¯ ]
>>> b a r . append ( ¡¯ o ¡¯ )
>>> b a r
[ ¡¯b ¡¯ , ¡¯a ¡¯ , ¡¯ j ¡¯ , ¡¯h ¡¯ , ¡¯ l ¡¯ , ¡¯o ¡¯ ]
>>> b a r . pop ( )
¡¯o ¡¯
>>> b a r
[ ¡¯b ¡¯ , ¡¯a ¡¯ , ¡¯ j ¡¯ , ¡¯h ¡¯ , ¡¯ l ¡¯ ]
>>> b a r . e x t e n d ( [ ¡¯ y ¡¯ , ¡¯ x ¡¯ ] )
>>> b a r
[ ¡¯b ¡¯ , ¡¯a ¡¯ , ¡¯ j ¡¯ , ¡¯h ¡¯ , ¡¯ l ¡¯ , ¡¯y ¡¯ , ¡¯x ¡¯ ]
>>> b a r . i n s e r t ( ¡¯w ¡¯ , 3 )
T r a c e b a c k ( most r e c e n t c a l l l a s t ) :
F i l e ¡±¡± , l i n e 1 , i n
T y p e E r r o r : an i n t e g e r i s r e q u i r e d
>>> b a r . i n s e r t ( 3 , ¡¯w ¡¯ )
>>> b a r
[ ¡¯ b ¡¯ , ¡¯ a ¡¯ , ¡¯ j ¡¯ , ¡¯w ¡¯ , ¡¯ h ¡¯ , ¡¯ l ¡¯ , ¡¯ y ¡¯ , ¡¯ x ¡¯ ]
>>> b a r . s o r t ( )
>>> b a r
[ ¡¯ a ¡¯ , ¡¯ b ¡¯ , ¡¯ h ¡¯ , ¡¯ j ¡¯ , ¡¯ l ¡¯ , ¡¯w ¡¯ , ¡¯ x ¡¯ , ¡¯ y ¡¯ ]
>>> b a r [ : : ? 1 ]
[ ¡¯ y ¡¯ , ¡¯ x ¡¯ , ¡¯w ¡¯ , ¡¯ l ¡¯ , ¡¯ j ¡¯ , ¡¯ h ¡¯ , ¡¯ b ¡¯ , ¡¯ a ¡¯ ]
Tuples are immutable lists
Sets are unordered lists
>>> t = ( 4 , 6 , 2 , 3 )
>>> t [ 0 ] = 5
T r a c e b a c k ( most r e c e n t c a l l l a s t ) :
F i l e ¡±¡± , l i n e 1 , i n
T y p e E r r o r : ¡¯ t u p l e ¡¯ o b j e c t d o e s no t s u p p o r t i t e m a s s i g n m e n t
>>> s = { 3 , 9 , 6 , 2 }
>>> s [ 2 ]
T r a c e b a c k ( most r e c e n t c a l l l a s t ) :
F i l e ¡±¡± , l i n e 1 , i n
T y p e E r r o r : ¡¯ s e t ¡¯ o b j e c t d o e s no t s u p p o r t i n d e x i n g
>>> 6 i n s
True
>>> 7 i n s
False
11 / 33
12 / 33
Dictionaries
Dictionaries
Dictionaries map keys to values. Both the keys and values can be of any
type, from strings to numbers, to other dictionaries.
1 >>> from s a m p l e d a t a i m p o r t ?
2 >>> u n i
3 { ¡¯ J o n e s ¡¯ : ¡¯ O x f o r d ¡¯ , ¡¯ G i l l i a m ¡¯ : ¡¯ O c c i d e n t a l ¡¯ , ¡¯ C l e e s e ¡¯ : ¡¯ Cam b r id ge ¡¯ ,
¡¯ Chapman ¡¯ : ¡¯ Cambridge ¡¯ , ¡¯ I d l e ¡¯ : ¡¯ Cam br id ge ¡¯ , ¡¯ P a l i n ¡¯ : ¡¯ O x f o r d ¡¯ }
4 >>> u n i [ ¡¯ P a l i n ¡¯ ]
5 ¡¯ Oxford ¡¯
6 >>> u n i [ ¡¯ P a l i n ¡¯ ] = ¡¯ O x f o r d U n i v e r s i t y ¡¯
7 >>> u n i [ ¡¯ P a l i n ¡¯ ]
8 ¡¯ Oxford U n i v e r s i t y ¡¯
9 >>> u n i . k e y s ( )
10 [ ¡¯ J o n e s ¡¯ , ¡¯ G i l l i a m ¡¯ , ¡¯ C l e e s e ¡¯ , ¡¯ Chapman ¡¯ , ¡¯ I d l e ¡¯ , ¡¯ P a l i n ¡¯ ]
You can also start from an empty dictionary and then add values:
s p o r t 2 t y p e ={}
s p o r t 2 t y p e [ ¡¯ f o o t b a l l ¡¯ ]= ¡¯ o u t ¡¯
s p o r t 2 t y p e [ ¡¯ i c e h o c k e y ¡¯ ]= ¡¯ i n ¡¯
>>> s p o r t 2 t y p e
{ ¡¯ i c e hockey ¡¯ : ¡¯ i n ¡¯ , ¡¯ f o o t b a l l ¡¯ :
13 / 33
Python Tips
¡¯ out ¡¯ }
14 / 33
Python Tips
>>> f o o = [ ¡¯ c a t ¡¯ , ¡¯ dog ¡¯ , ¡¯ h a m s t e r ¡¯ , ¡¯ b u f f a l o ¡¯ , ¡¯ c h e e t a h ¡¯ ]
>>> d i r ( f o o )
#f i n d l i s t a t t r i b u t e s and methods
class
¡¯ , ¡¯ contains
¡¯, ¡¯
delattr
¡¯,
[ ¡¯ add ¡¯ , ¡¯
¡¯ delitem
¡¯, ¡¯
delslice
¡¯ , ¡¯ doc
¡¯ , ¡¯ eq
¡¯,
¡¯ , ¡¯ ge
¡¯ , ¡¯ getattribute
¡¯ , ¡¯ getitem
¡¯,
¡¯ format
¡¯
getslice
¡¯ , ¡¯ gt
¡¯ , ¡¯ hash
¡¯ , ¡¯ iadd
¡¯ , ¡¯ imul
¡¯,
init
¡¯, ¡¯
iter
¡¯, ¡¯
le
¡¯, ¡¯
len
¡¯, ¡¯
lt
¡¯,
¡¯
¡¯ , ¡¯ new ¡¯ , ¡¯ reduce
¡¯ , ¡¯ reduce ex
¡¯,
¡¯ mul ¡¯ , ¡¯ ne
¡¯ , ¡¯ reversed
¡¯ , ¡¯ rmul
¡¯, ¡¯
setattr
¡¯,
¡¯ repr
¡¯, ¡¯
setslice
¡¯, ¡¯
sizeof
¡¯, ¡¯
str
¡¯,
¡¯ setitem
¡¯ , ¡¯ append ¡¯ , ¡¯ c o u n t ¡¯ , ¡¯ e x t e n d ¡¯ , ¡¯ i n d e x ¡¯ ,
¡¯ subclasshook
¡¯ i n s e r t ¡¯ , ¡¯ pop ¡¯ , ¡¯ remove ¡¯ , ¡¯ r e v e r s e ¡¯ , ¡¯ s o r t ¡¯ ]
#c h e c k t h e d o c s t r i n g
>>> p r i n t f o o . pop . d o c
L . pop ( [ i n d e x ] ) ?> i t e m ?? remove and r e t u r n i t e m a t i n d e x ( d e f a u l t
R a i s e s I n d e x E r r o r i f l i s t i s empty o r i n d e x i s o u t o f r a n g e .
>>> f o o . pop ( )
¡¯ cheetah ¡¯
>>> f o o
[ ¡¯ c a t ¡¯ , ¡¯ dog ¡¯ , ¡¯ h a m s t e r ¡¯ , ¡¯ b u f f a l o ¡¯ ]
To see the methods available for a variable s, type dir (s) at the
interpreter
Python documentation (and Google) will help explain what each
method does:
You can also check the docstring for what methods do
15 / 33
last ).
16 / 33
Iteration in python
List comprehensions
The python for loop is very powerful, due to its natural integration with
iterators.
You can iterate lists:
Recall set-builder notation from Discrete Math:
1
2
3
4
5
6
7
8
9
10
>>> from s a m p l e d a t a i m p o r t ?
>>> f o r c h e e s e i n c h e e s e s :
...
p r i n t ¡¯%s i s t a s t y ¡¯ % ( c h e e s e )
...
swiss is tasty
gruyere i s tasty
cheddar i s t a s t y
stilton is tasty
roquefort is tasty
brie is tasty
S = {3x|x ¡Ê N, x > 5}
We can approximate that in Python
>>> r a n g e ( 1 , 1 1 )
[1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10]
>>> {3? x f o r x i n r a n g e ( 1 , 1 1 ) i f x >5}
s e t ( [ 2 4 , 18 , 27 , 21 , 3 0 ] )
>>> [ 3 ? x f o r x i n r a n g e ( 1 , 1 1 ) i f x >5]
[ 1 8 , 21 , 24 , 27 , 30]
You can iterate dictionaries:
1
2
3
4
5
6
7
8
9
>>> f o r name i n u n i :
...
p r i n t name , ¡± went t o ¡± , u n i [ name ]
...
J o n e s went t o O x f o r d
G i l l i a m went t o O c c i d e n t a l
C l e e s e went t o Cam b rid ge
Chapman went t o Ca mb r i dge
I d l e went t o Ca mbr i dge
P a l i n went t o O x f o r d U n i v e r s i t y
Comprehensions arise in very common coding scenarios
17 / 33
18 / 33
List comprehensions
List comprehensions
Here¡¯s a common coding task: iterate over some list, perform some action
on each element of that list, and store the results in a new list. Here¡¯s an
example:
But wait, there¡¯s more! Suppose you only want to add items to the list if
they meet a certain condition, say if the item begins with the letter s. Well
here¡¯s the long way:
>>> c h e e s e s = [
>>>
>>>
...
...
>>>
[5 ,
¡¯ s w i s s ¡¯ , ¡¯ gruyere ¡¯ , ¡¯ cheddar ¡¯ , ¡¯ s t i l t o n ¡¯ ,
¡¯ roquefort ¡¯ , ¡¯ brie ¡¯ ]
>>>
>>>
...
...
...
>>>
[5 ,
c h e e s e l e n =[]
for c in cheeses :
c h e e s e l e n . append ( l e n ( c ) )
cheeselen
7 , 7 , 7 , 9 , 4]
s c h e e s e l e n =[]
for c in cheeses :
i f c [0]== ¡¯ s ¡¯ :
s c h e e s e l e n . append ( l e n ( c ) )
scheeselen
7]
You can add a condition at the end of the list comprehension:
We can do this on a single line:
c h e e s e l e n =[ l e n ( c ) f o r c i n c h e e s e s
>>> s c h e e s e l e n
[5 , 7]
c h e e s e l e n =[ l e n ( c ) f o r c i n c h e e s e s ]
>>> c h e e s e l e n
[5 , 7 , 7 , 7 , 9 , 4]
19 / 33
i f c [0]== ¡± s ¡± ]
20 / 33
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
Related searches
- college selection worksheet
- how to add selection boxes in excel
- college selection criteria worksheet
- college selection criteria spreadsheet xls
- second reading selection with comprehension questions
- selection of appropriate statistical tests
- software selection template
- refund selection customer service
- excel multiple selection list box
- what is selection bias
- python selection from list
- random selection python