Lab3003
  • FacultyAlgorithmChallenge
  • README
  • Question Bank
  • Python Documentation
    • BetterMap
    • Board
    • Card
    • Circle
    • Deck
    • README.md
    • Guide For Bookmarklet
    • Hand
    • HashMap
    • Hist
    • Kangaroo
    • LinearMap
    • Markov
    • Point
    • PokerDeck
    • PokerHand
    • Rectangle
    • State
    • Test
    • ThinkPython
    • ThinkPython2
    • Time
    • Think Python
    • thinkpython
  • Files
  • Image Files
  • lab
    • InsertSortTDD
    • countingBits
    • cs3003mergeSortLectureGuideLine
    • index_min
    • insort
    • One-line factorial function in Python
  • Manual for Python Lab
    • COURSE OBJECTIVES
    • 1_timelines
    • FDPNotes
    • PC-2_Python
    • lab1-kgashok.py
    • Lab 10 :Matrix Multiplication
    • Lab 11: Programs that take command line arguments (word count)
    • Lab 11: Programs that take command line arguments
    • Lab 12: Compute the most frequently used words from the text file
    • Lab 12: Find the most frequent words in a text read from a file
    • Lab 12a: File content sorter
    • Lab 2: Find the square root of a number (Newton’s method)
    • Lab 3: Compute power of a number (Exponentiation)
    • Lab 3: Exponentiation (power of a number)
    • lab4-binaraysearch-anvar.py
    • Solution for Binary Search
    • lab4-joelanandraj-binarysearch.py
    • Lab 4: Linear and Binary Search
    • lab4-lin-anvar.py
    • Linear Searcher
    • Lab 5 : find n prime numbers
    • lab6-kgashok.py
    • lab7-kgashok.py
    • lab8-kgashok.py
    • Lab 8: Selection and Insertion sort using Python
    • Merge Sort
    • Quick Sort
    • labSheet
    • pc0
    • sortPythonic
    • Sorting
  • misc
    • Bookmarklets
    • Guide For Bookmarklet
    • pythonResources
    • FDP for Python
    • Agenda for Workshop
      • Agenda
  • notes
    • Problem Set
    • InsertSortTDD
    • MergeSort
    • cs3003-unit1-notes
    • cs3003-unit3
    • cs3003-unit4-examples
    • Unit 4 Lists, Tuples and Dictionaries
    • cs3003insertsortLectureGuide
    • cs3003mergeSortLectureGuideLine
    • Designing and Delivering Effective Lectures
    • histogram.py
    • selectSortLectureGuide
  • Sandbox to try ThinkPy2 code
    • Code from ThinkPython Github repository
  • Important Topics
    • 3003-syllabus
    • GE8161 PROBLEM SOLVING AND PYTHON PROGRAMMING LABORATORY L T P C
    • Unit II Version 2
    • Unit IV material
    • UNIT III CONTROL FLOW, FUNCTIONS
    • Unit 1 Algorithm Problem Solving
    • Unit_V_Notes
    • UpdatedSyllabus
    • glossary
    • glossaryGeneration.py
    • importantTopics-kgashok
    • memCSV
    • Tower of Hanoi
    • Notes for Unit 2 - Illustrative programs
    • unit5-updated_notes
    • unit_1_notes
    • Unit 3 Control Flow Version 1
    • unit 3
      • UNIT III CONTROL FLOW, FUNCTIONS
    • unit_i_img
Powered by GitBook
On this page
  • Selection Sort
  • Context setting
  • Agenda
  • Pre-req quiz
  • Interactive Coding
  • Stage - 1
  • Stage 2
  • Selection Sort Description
  • Pseudo Code
  • Part 1.5
  • Part 2
  • A More Efficient Selection Sort
  • Summary
  • Last 2 Minute
  • Program File for Demo
  1. notes

selectSortLectureGuide

Selection Sort

Lecture outline

Context setting

Unit 4 -> Lists, Tuples and Dictionaries -> Illustrative Programs

  • It is very important to use a data type in a real-world case, to understand its true value and benefit.

  • We are covering three types of sorts

    • Comparison Algorithms - Insertion Sort and Selection Sort

    • Divide and Conquer Algorithms - Merge Sort, Quick Sort

  • We have already seen the power of Lists when we covered InsertionSort

    • Select a value from the unsorted sub-list

    • Decide where to insert it in the already_sorted sub-list

    • Right shift all the values and then insert the value

Agenda

  • Over the next 20 minutes, we shall see how lists can be used to implement SelectionSort

  • SHOW and TELL - Show Example, And Tell Theory

    • versus Tell Theory, Show Example

    • a more effective style to create engagement

      • VERY VERY effective when you students participate

      • Even more effective when students KNOW something already

Pre-req quiz

- Are you ready?
	- Do you know something already
	- Known to Unknown
  • http://j.mp/indexMinCC - is the best way to be prepared for SelectionSort

  • how do you iterate over all the elements in a list, except the last one? Write the python code to do this

  • What is the value of [1, 2, 3, 4][0:] and [1, 2, 3, 4][1:] and [1, 2, 3, 4][2:]?

  • What is the built-in function which is used to find the minimum value of a list of numbers? Create a list containing 10 random numbers. Write the python code to find the minimum value in the list.

  • What is the list method to find out the index of a value in a list?

    • How many arguments does the method accept?

    • What is the second argument for?

  • What are the ways you can swap the value in two variables?

    • What is the most pythonic way to do this?

      • Word count - Python beats Java, like crazy!

Show of hands as to many of you students reviewed all the above questions and have answers written down in your notebooks? - best practice of a engineering student is to come prepared for the class. You must spend at least 2 hours reviewing the material taught in class, and preparing for the class

Interactive Coding

Stage - 1

  1. Example of list containing [1, 2, 3, 5, 6, 4] 2. Already sorted list, except the number 4

  2. Select the minimum value in all of the unsorted list 3. 1 is the minimum - place it in index 0 4. 2 is the minimum - place it in index 1 5. 3 is the minimum - place it in index 2 6. 4 is the minimum - prepare to swap with 5 7. [1, 2, 3, 4, 6, 5] 7. 5 is the minimum - prepare to swap with 6 8. [1, 2, 3, 4, 5, 6]

  3. If necessary (i != min_i) swap the minimum value from the unsorted sublist with the element in the sorted sub-list


Stage 2

  1. Define an iteration through the list, and do this for every element in the list

  2. Initialize the right variables and execute the code

  3. Place the entire code inside inside a function definition and call it selectionsort

Selection Sort Description

  • In selectionsort, the position of the update is pre-determined, starting from the beginning of the list. We then go select the minimum value among the unsorted elements of the list, and swap it with the element in the pre-determined location.

Pseudo Code

Have seen the example, it becomes very easy to define the pseudo code for SelectionSort

repeat (numOfElements - 1) times
	for each of the unsorted elements
	select the minimum value among them
	swap minimum with first unsorted position

The Python code to implement the pseudo code above:

  def  selectionsort(alist):
    n =  len(alist)
    for i in  range(n-1):
	  unsorted = alist[i:]
	  smallest =  min(unsorted)
	  min_i = alist.index(smallest, i)
	  alist[i],alist[min_i]  = alist[min_i], alist[i]
	  print("intermediary", alist)
    return alist

Part 1.5

Break Activity for the 20th min which also helps students review what was covered until now.

  • Lead with the question: Can you improve on the above logic? How can you do it? Please discuss with your immediate neighbour.

    • if you know how to code it, write down the code in Python as well

    • Go back and improve the pseudo code as well

def selectionsort(alist):
    n = len(alist)
    # STEP 0 - iterate through the list
    for i in range(n-1):
        min_i = i
        # STEP 1 - update mini_i with index
        # of min value in unsorted alist[i+1:]
        for j in range(i+1, n):
            if alist[j] < alist[min_i]:
                min_i = j
        # STEP 2 - swap it with element at index 'i'
        if min_i != i:
            alist[i], alist[min_i] = alist[min_i], alist[i]
    return alist

Part 2

  • OPTIONAL - generate a list containing tuples, where each tuple contains both the element and the index of the element in the list

  • OPTIONAL - use a built-in function to find out the tuple containing the least value in the list

A More Efficient Selection Sort

  • uses tuples and list comprehension to make the code very efficient and eminently readable.

def selectsort(alist):
    n = len(alist)
    for i in range(n-1):
        unsorted = alist[i:]
        (minval, min_i) = min((v, i) \
            for i, v in enumerate(unsorted))
        alist[i], alist[min_i+i] = alist[min_i+i], alist[i]
        print("intermediary", alist)
    return alist

tlist = [85, 69, 12, 12, 54, 36, 45, 5]
print("unsorted", tlist)
print("sorted:", selectsort(tlist))

Summary

  1. We incrementally developed SelectionSort in a "manual mode"

  2. We arrived at the pseudo code

  3. We wrote the equivalent code for SelectionSort

In reflection, SelectionSort is just the opposite of InsertionSort. The worst case complexity of this SelectionSort is O(n^2)

Last 2 Minute

  • respond to Questions from Students

    • review the relevant Question Paper snippets

    • Ask 1 or more students questions from Pre-requisites

  • http://j.mp/selectionSortCC and http://j.mp/indexMinCC

  • Review http://j.mp/mergeVisual for the next class

Program File for Demo

Modify this file as you deem fit to demonstrate on PythonAnywhere.com or on the mu editor

  • http://j.mp/selectPAW

  • This is the script I use in my sample video http://bit.ly/selectionVideo2

Previoushistogram.pyNextSandbox to try ThinkPy2 code

Last updated 3 years ago

select