#! python # -*- coding: utf-8 -*- """ CS101 Lab solution for week 9 : list and sorting. @date: Thu Feb 26 22:07:23 2015. @author: Lilian Besson for CS101 course at Mahindra Ecole Centrale 2015. @licence: GNU Public License version 3. """ # %% Problem 1 : reminders on list # Accessing a list's elements: def print_date(date): day = date[0] month = date[1] year = date[2] # the 3rd value has index 2 (warning!) print "Day number is", day, " and month number is", month, " and the year is", year print_date([02, 03, 2015]) # Looping over a list: team = [ '134', '123', '058', '096', '155', '007', '241' ] print "This team has", len(team), "member(s), with the following roll numbers:" # example of len() for nb in team: # example of a loop rollnumber = '14XJ00' + nb # TODO: update every year! print "- someone has the roll number", rollnumber # %% Problem 2 : some basic statistical computations for a list # http://docs.scipy.org/doc/numpy/reference/routines.statistics.html def average(values): """ Compute the numerical average of the list, returned as a float number.""" n = len(values) if n == 0: return 0.0 # math convention is that an empty sum is 0 else: sum_of_values = sum(values) # Python's builtin function sum() return float(sum_of_values)/float(n) # Some example of grades from last week lab Exam for your group grades = [ 7.5, 15, 7, 2.5, 9, 9.5, 14, 12 ] print " - For these", len(grades), "students, their average is", average(grades), "out of 20. Keep working, you can all do better!" from math import sqrt def standard_deviation(values): """ Compute the standard deviation of the list, returned as a float number. More on http://docs.scipy.org/doc/numpy/reference/generated/numpy.std.html#numpy.std""" n = len(values) if n == 0: return 0.0 # math convention is that an empty sum is 0 else: mean = average(values) # our own new function average() return sqrt(sum([ (x - mean)**2 for x in values ])/float(n)) print " - For these", len(grades), "students, the standard deviation is", standard_deviation(grades), "(for grades out of 20). This high value means the grades are well spaced!\n" # One example of string formatting done well: print " - For these {n} students, their average is {avrg:.2f} (for grades out of 20. Keep working, you can all do better!".format(n=len(grades), avrg=average(grades)) print " - For these {n} students, the standard deviation is {std:.2f} (for grades out of 20). This high value means the grades are well spaced!".format(n=len(grades), std=standard_deviation(grades)) # %% Problem 3 : generating a random list of artificial grades # It starts to become interesting import random def artificial_grades(N = 231, max_grade = 100.0): """ Generate a list of N random grades from 0 to max_grade (default is 100).""" grades = [] for i in xrange(N): g = random.uniform(0, max_grade) print " - the random grade", g, "has been generated with random.uniform from 0 to", max_grade g = round(g, 1) # we want one digit after the comma only print " and we store it rounded to", g grades.append(g) return grades grades_labexam = artificial_grades(N=27, max_grade=20.0) # A shorted version as another example of list comprehension def artificial_grades(N = 231, max_grade = 100.0): return [ round(random.uniform(0, max_grade), 1) for i in xrange(N) ] # More on http://docs.scipy.org/doc/numpy/reference/generated/numpy.random.rand.html#numpy.random.rand # Generate artificial grades for the First Mid Term Exam for CS101 grades_midterm = artificial_grades(N=231, max_grade=100.0) # Automatically print average and standard deviation def print_average_std(grades, max_grade = 100.0): print " - For these {n} students, their average is {avrg:.2f} (for grades out of {max}.".format(n=len(grades), max=max_grade, avrg=average(grades)) print " - For these {n} students, the standard deviation is {std:.2f} (for grades out of {max}).".format(n=len(grades), max=max_grade, std=standard_deviation(grades)) print_average_std(grades_midterm) # %% Problem 4 : testing if a list is sorted (in O(n**2)) def is_sorted(values): """ Tests if the list is sorted (in O(n**2) worst case).""" # we assume that the list is sorted answer = True # the answer that will be produced n = len(values) for i in xrange(n): for j in xrange(i+1, n): if values[i] > values[j]: answer = False break # print "I found a pair in the wrong order, for i =", i, "and j =", j return answer # One-liner: # is_sorted = lambda l: all([ l[i] < l[j] for i in xrange(len(l)) for j in xrange(i+1, len(l))]) def print_is_sorted(values): n = len(values) if is_sorted(values): print "This list of {} values is sorted.".format(n) else: print "This list of {} values is not sorted.".format(n) print_is_sorted(grades_labexam) print_is_sorted(sorted(grades_midterm)) # %% Problem 5 : first sorting algorithm (shuffle as long as needed) def shuffle_sort(values): """ Shuffle the list as long as it is not sorted.""" while not is_sorted(values): print "The values are still not sorted, let shuffle them!" random.shuffle(values) # this shuffles the list in place # this while loop might take a LOT OF TIME to finish # but do you think it ALWAYS terminates? return values print "Trying the shuffle sort for these 8 artificial grades of the First CS101 Lab Exam:" shuffle_sort(grades) print_is_sorted(grades) # %% Problem 6 : the bubble sort def swap(values, i, j): """ Swap the ith and jth value of the list, in place.""" values[i], values[j] = values[j], values[i] def bubble_sort(values): """ Sort the list by 'fixing' every bad-ordered consecutive pair.""" n = len(values) nb_of_swapping = 0 for i in xrange(n): for j in xrange(i+1, n): if values[i] > values[j]: # print "I found a pair in the wrong order, for i =", i, "and j =", j, "so I inverted it." nb_of_swapping += 1 swap(values, i, j) print "Done with one Bubble sort, I did", nb_of_swapping, "swapping operation for sorting that list of lenght", n grades_labexam = artificial_grades(N=27, max_grade=20.0) print "==> Trying the Bubble sort for these 27 artificial grades of the First CS101 Lab Exam:" bubble_sort(grades_labexam) print_is_sorted(grades_labexam) # %% Problem 7 : using Python's sorted() function or .sort() list method # This sort is efficient, stable and in place grades = artificial_grades(N=231, max_grade=20.0) print "==> Trying Python's sorted function for these 231 artificial grades of the First CS101 Mid Term Exam:" grades = sorted(grades) # sorted() produces a new sorted list # grades.sort() does the exactly the same as the previous line print_is_sorted(grades) # %% Problem 8 : comparing the three sort algorithms : can you try to see by yourself how the computation times evolve when n the size of the list grows ? N = 1000 biglist = artificial_grades(N, max_grade=100) bigcopy1 = list(biglist) bigcopy2 = list(biglist) bigcopy3 = list(biglist) print "\n\nSorting", N, "numbers with three approaches:" # %% print "1) Python's sorted function (optimized one, in O(n log(n)):" bigcopy1.sort() # ~ 5' 50" for 10000 numbers # ~ 5' 50" for 50000 numbers print_is_sorted(bigcopy1) # %% print "2) our own Bubble sort function (naive one, in O(n ** 2):" bubble_sort(bigcopy2) # ~ 11' for 10000 numbers # ~ 11' for 50000 numbers print_is_sorted(bigcopy2) # %% print "3) our own Shuffle sort function (stupid random one, in O(n!)):" print "it will take some 10 to the power 30000 operations... do not even try to execute it!" #shuffle_sort(bigcopy3) # 10**30000 operations for 10000 numbers #print_is_sorted(bigcopy3) # FIXME this will never terminates