Introduction to Python Programming

Introduction to Python Programming

(7) Sorting Algorithms

S. Thater and A. Friedrich

Saarland University

Winter Semester 2011/2012

S. Thater and A. Friedrich ( Saarland University)

Introduction to Python Programming

Winter Semester 2011/2012 1 / 15

Sorting Algorithms

Agenda: Insertion Sort Selection Sort Bubblesort Mergesort Quicksort

Goals: Understand the above sorting algorithms. Get an idea that there are differences in efficiency. Get used to recursion. We won't talk about complexity theory in this lecture.

S. Thater and A. Friedrich ( Saarland University)

Introduction to Python Programming

Winter Semester 2011/2012 2 / 15

Swapping two items of a list

How can we swap two items of a list? 1 a = [5, 3]

2

3 Today, we always assume that our list is called a.

S. Thater and A. Friedrich ( Saarland University)

Introduction to Python Programming

Winter Semester 2011/2012 3 / 15

Selection Sort

Selection Sort Until list is empty:

Find the smallest element of the remaining list. Append it to a new list.

S. Thater and A. Friedrich ( Saarland University)

Introduction to Python Programming

Winter Semester 2011/2012 4 / 15

Selection Sort: Code

1 def selection_sort(a):

2

""" sorting algorithm, creates a NEW list """

3

b = []

4

# Why is the list a copied here?

5

a = a[:]

6

while len(a) > 0:

7

# Find minimum of the list

8

minimum = 0

9

for i in range(1, len(a)):

10

if a[i] < a[minimum]:

11

minimum = i

12

# Remove the minimum from the list

13

# and append it to the new list

14

b.append(a.pop(minimum))

15

return b

S. Thater and A. Friedrich ( Saarland University)

Introduction to Python Programming

Winter Semester 2011/2012 5 / 15

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download