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.

Google Online Preview   Download