sorting items in python

Question

Good day everyone, I need help with sorting and writing a sorting function in python. I am trying to write a function insert_in_order which takes a list of strings items and a string item. I'm trying to do this assuming that items is already sorted in alphabetical order and i must insert item into the correct position in items

Also

in regards to the same problem i am facing, i also want to right a function remove which takes a list items and a string item. This function should remove the first occurrence of item in items. Also, if item does not occur at all in items, the function should leave items unchanged.

Edit:

my original set of functions is as follows

def read_list(fname):
    items = []
    with open(fname, 'r') as fin:
        for line in fin:
            items = insert_in_order(items, line[:-1])

    return items


def write_list(items, fname):
    fout = open(fname, 'w')
    for item in items:
        fout.write(item + '\n')
    fout.close()

and i also have a test file which is supposed to test those functions:

class TestLabThre(unittest.TestCase):
    def test_read_list(self):
        self.assertEqual(
                read_list('lab06ReadTest.txt'),
                ['a', 'b', 'c', 'd', 'e'])

def test_write_list(self):
    write_list(['a', 'b', 'c', 'd', 'e'], 'lab06WriteTest.txt')
    in_file = open('lab06WriteTest.txt', 'r')
    self.assertEqual(in_file.read(), 'a\nb\nc\nd\ne\n')

my insert_in_order and remove functions are supposed to be added to the functions so that when i run my tests, they pass. But i get a "failed test" every time.

I'm really confused and any help pointing me in the right direction will be appreciated.

unutbu · Accepted Answer · 2013-04-06 21:15:25Z

3

Use bisect.insort_left to insert an item x into a list a, and keep it sorted assuming a is sorted.

Use list.remove to remove the first occurence of value from a list. This function raises a ValueError if the value is not in the list. So you'll need to wrap the call in a try..except to handle the exception -- see below for an example.

import bisect

cheese = sorted('manchego stilton brie gouda'.split())
print(cheese)
# ['brie', 'gouda', 'manchego', 'stilton']

item = 'gorgonzola'
bisect.insort_left(cheese, item)
print(cheese)
# ['brie', 'gorgonzola', 'gouda', 'manchego', 'stilton']

try:    
    cheese.remove('manchego')
except ValueError: 
    pass
print(cheese)
# ['brie', 'gorgonzola', 'gouda', 'stilton']

edited Apr 6, 2013 at 21:15

answered Apr 6, 2013 at 21:09

unutbu

886k197 gold badges1.9k silver badges1.7k bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

ovgolovin Over a year ago

Why don't you use bisect.bisect_left to find the position of the item and then list.pop to remove it. This will make search log(n), not O(n)?

unutbu Over a year ago

Deleting an item from a Python list is O(n), so whether we use list.pop or list.remove we are still O(n).

ovgolovin Over a year ago

Yeah. But then why use bisect at all?

unutbu Over a year ago

The OP has a list. Insertion and deletion from the list is going to be O(n). Conversion to a blist will be O(n). So all solutions at best will be O(n). bisect.insort_left does precisely what the OP asked for, and since it is written in C it will run faster than a Python loop.

Kuma Over a year ago

in my case, is "cheese" equal to "items" or "item"? @unutbu

|

Community · Accepted Answer · 2017-05-23 10:25:12Z

1

Regarding your sorting problem, a quick solution which requires no additional modules (which may not be computationally optimal, but good enough in many cases):

>>> your_list = ['a', 'b', 'c']
>>> your_list.append('baa')
>>> your_list.sort()
>>> print your_list
['a', 'b', 'baa', 'c']

For removing items, just use the list's remove method with an exception handler, as described in @unutbu's solution.

edited May 23, 2017 at 10:25

CommunityBot

11 silver badge

answered Apr 6, 2013 at 21:16

Henry Gomersall

8,7423 gold badges37 silver badges61 bronze badges

2 Comments

Kuma Over a year ago

i'm trying to implement that in a function format. please look at my edit (in my original post)

Henry Gomersall Over a year ago

So write a function. I feel perhaps you should go back and read some tutorials if you can't manage to write a function by yourself; that's pretty basic stuff.

ovgolovin · Accepted Answer · 2013-04-06 21:11:28Z

0

Look at bisect module which finds the position of insertion or deletion in sorted list.

Also, note, that insertions and deletions in list is O(n) as they require to shift all the items to the right of the place of insertion or deletion. You may look into blist module to use instead of list which performs these operations in O(log(n)).

answered Apr 6, 2013 at 21:11

ovgolovin

13.5k7 gold badges53 silver badges80 bronze badges

Collectives™ on Stack Overflow

sorting items in python

3 Answers 3

7 Comments

2 Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

7 Comments

2 Comments

Comments

Related