There is a sorting function as such:
def iterative_insertion_sort(A):
'''Sort A iteratively.'''
for i, key in enumerate(A[1:]):
while i > -1 and A[i] > key:
print(id(key), id(A[i+1]))
A[i + 1] = A[i]
print(id(key), id(A[i+1]))
i = i - 1
A[i + 1] = key
The sorting function is working fine with floats.
Sample output: ./insertion_sort.py .23 .21 .26
140566861513304 140566861513304
140566861513304 140566861513256
[0.21, 0.23, 0.26]
But I have my custom class called lList which have link(another custom class) type of elements. When I input instances of lList, the sort doesn't work correctly.
Sample output: 0.23 0.21 0.26 /
139732300992808 139732300992808
139732300992808 139732300992808
0.23 0.23 0.26 /
As we can see the id of key and the array element is different after the assignment statement in case of float. But in case of the custom class even after the assignment operation, the id of key and array element is same. This is the cause of trouble.
I suspect the problem is because of the fact that floats are immutable, whereas my custom class isn't. My question is what is the best way to tackle the situation?
Note: I would prefer zero to minimal changes in my sorting procedure. However, I am willing to customize my lList or link class.
P.S. I have just posted only the relevant pieces of code. If the class definition is also needed, just mention it, I will add that too.
Many Thanks!
Update:
link definition:
class link:
'''Implement link.'''
def __init__(self, key=None):
self.key = key
self.nxt = None
self.prev = None
def __str__(self):
'''Print link.'''
if self:
return str(self.key)
else:
return '/'
def __gt__(self, other):
return self.key > other.key
This is the lList definition:
class lList:
'''Implement list of links.'''
def __init__(self):
self._head = None
self._numberOfLinks = 0
def list_insert(self, x):
'''Insert link x at the beginning of list.'''
x.nxt = self._head
if self._head:
self._head.prev = x
self._head = x
self._numberOfLinks += 1
def __str__(self):
'''Print list of links.'''
listFormat = ''
temp = self._head
while temp:
listFormat += str(temp) + ' '
temp = temp.nxt
else:
listFormat += '/ '
return listFormat
def get_data(self, position):
'''Return link from list at position position from head.'''
i = 0
temp = self._head
while i < position:
temp = temp.nxt
i += 1
return temp
def set_data(self, position, newLink):
'''Overwrite key of link at position distance from head of list with key of newLink.'''
i = 0
temp = self._head
while i < position:
temp = temp.nxt
i += 1
temp.key = newLink.key
def __getitem__(self, position):
if type(position) is slice:
return [self[i] for i in range(*position.indices(len(self)))]
elif type(position) is int:
if position < 0:
position += len(self)
if position >= len(self):
raise IndexError("The index (%d) is out of range."%position)
return self.get_data(position)
else:
raise TypeError("Invalid argument type.")
def __setitem__(self, position, value):
self.set_data(position, value)
def __len__(self):
return self._numberOfLinks
And this is the mimimal code that creates the same scene:
test = lList()
l = link(.26)
test.list_insert(l)
l = link(.21)
test.list_insert(l)
l = link(.23)
test.list_insert(l)
print(test)
iterative_insertion_sort(test)
print(test)
Yes, the problem is less one of immutability and more one of shared references.
When sorting floating point values, you store a reference to the float stored in A[1] in key. You then alter the reference in A[1] with the value from A[0]. That means that A[1] now points to a different object, and later on setting A[0] to key is fine.
But when sorting your linked list, you never alter A[1]. You alter an attribute of A[1]. key and A[1] continue to point to the same link instance, and setting A[1].key is visible in key.key too.
You can fix this by actually replacing the whole link object by a new one:
def set_data(self, position, newLink):
'''Overwrite key of link at position distance from head of list with key of newLink.'''
i = 0
temp = self._head
while i < position:
temp = temp.nxt
i += 1
newlink = link(newLink.key)
if temp.prev:
temp.prev.nxt = newlink
else:
self._head = newlink
newlink.nxt = temp.nxt
This makes it equivalent to setting a new value in a Python list object:
(4302695168, 4302695168)
(4302695168, 4303149248)
0.21 0.23 0.26 /