# Sorting a double linked list

• (2 Pages)
• 1
• 2

## 17 Replies - 3283 Views - Last Post: 29 March 2013 - 01:50 AMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=316685&amp;s=cd355ee0a51d1cbc2c9f8e2dc669ccb6&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 medaa

Reputation: 6
• Posts: 106
• Joined: 24-October 12

# Sorting a double linked list

Posted 25 March 2013 - 02:17 PM

Im trying to sort a doubly linked list, but Im having a problem implementing the sort function:

Here are all the functions:

```from d_linked_node import d_linked_node
from item import item

def __init__(self):
self.__tail=None
self.__size=0

def search(self, item):
found = False
if current.getData() == item:
found= True
else:
current = current.getNext()
return found

def index(self, item):
found = False
index = 0
if current.getData() == item:
found= True
else:
current = current.getNext()
index = index + 1
index = -1
return index

if (self.__tail == None):
self.__size += 1
self.__tail = temp
else:
self.__size += 1

def remove(self, item):
if (self.search(item)):
inde = self.index(item)
self.__size -= 1
if (inde == 0):
self.__tail = None
else:
else:
for i in range(inde):
temp = temp.getNext()
a = temp.getPrevious()
a.setNext(temp.getNext())
if (a.getNext() == None):
self.__tail = a
else:
a.getNext().setPrevious(a)

def append(self, item):
if self.__size == 0:
else:
self.__size +=1
self.__tail.setNext(temp)
self.__tail = temp

def insert(self, pos, item):
for i in range(pos):
temp = temp.getNext()
if (pos == 0):
if (self.__size == 0):
self.__tail = temp_in
else:
temp_in.getNext().setPrevious(temp_in)
self.__size +=1
else:
if (temp == None):
temp_in.setPrevious(self.__tail)
self.__tail.setNext(temp_in)
self.__tail=temp_in
else:
temp_in.setNext(temp)
temp.getPrevious().setNext(temp_in)
temp_in.setPrevious(temp.getPrevious())
temp.setPrevious(temp_in)
self.__size +=1

def pop1(self):
temp = self.__tail
if (self.__size < 2):
self.__tail = None
self.__size = 0
else:
temp.getPrevious().setNext(None)
self.__tail = temp.getPrevious()
self.__size -= 1
return temp.getData()

def pop(self, pos):
self.__size -= 1
if (pos == 0):
self.__tail = None
else:
return temp.getData()
else:
for i in range(pos):
temp = temp.getNext()
a = temp.getPrevious()
a.setNext(temp.getNext())
if (a.getNext() == None):
self.__tail = a
else:
a.getNext().setPrevious(a)
return temp.getData()

def search_larger(self, item):
a = 0
while temp != None:
if (temp.getData() > item):
break
temp = temp.getNext()
a +=1
if(temp == None):
return -1
return a

def get_size(self):
return self.__size

def get_item(self, pos):
if (pos < 0):
if (pos < -self.__size):
raise Exception("pos doesn't exist")
temp = self.__tail
for i in range(pos,-1):
temp = temp.getPrevious()
return temp.getData()
else:
if (pos >= self.__size):
raise Exception("pos doesn't exist")
for i in range(0,pos):
temp = temp.getNext()
return temp.getData()

def sort(self):
for index in range(len(self)):
smallindex=index
for i in range(index,len(self)):
if self[i]<self[smallindex]:
smallindex=i

temp=self[index]
self[index]=self[smallindex]
self[smallindex]=temp
pass

#you need to implement the sort by using selection sort to sort a list of items
#sort by the specified attribute, either "price" or "quantity"
def sort_by_attr(self, attr):
if attr=="Price":
for index in range(len(self)):
smallindex=index
for i in range(index,len(self)):
if self[i]<self[smallindex]:
smallindex=i

temp=self[index]
self[index]=self[smallindex]
self[smallindex]=temp

elif attr=="Quantity":
for index in range(len(self)):
smallindex=index
for i in range(index,len(self)):
if self[i]<self[smallindex]:
smallindex=i

temp=self[index]
self[index]=self[smallindex]
self[smallindex]=temp

def __str__(self):
pr = ""
while (temp != None):
pr = pr + str(temp.getData()) + " "
temp = temp.getNext()
pr = pr[:-1]
return pr

def test():

assert is_pass == True, "fail the test"

is_pass = (str(linked_list) == "Hello World")
assert is_pass == True, "fail the test"

assert is_pass == True, "fail the test"

assert is_pass == True, "fail the test"

assert is_pass == True, "fail the test"

assert is_pass == True, "fail the test"

assert is_pass == True, "fail the test"

assert is_pass == True, "fail the test"

assert is_pass == True, "fail the test"

for i in range(0, 10):
int_list2.remove(1)
int_list2.remove(3)
int_list2.remove(2)
int_list2.remove(0)
is_pass = (str(int_list2) == "9 8 7 6 5 4")
assert is_pass == True, "fail the test"

for i in range(11, 13):
int_list2.append(i)
is_pass = (str(int_list2) == "9 8 7 6 5 4 11 12")
assert is_pass == True, "fail the test"

for i in range(21, 23):
int_list2.insert(0,i)
is_pass = (str(int_list2) == "22 21 9 8 7 6 5 4 11 12")
assert is_pass == True, "fail the test"

is_pass = (int_list2.get_size() == 10)
assert is_pass == True, "fail the test"

is_pass = (int_list.get_size() == 0)
assert is_pass == True, "fail the test"

for i in range(0, 1000):
int_list.append(i)
correctOrder = True

is_pass = (int_list.get_size() == 1000)
assert is_pass == True, "fail the test"

for i in range(0, 200):
if int_list.pop1() != 999 - i:
correctOrder = False

is_pass = correctOrder
assert is_pass == True, "fail the test"

is_pass = (int_list.search_larger(200) == 201)
assert is_pass == True, "fail the test"

int_list.insert(7,801)

is_pass = (int_list.search_larger(800) == 7)
assert is_pass == True, "fail the test"

is_pass = (int_list.get_item(-1) == 799)
assert is_pass == True, "fail the test"

is_pass = (int_list.get_item(-4) == 796)
assert is_pass == True, "fail the test"

if is_pass == True:
print ("=========== Congratulations! Your have finished exercise 1! ============")

if __name__ == '__main__':
test()

```

and heres the tests im trying to pass:
```from d_linked_list import *
import random

def test_sort_integer():

for i in range(1000):
data = random.randint(1, 1000)
integer_list.append(data)

#print(integer_list)

integer_list.sort()

#print(integer_list)

prev_data = integer_list.pop(0)
cur_data = integer_list.pop(0)

while integer_list.get_size() > 0:
assert cur_data >= prev_data, 'error: linked list is not sorted'

prev_data = cur_data
cur_data = integer_list.pop(0)

print('========== cong ==================')

if __name__ == '__main__':
test_sort_integer()
```

```from d_linked_list import *
import random

def test_sort_by_attr(attr):

for i in range(10):
name = 'goods' + str(i)
price = random.randint(0, 1000)
quantity = random.randint(1, 100)

good = item(name, price, quantity)

item_list.append(good)

#print(item_list)

item_list.sort_by_attr(attr)

#print(item_list)

prev_data = item_list.pop(0)
cur_data = item_list.pop(0)

while item_list.get_size() > 0:
if attr == 'price':
assert cur_data.get_price() >= prev_data.get_price(), \
'error: linked list is not sorted by price'
elif attr == 'quantity':
assert cur_data.get_quantity() >= prev_data.get_quantity(), \
'error: linked list is not sorted by quantity'
else:
raise Exception('illegal attribute')

prev_data = cur_data
cur_data = item_list.pop(0)

print('========== cong on ' + attr + ' ==================')

def test_sort():
test_sort_by_attr('price')
test_sort_by_attr('quantity')

if __name__ == '__main__':
test_sort()
```

but I know both my sort functions are wrong but I cant figure out why!!

Is This A Good Question/Topic? 1

## Replies To: Sorting a double linked list

### #2 jon.kiparsky

• Pancakes!

Reputation: 8930
• Posts: 15,437
• Joined: 19-March 11

## Re: Sorting a double linked list

Posted 25 March 2013 - 02:21 PM

Please be more specific about what's happening, or what's not happening that you'd like to have happen. It's easier to help solve your problem if you tell us what your problem is!

### #3 medaa

Reputation: 6
• Posts: 106
• Joined: 24-October 12

## Re: Sorting a double linked list

Posted 25 March 2013 - 02:27 PM

Heres the error Im getting:
File "d_linked_list.py", line 170, in sort
for index in range(len(self)):
builtins.TypeError: object of type 'd_linked_list' has no len()

I get the same error for both tests when I run them.
For the def sort(self), I want to sort a d-list in ascending order and for def sort by_att(self, attar):, I want to sort the list by either price or quantity
Im hoping you can look at my sort functions and tell me what Im doing wrong.

### #4 jon.kiparsky

• Pancakes!

Reputation: 8930
• Posts: 15,437
• Joined: 19-March 11

## Re: Sorting a double linked list

Posted 25 March 2013 - 02:37 PM

len(foo) simply calls foo's __len__ method. You haven't defined that method for your linked list.

### #5 baavgai

• Dreaming Coder

Reputation: 6379
• Posts: 13,629
• Joined: 16-October 07

## Re: Sorting a double linked list

Posted 25 March 2013 - 02:37 PM

```	def sort(self):
for index in range(len(self)):
smallindex=index
for i in range(index,len(self)):
if self[i]<self[smallindex]:

```

How exactly does len(self) work with your class? How does self[i] work? If you want that kind of functionality, you could write it. You haven't. Though you do have some methods you might consider calling. Note, sorting a linked list based on index position is probably the worst possible choice.

### #6 medaa

Reputation: 6
• Posts: 106
• Joined: 24-October 12

## Re: Sorting a double linked list

Posted 25 March 2013 - 02:53 PM

what Im trying to do is take my list and go through each element and do a compare and swap type of thing

### #7 medaa

Reputation: 6
• Posts: 106
• Joined: 24-October 12

## Re: Sorting a double linked list

Posted 25 March 2013 - 03:00 PM

Do you recommend at faster and simpler way?

### #8 baavgai

• Dreaming Coder

Reputation: 6379
• Posts: 13,629
• Joined: 16-October 07

## Re: Sorting a double linked list

Posted 25 March 2013 - 05:58 PM

Faster or simpler, pick one...

I'd just do a simple bubble sort. If you only swap the values, not the nodes, it's pretty straight forward. Even if do swap the nodes, it's not too bad.

Note, a proper bubble sort, not one of those horrid index loop things.

e.g.
```def sort(self):
swapped = True
while swapped:
swapped = False
while node.next:
if node.next.value < node.value:
# ...

```

Hmmm... your instructions are to use a selection sort? Same deal, hold on to your nodes. Not indexes:
```def sort(self):
while i.next:
selected = i
j = i.next
while j:
if j.value < selected.value:
# ...

```

### #9 medaa

Reputation: 6
• Posts: 106
• Joined: 24-October 12

## Re: Sorting a double linked list

Posted 25 March 2013 - 10:48 PM

```def sort(self):
while i.next:
selected = i
j = i.next
while j:
if j.value < selected.value:
else:

```

Am I kinda on the right track, im still getting an error:

Traceback (most recent call last):
File "/Desktop/WingIDE.app/Contents/MacOS/src/debug/tserver/_sandbox.py", line 29, in <module>
File "/Desktop/WingIDE.app/Contents/MacOS/src/debug/tserver/_sandbox.py", line 21, in test_sort_integer
builtins.Assertionerror: error: linked list is not sorted

### #10 baavgai

• Dreaming Coder

Reputation: 6379
• Posts: 13,629
• Joined: 16-October 07

## Re: Sorting a double linked list

Posted 26 March 2013 - 04:46 AM

Not quite. Keep in mind, you're swapping "values" In a selection sort, there are two ways this is done; at the time or at the end of the inner loop, the latter being much more efficient.

Let's go back to your first sort:
```# we're going to sort a list a, for demonstration purposes.
# def sort(self):
def selSort(a):
# for each item
# for index in range(len(self)):
# note, a proper selection sort stops one from the end
for i in range(len(a)-1):
# look at what you're doing here
# you're holding a reference to index i
selected = i
# you actually want to loop from i+1 to the end
# for i in range(index,len(self)):
for j in range(i+1,len(a)):
# compare the selected value to the inner loop value
if a[j]<a[selected]:
# if the inner loop value is smaller
# save the INDEX
selected = j
# you leave the inner loop, it's swap time
# however, don't swap unless selected has changed from i
if not selected==i:
# we are swapping values
tempVal = a[i] # hold so we don't loose
a[i] = a[selected] # replace with selected value
a[selected] = tempVal # complete swap

```

Back to a linked list. There is no len, but using head and last node as your start and stop values, it's pretty much the same logic.

The next line in the code I gave would be:
```if j.value < selected.value:
selected = j # understand?  We're hold the "index."  The node with the value we want to swap with node i.

```

Hope this helps.

### #11 medaa

Reputation: 6
• Posts: 106
• Joined: 24-October 12

## Re: Sorting a double linked list

Posted 26 March 2013 - 09:32 AM

Okay Its slowly coming together.
Except I dont know what to do with this line or what its doing:

```while integer_list.get_size() > 0
```

```def sort(self):
def sort(self):
while i.next:
selected = i
j = i.next
while j:
if j.value < selected.value:
selected=j
```

How do you handle this piece of code, is it in the while j loop, or do I make a new loop?

### #12 baavgai

• Dreaming Coder

Reputation: 6379
• Posts: 13,629
• Joined: 16-October 07

## Re: Sorting a double linked list

Posted 26 March 2013 - 11:02 AM

You know, you still have to write the rest of that sort. You have swaps to make, nodes to move...

The integer_list.get_size() doesn't really make sense out of context. So, context:
```# this is essentially one pass of a bubble sort
# if you have to make a swap, you fail
prev_data = integer_list.pop(0) # get the first value
cur_data = integer_list.pop(0) # get the second value

# this is actually pretty sloppy, we're assuming more than two items
while integer_list.get_size() > 0: # basically, we're just testing if there are more items
# this check should to make sure that prev_data <= cur_data is true
# as a sort should have made it
# however, the = in >= is a bug and will fail if two values are the same, which should be valid
assert cur_data >= prev_data, 'error: linked list is not sorted'

# move forward
# the current is now the previous
prev_data = cur_data
# the newly popped value is current
cur_data = integer_list.pop(0)

```

Note, if the last value is out of order, this code will give you a pass.

### #13 medaa

Reputation: 6
• Posts: 106
• Joined: 24-October 12

## Re: Sorting a double linked list

Posted 26 March 2013 - 03:10 PM

So I talked to my prof and he helped me work out a code:

```from d_linked_node import d_linked_node
from item import item

def __init__(self):
self.__tail=None
self.__size=0

def search(self, item):
found = False
if current.getData() == item:
found= True
else:
current = current.getNext()
return found

def index(self, item):
found = False
index = 0
if current.getData() == item:
found= True
else:
current = current.getNext()
index = index + 1
index = -1
return index

if (self.__tail == None):
self.__size += 1
self.__tail = temp
else:
self.__size += 1

def remove(self, item):
if (self.search(item)):
inde = self.index(item)
self.__size -= 1
if (inde == 0):
self.__tail = None
else:
else:
for i in range(inde):
temp = temp.getNext()
a = temp.getPrevious()
a.setNext(temp.getNext())
if (a.getNext() == None):
self.__tail = a
else:
a.getNext().setPrevious(a)

def append(self, item):
if self.__size == 0:
else:
self.__size +=1
self.__tail.setNext(temp)
self.__tail = temp

def insert(self, pos, item):
for i in range(pos):
temp = temp.getNext()
if (pos == 0):
if (self.__size == 0):
self.__tail = temp_in
else:
temp_in.getNext().setPrevious(temp_in)
self.__size +=1
else:
if (temp == None):
temp_in.setPrevious(self.__tail)
self.__tail.setNext(temp_in)
self.__tail=temp_in
else:
temp_in.setNext(temp)
temp.getPrevious().setNext(temp_in)
temp_in.setPrevious(temp.getPrevious())
temp.setPrevious(temp_in)
self.__size +=1

def pop1(self):
temp = self.__tail
if (self.__size < 2):
self.__tail = None
self.__size = 0
else:
temp.getPrevious().setNext(None)
self.__tail = temp.getPrevious()
self.__size -= 1
return temp.getData()

def pop(self, pos):
self.__size -= 1
if (pos == 0):
self.__tail = None
else:
return temp.getData()
else:
for i in range(pos):
temp = temp.getNext()
a = temp.getPrevious()
a.setNext(temp.getNext())
if (a.getNext() == None):
self.__tail = a
else:
a.getNext().setPrevious(a)
return temp.getData()

def search_larger(self, item):
a = 0
while temp != None:
if (temp.getData() > item):
break
temp = temp.getNext()
a +=1
if(temp == None):
return -1
return a

def get_size(self):
return self.__size

def get_item(self, pos):
if (pos < 0):
if (pos < -self.__size):
raise Exception("pos doesn't exist")
temp = self.__tail
for i in range(pos,-1):
temp = temp.getPrevious()
return temp.getData()
else:
if (pos >= self.__size):
raise Exception("pos doesn't exist")
for i in range(0,pos):
temp = temp.getNext()
return temp.getData()

def select_least(self):
while current.getNext():
current=current.getNext()
if current.getData()<least.getData():
least=current
return least

def sort(self):
while self.__size > 0:
remaining = self.select_least()
sorted_list.append(remaining)
self.remove(remaining)
self.__tail = sorted_list.tail
self.__size = sorted_list.size
pass

def sort_by_attr(self, attr):
if attr=="Price":
while self.__size> 0:
remaining = self.select_least()
sorted_list.append(remaining)
self.remove(remaining)
self.__tail = sorted_list.tail
self.__size = sorted_list.size

elif attr=="Quantity":
while self.__size> 0:
remaining = self.select_least()
sorted_list.append(remaining)
self.remove(remaining)
self.__tail = sorted_list.tail
self.__size = sorted_list.size

def __str__(self):
pr = ""
while (temp != None):
pr = pr + str(temp.getData()) + " "
temp = temp.getNext()
pr = pr[:-1]
return pr

def test():

assert is_pass == True, "fail the test"

is_pass = (str(linked_list) == "Hello World")
assert is_pass == True, "fail the test"

assert is_pass == True, "fail the test"

assert is_pass == True, "fail the test"

assert is_pass == True, "fail the test"

assert is_pass == True, "fail the test"

assert is_pass == True, "fail the test"

assert is_pass == True, "fail the test"

assert is_pass == True, "fail the test"

for i in range(0, 10):
int_list2.remove(1)
int_list2.remove(3)
int_list2.remove(2)
int_list2.remove(0)
is_pass = (str(int_list2) == "9 8 7 6 5 4")
assert is_pass == True, "fail the test"

for i in range(11, 13):
int_list2.append(i)
is_pass = (str(int_list2) == "9 8 7 6 5 4 11 12")
assert is_pass == True, "fail the test"

for i in range(21, 23):
int_list2.insert(0,i)
is_pass = (str(int_list2) == "22 21 9 8 7 6 5 4 11 12")
assert is_pass == True, "fail the test"

is_pass = (int_list2.get_size() == 10)
assert is_pass == True, "fail the test"

is_pass = (int_list.get_size() == 0)
assert is_pass == True, "fail the test"

for i in range(0, 1000):
int_list.append(i)
correctOrder = True

is_pass = (int_list.get_size() == 1000)
assert is_pass == True, "fail the test"

for i in range(0, 200):
if int_list.pop1() != 999 - i:
correctOrder = False

is_pass = correctOrder
assert is_pass == True, "fail the test"

is_pass = (int_list.search_larger(200) == 201)
assert is_pass == True, "fail the test"

int_list.insert(7,801)

is_pass = (int_list.search_larger(800) == 7)
assert is_pass == True, "fail the test"

is_pass = (int_list.get_item(-1) == 799)
assert is_pass == True, "fail the test"

is_pass = (int_list.get_item(-4) == 796)
assert is_pass == True, "fail the test"

if is_pass == True:
print ("=========== Congratulations! Your have finished exercise 1! ============")

if __name__ == '__main__':
test()

```

I added a new function called select_least.

Does it make sense?

so my sort function has changed as you can see

### #14 baavgai

• Dreaming Coder

Reputation: 6379
• Posts: 13,629
• Joined: 16-October 07

## Re: Sorting a double linked list

Posted 27 March 2013 - 05:39 AM

It makes sense. It's kind of an inside out selection sort. But look at all the work you're doing! And there are a number of bugs, I'm afraid.

You're returning a node, which is good. You're appending the NODE to your new list, which is wrong. You're calling remove on the value ( which is still wrong, because it's a node. )

You should be able to remove the returned node from your list without calling anything. Though, a private removeNode method would be good.

Removing that node is complex. Swapping values wouldn't be. Inserting in order wouldn't be, either. You're making it harder on yourself, really.

The sort I offered only has a few more lines to complete it. Less code than that select_least... which has a bug in it, btw. It will crash on an empty list.

### #15 medaa

Reputation: 6
• Posts: 106
• Joined: 24-October 12

## Re: Sorting a double linked list

Posted 27 March 2013 - 09:45 AM

This was quite a hard exercise for me and my classmates so my prof decided to forget about it. But im so frustrated now because Ive tried a bunch of things and I cant figure it out. Is it possible if you can show me your completed code and explain to me how you got it one last time if you have time.