I'm really confused at the moment. I'm not looking for anyone to give me the answers, but if you could at least give hints on what i need to do in each method, i'll be happy!! FYI, one of the main things that's confusing me is that i'm not allowed to use any built in methods. Only can use the index operator [], the splice operator [:], the + operator for list concatenation, and the len function. I've attempted to begin doing the few that i know, but i'm sure they're not correct.

I tried explaining what each method is supposed to do the best that i can:

class SortedList:
    def __init__(self):
    """
    Creates an empty list
    """
        self.L = []
        
    def insert(self, item):
    """
    Inserts new item into some sorted list, entering the item in
    the corrected (Sorted) posistion in the list.
    """
        self.L.append(item)
        
    def remove(self):
    """
    Removes an item from a sorted list. If item isn't in list
    List remains unchanged.
    """
        new_list = []
        for item in self.L:
            if item not in new_list:
                new_list.append(item)
            return new_list
        
    def size(self):
    """
    Method returns the number of occurrences of a given item in
    a sorted list
    """
        return len(self.L)
    
    def count(self):
    """
    Method returns the number of occurrences of a given item in a
    sorted list
    """

    def belongs(self):
    """
    Method returns True if a given item belongs to the sorted list
    and False otherwise.
    """
        if i in self.L:
            return True
        else:
            False
            
    def __str__(self):
    """
    Method returns a printable version of the sorted list, which is
    a string containing the elements of the sorted list, surrounded by
    square braces.
    """
        s1 = "List: " + str(self.L)
        
    def __add__(self):
    """
    Method overloads the + operator and returns the sum of two sorted
    lists.
    """

    def __mul__(self):
    """
    Method overloads the * operator and returns the product of a sorted
    list and a positive interger.
    """

Recommended Answers

All 12 Replies

You have at least line 24 incorrectly indented inside the loop. The docstrings are not indented into inside functions.

And you are missing the loop to find the correct position to insert the value in insert method; size is returning whole length, not only requested part, remove is missing parameter for value to remove and the action it does looks like set operation not removal of certain value (one or all, I do not know the spec),__add__ and __mul__ is missing all definition (and you need to define __radd__ also), your __str__ method does not return value (and it is useful to have also __repr__, even if you just assign it to the __str__ function)...

You should do methods one by one, and continue only you are tested the new function basically correct (some errors you do find later, but most should be found before doing the next function).

Is this for production or is it just an exercise?

If it is for production use bisect.insort to insert items into a list in sorted order.

If is for production, use blist instead.

For serious exercise bisect is the reasonable strategy, maybe after some naive implementation (I did simple implementation of your task using itertools.takewhile for simple short cutting because of data is sorted).

I'm not sure if i understand what you mean.. What is "production" And whats blist?

"Production" is a word that refers to source or code used for practical application. It means you're writing a real program that someone, somewhere is going to use to do something.

"blist" is a third party module. People write third party modules for other people to use to make programs. Third party modules can offer things the standard Python distribution doesn't offer, such as additional functionality or better performance.

I suggested bisect thinking you wanted to write a program using just what is available in a standard Python distribution, but pyTony is right that if you have differing requirements such as a more performant implementation you should research which third party options are available and decide which - if any - to use.

commented: Nice signature links and nice explanation. +13

"Production" is a word that refers to source or code used for practical application. It means you're writing a real program that someone, somewhere is going to use to do something.

"blist" is a third party module. People write third party modules for other people to use to make programs. Third party modules can offer things the standard Python distribution doesn't offer, such as additional functionality or better performance.

I suggested bisect thinking you wanted to write a program using just what is available in a standard Python distribution, but pyTony is right that if you have differing requirements such as a more performant implementation you should research which third party options are available and decide which - if any - to use.

Oh it's not really a program that someone somewhere is going to use. It's just a small part of an assignment that i have in my beginners class.

I would ask my teacher permission to use the bisect. you can tell it is our recomendation. It would make your code actually quite usefull code without reducing any way your learning experience, as otherwise I would bet that most solutions would use linear scan of list even looking value after the place of item is passed or when value is less than first or more than last value in list.

Simple example of bisect:

>>> values = [1, 3, 5, 10]
>>> import bisect

>>> values.insert(bisect.bisect(values, 4), 4)
>>> values
[1, 3, 4, 5, 10]
>>>
commented: Good example. +6

From my understanding on what it's asking, when i run my code, it should run something like: print("Inserting items 42, 11, 3, 6, 63 in L1..")

L1.insert(42)
L1.insert(11)
L1.insert(3)
L1.insert(6)
L1.insert(63)
print("The SortedList L1 is now: ")
    print("Correct answer: [3 6 11 42 63]")

print(" Your answer:", L1) The bisect method would still be of better use?

Bisect is one of the better options.

There are performance implications with any kind of sorting. Bisection has logarithmic time complexity. I don't know what the time complexity is for sorting in the standard Python distribution.

If we are adding a lot of items then at some point simply extending the list and sorting it will be faster than insorting each item individually. (Probably.) It's much more elegant too.

import bisect
#making a new list
x = [5, 4, -3, 100, 88.3, -23.9]
#sort it
x.sort()
print(x)
#[-23.9, -3, 4, 5, 88.3, 100]
#adding an item to an existing list
#preserving sorting
bisect.insort(x, 65.5)
print(x)
#[-23.9, -3, 4, 5, 65.5, 88.3, 100]
#adding many items to an existing list
x.extend((75.4, -100, 999))
#sort it
x.sort()
print(x)
#[-100, -23.9, -3, 4, 5, 65.5, 75.4, 88.3, 100, 999]

That's where i'm confused at. I'm sure the bisect method works, but the module is already created.. What i'm asked to do is come up with the code that runs it. The method that i'm asking for help on is just one little part of the code. A sample of what it looks like:

print("Inserting items 42, 11, 3, 6, 63 into L1...")
    L1.insert(42)
    L1.insert(11)
    L1.insert(3)
    L1.insert(6)
    L1.insert(63)
print("The SortedList L1 is now: ")
    print("Correct answer: [3 6 11 42  63 ]")
    print("   Your answer:", L1)

    ans = input("Ready for the next test [y/n]? ")
    if ans != 'y':
        exit()

You mean you want to write your own implementation?

The source for most standard modules is included with the standard Python distribution. On Windows they can typically be found in "C:\Python32\Lib". The two digits can be different depending on your Python version.

The source for "insort_right":

def insort_right(a, x, lo=0, hi=None):
    """Insert item x in list a, and keep it sorted assuming a is sorted.

    If x is already in a, insert it to the right of the rightmost x.

    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if x < a[mid]: hi = mid
        else: lo = mid+1
    a.insert(lo, x)

You mean you want to write your own implementation?

The source for most standard modules is included with the standard Python distribution. On Windows they can typically be found in "C:\Python32\Lib". The two digits can be different depending on your Python version.

The source for "insort_right":

def insort_right(a, x, lo=0, hi=None):
    """Insert item x in list a, and keep it sorted assuming a is sorted.

    If x is already in a, insert it to the right of the rightmost x.

    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if x < a[mid]: hi = mid
        else: lo = mid+1
    a.insert(lo, x)

I'm not sure. I've emailed him, but no response and it's been a few days.. Here's a briefing on what it's asking me to do.. insert: Insert a new item into the sorted list. The item is inserted in the corrected (sorted) position in the sorted list. You're not allowed to use any built-in list functions or methods other [], [:], +, and len. For example, if L1 is the sorted list 3, 5, 18, 22 then after the command L1.insert(21), L1 will be 3, 5, 18, 21, 22. Observe that this method has two parameters: self and item (the item to be inserted).

def insert(self, item):
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.