module location

[Jadellll]

Hi, I'm looking for where either the sort module or the sorted() function resides.
I'm thinking a module in the default folders, but have no idea where it is, or how to locate it (sorted is in the path, but I don't know how to display a parent based of its function)
Also, if this is in a module/group of built in functions, I would like to know that file aswell.
The reason is I'm trying to learn how for example sorted() works (so I could build my own instead of using the built in) for knowledge's sake. I could ask for how it works, but knowing how to find multiple functions would be better.
Thanks a bunch
-Brandon

[bumsfeld]

Functions sort() and sorted() reside in the core of the Python interpreter which is written in C and compiled. On Windows the Python core is for instance in the dynamic link library called python25.dll which the Python installer put into directory C:\WINDOWS\system32

Here is example of the rather slow but classic bubble sort for integer list:

import random

def make_list(num_elements):
    """
    make list of num_elements random integers between 0 and 1000
    """
    return [random.randint(0, 1000) for i in xrange(num_elements)]

def bubble_sort(list1):
    # make true copy of list1 so there is no feedback
    list1 = list(list1)
    for i in xrange(len(list1) - 1, 0, -1):
        for j in xrange(1, i + 1):
            if list1[j - 1] > list1[j]:
                temp = list1[j - 1]
                list1[j - 1] = list1[j]
                list1[j] = temp
    return list1

list2 = make_list(100)

print list2  # unsorted

print "-"*70

list3 = bubble_sort(list2)

print list3   # now sorted

Hope that helps.

[Jadellll]

right now I don't get it, but it will help after some analyzation.
Thanks.

[vegaseat]

Putting in a temporary test print line might just help you better understand what is going on ...

def bubble_sort(list1):
    # make true copy of list1 so there is no feedback
    list1 = list(list1)
    for i in xrange(len(list1) - 1, 0, -1):
        print list1  # a test print
        for j in xrange(1, i + 1):
            if list1[j - 1] > list1[j]:
                temp = list1[j - 1]
                list1[j - 1] = list1[j]
                list1[j] = temp
    return list1

list2 = reversed(range(10))

print bubble_sort(list2)

"""
my output -->
[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
[8, 7, 6, 5, 4, 3, 2, 1, 0, 9]
[7, 6, 5, 4, 3, 2, 1, 0, 8, 9]
[6, 5, 4, 3, 2, 1, 0, 7, 8, 9]
[5, 4, 3, 2, 1, 0, 6, 7, 8, 9]
[4, 3, 2, 1, 0, 5, 6, 7, 8, 9]
[3, 2, 1, 0, 4, 5, 6, 7, 8, 9]
[2, 1, 0, 3, 4, 5, 6, 7, 8, 9]
[1, 0, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
"""

For instance watch the zero bubble/move from the end to the front.

[Jadellll]

yeah I think I'm getting it now. The first for loop finds each element in reverse order. The second tests that elements vs each other element. If its greater, the smaller one goes to j-1, if its bigger, it goes to j. right?

[vegaseat]

yeah I think I'm getting it now. The first for loop finds each element in reverse order. The second tests that elements vs each other element. If its greater, the smaller one goes to j-1, if its bigger, it goes to j. right?

Yes, you got the hang of it!

You can improve the bubble sort quite a bit by using a tuple swap and breaking out if the list is sorted. Here is an example without the check, it blindly goes through the whole loop ...

def bubble_sort(list1):
    # make true copy of list1 so there is no feedback
    list1 = list(list1)
    for i in xrange(len(list1) - 1, 0, -1):
        print list1  # a test print
        for j in xrange(1, i + 1):
            if list1[j - 1] > list1[j]:
                # use a tuple swap
                list1[j - 1], list1[j] = list1[j], list1[j - 1]
    return list1

list2 = [0, 1, 2, 3, 5, 4, 6, 7, 8, 9]  # nearly sorted

list3 = bubble_sort(list2)
print '-'*30
print list3

"""
my output -->
[0, 1, 2, 3, 5, 4, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
------------------------------
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
"""

In this example we are checking for completion of the sorting ...

def bubble_sort(list1):
    # make true copy of list1 so there is no feedback
    list1 = list(list1)
    for i in xrange(len(list1) - 1, 0, -1):
        swap_test = False
        print list1  # a test print
        for j in xrange(1, i + 1):
            if list1[j - 1] > list1[j]:
                # use a tuple swap
                list1[j - 1], list1[j] = list1[j], list1[j - 1]
                swap_test = True
        if swap_test == False:
            break
    return list1

list2 = [0, 1, 2, 3, 5, 4, 6, 7, 8, 9]  # nearly sorted

list3 = bubble_sort(list2)
print '-'*30
print list3

"""
my output -->
[0, 1, 2, 3, 5, 4, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
------------------------------
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
"""

[Jadellll]

Well I can officially say I totally get it.
Thanks :)