Sorting a double linked list

  • (2 Pages)
  • +
  • 1
  • 2

17 Replies - 2235 Views - Last Post: 29 March 2013 - 01:50 AM Rate Topic: -----

#16 leogrr  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 6
  • Joined: 12-March 13

Re: Sorting a double linked list

Posted 28 March 2013 - 07:00 AM

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


This function doesnt even make sense, and second whats "next" you need to be more clear.
Was This Post Helpful? 0
  • +
  • -

#17 atraub  Icon User is offline

  • Pythoneer
  • member icon

Reputation: 759
  • View blog
  • Posts: 2,010
  • Joined: 23-December 08

Re: Sorting a double linked list

Posted 29 March 2013 - 01:02 AM

the "next" does make perfect sense if you know what a node in a linked list is. What part are you having trouble understanding? You need to be more clear.

Snarkiness aside, the sort doesn't work, but that's already been discussed.

This post has been edited by atraub: 29 March 2013 - 02:06 AM

Was This Post Helpful? 0
  • +
  • -

#18 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5832
  • View blog
  • Posts: 12,684
  • Joined: 16-October 07

Re: Sorting a double linked list

Posted 29 March 2013 - 01:50 AM

I offered the partial selection sort example. It does require you have a basic understanding of linked list conventions.

I wanted to give this a few says to cool, let the OP turn in their work.

For completeness, here's a full example.
import random

class LinkedList(object):
	class Node(object):
		def __init__(self, value, next=None): 
			self.value, self.next = value, next
	def __init__(self): 
		self.head = None
	def add(self, value):
		self.head = self.head = LinkedList.Node(value, self.head)
	def __iter__(self):
		node = self.head
		while node:
			yield node.value
			node = node.next

	# selection sort on linked list
	def sort(self):
		if self.head and self.head.next:
			i = self.head
			while i.next:
				selected = i
				j = i.next
				while j:
					if j.value < selected.value:
						selected = j
					j = j.next
				if not selected==i:
					i.value, selected.value = selected.value, i.value
				i = i.next

def isSorted(values):
	last = None
	for i in values:
		if last and i<last:
			return False
		last = i
	return True

def test():
	ll = LinkedList()
	for i in range(20):
		ll.add(random.randint(1,100))
	print(' '.join([str(i) for i in ll]))
	print('sorted: ' + str(isSorted(ll)))
	ll.sort()
	print(' '.join([str(i) for i in ll]))
	print('sorted: ' + str(isSorted(ll)))


test()



A basic linked list stack implementation. The sort looks a little odd because, well, it's a selection sort on nodes.

This post has been edited by baavgai: 29 March 2013 - 01:56 AM
Reason for edit:: bug in isSorted

Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2