Add elements into a sorted array in ascending order

Question

I have the following program which implements a sorted bag. It adds elements successfully in sorted order (ascending order) when giving a list. When I created a new sorted bag with the argument of another bag, it's not in sorted order (instead in descending order). See below

Thanks for the help

# Array Class
#----------------------------------------------------
class Array(object):        # Represents an array.
DEFAULT_CAPACITY = 5
def __init__ (self, capacity, fillValue = None):
'''Capacity = static size of array. fillValue is placed at each element'''
    self._items = list()
    self._capacity = capacity
    self._logicalSize = 0
    self._fillValue = fillValue
    for count in range(capacity):
        self._items.append(fillValue)

def __getitem__(self, index): return self._items[index]

def __setitem__(self, index, newItem):      
    self._items[index] = newItem

# ArraySortedBag Class
#----------------------------------------------------
class ArraySortedBag(object):
'''An array-based bag implementation'''
def __init__(self, sourceCollection = None):
    '''Sets the initial state of self, which includes the contents
    of sourceCollection, if it's present'''
    self._items = Array(10)
    self._size  = 0
    if sourceCollection:
        for item in sourceCollection:
            self.add(item)

def __len__(self): return self._size

def __iter__(self):
    cursor = 0
    while cursor < len(self):
        yield self._items[cursor]
        cursor += 1

def add(self, item):
    '''Adds item to self.'''        
    insertIndex = 0

    # First found the index where the item will be inserted at
    for i in range(self._size):
        if self._items[i] > item:
            insertIndex = i
            break
    # Then, shift items down by one position until the insertIndex,
    for i in range (self._size, insertIndex, -1):
        self._items[i] = self._items[i-1]

    # Last, assign value to _items[insertIndex]
    self._items[insertIndex] = item
    self._size += 1

# Test Driver
#----------------------------------------------------
if __name__ == "__main__":
b1 = ArraySortedBag([2000, 2, 1000])
print ("Display bag b1")
for i in b1:              # <------ Correct order, ascending order
    print (i)

b2 = ArraySortedBag(b1)
print ("\nDisplay bag b2")
for i in b2:                 # <----- Wrong order, descending order
    print (i)

Please fix the indenting of the code in your question.

martineau
– martineau

2015-04-02 09:20:29 +00:00
Commented Apr 2, 2015 at 9:20 — martineau
– martineau, Commented Apr 2, 2015 at 9:20

xxyzzy · Accepted Answer · 2015-04-02 09:28:56Z

1

In the second instantiation of class ArraySortedBag, you are passing a sorted list. The ArraySortedBag.init() method adds the items using the add() method. When add() is called the item to be added is never less than the existing list. Therefore insertIndex remains equal to zero. Therefore the new item is added to the beginning of the list.

# First found the index where the item will be inserted at
for i in range(self._size):
    if self._items[i] > item:     # item is never less than self._items[i]
        insertIndex = i
        break

edited Apr 2, 2015 at 9:28

answered Apr 2, 2015 at 9:04

xxyzzy

5884 silver badges7 bronze badges

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

5 Comments

user1972031 Over a year ago

Why is the item to-be-added always less than the existing list?

user1972031 Over a year ago

If so, how to fix the code, so that adding elements would result in ascending order? Thanks --

martineau Over a year ago

While adding presorted items, each item added will be greater that any already added to the internal list.

xxyzzy Over a year ago

My statement was wrong but I think the conclusion holds. I will edit my response in a few minutes.

user1972031 Over a year ago

Thanks xxyzzy for pointing out my bug in add() method. Thanks Martineau for clarifications. Thanks all others for helpful suggestions.

sanyi · Accepted Answer · 2015-04-02 11:31:20Z

1

For adding items into a sorted list so that one maintains the list sorted, I recommend using the bisect library's insort_left or insort_right.

import bisect

list = [10, 20, 30]

bisect.insort(list, 25)
bisect.insort(list, 15)

print list

answered Apr 2, 2015 at 11:31

sanyi

6,2792 gold badges21 silver badges30 bronze badges

Collectives™ on Stack Overflow

Add elements into a sorted array in ascending order

2 Answers 2

5 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

5 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related