[Edu-sig] DS&A book

[Kirby Urner]

Thanks for the link Bruno.  I spent some time looking this over last night
and was immediately impressed that you've done parallel books using Java,
C++ and C#.  That makes your site a good place to compare and contrast, or
to move between languages (which likely mirrors your own process in writing
them).

Apropos to looking at algorithms, I was recently poking around in the MIT
computer science curriculum, which has been put on the web recently via
http://ocw.mit.edu/index.html

In Lecture 1 of 6.046J / 18.410J Introduction to Algorithms, Fall 2001 we
have a PDF version of a slideshow discussing the merge-sort algorithm -- in
the process of explaining how to derive O(n), a measure of an algorithm's
efficiency.

I've appended my Pythonic implementation of merge-sort.

I'll be studying you book some more as time goes on.  I've added it to
Favorites in my bookmarks.

Kirby

PS:  Arthur should be pleased, as this is all about using Python in upper
level compsci courses, a trimtab as he sees it (point of leverage, for
making Python in education really fly).

===============
"""
See:
http://ocw.mit.edu/NR/rdonlyres/Electrical-Engineering-and-Computer-Science/
6-046JIntroduction-to-AlgorithmsFall2001/55D1B4B5-BDA5-4E9E-B05E-5AB0EC974F8
A/0/lecture01.pdf
"""

import random

def merge_sort(thelist):
    """
    Recursive merge sort.  Divide list in half recursively down
    to single entries, merge back together
    """
    if len(thelist) == 1:
        return thelist
    else:
        # slice list in half
        t1 = thelist[:len(thelist)//2]
        t2 = thelist[len(thelist)//2:]
        return merge( merge_sort(t1), merge_sort(t2) )

def merge(t1,t2):
    """
    Merge two lists into one, popping items from one or the other, 
    smaller before larger
    """
    merged = []
    while len(t1) + len(t2) > 0:
        if not len(t2):
            merged.append(t1.pop(0))
        elif not len(t1):
            merged.append(t2.pop(0))
        elif (t1[0] < t2[0]):
            merged.append(t1.pop(0))
        else:
            merged.append(t2.pop(0))
    return merged

def utest():
    thelist = range(100)
    random.shuffle(thelist)
    print thelist
    print '--->'
    print merge_sort(thelist)

if __name__ == '__main__':
    utest()


> -----Original Message-----
> From: edu-sig-bounces at python.org [mailto:edu-sig-bounces at python.org] On
> Behalf Of Bruno R. Preiss
> Sent: Wednesday, October 01, 2003 7:03 PM
> To: edu-sig at python.org
> Subject: [Edu-sig] DS&A book
> 
> I have prepared a draft of a book entitled "Data Structures and
> Algorithms with Object-Oriented Design Patterns in Python." A web
> version is now available online at http://www.brpreiss.com/books/opus7.
> Bruno
> --
> Bruno R. Preiss
> brpreiss at brpreiss.com
> www.brpreiss.com