Sort a unordered list class in python? solution?

Question

I have a Unordered list class like this :

from node import Node

class UnorderedList:
    """
    Unordered list
    """

    def __init__(self):
        self.head = None

    def is_empty(self):
        return self.head == None

    def __len__(self):
        """
        returns the length of the list O(1)
        """
        return self.size()


    def add(self, item):
        """
        Add item to list
        """
        temp = Node(item)
        temp.set_next(self.head)
        self.head = temp

    def size(self):
        """
        Return size of list
        """
        current = self.head
        count = 0
        while current != None:
            count = count + 1
            current = current.get_next()

        return count

    def set(self, index, newdata):
        """
        Set node-data in list at specific index
        """
        current = self.head
        previous = None
        for i in range(index):
            previous = current
            current = current.get_next()
        if current != None:
            temp = Node(newdata)
            temp.set_next(current)
            if previous is None:
                self.head = temp
            else:
                previous.set_next(temp)
        else:
            raise("index out of range")

    def getIndex(self, item):
        """get the index of an item, assume the first one (head pointing to) 
is 0"""
        index = 0
        current = self.head
        found = False
        while current != None:
            if current.get_data() == item:
                found = True
                break
            else:
                current = current.get_next()
                index += 1
        if not found:
            index = None
        return index


    def get(self, index):
        """
        Returns node data based on index
        """
        current = self.head
        for i in range(index):
            current = current.get_next()
        if current != None:
            return current.get_data()
        else:
            raise("index out of range")

    def search(self, item):
        """
        Returns True if item found, else return False
        """
        # Här ska du returnera en bool (True/False)
        # beroende på om 'item' finns i listan
        current = self.head
        found = False
        while current != None and not found:
            if current.get_data() == item:
                found = True
            else:
                current = current.get_next()
        return found

    def print_list(self):
        """
        Prints each item in list
        """
        # Traversera listan och gör en print() på varje element
        result = "["
        node = self.head
        if node != None:
            result += str(node.data)
            node = node.next
            while node:
                result += ", " + str(node.data)
                node = node.next
        result += "]"
        return result



    def remove(self, item):
        """
        Removes item from list
        """
        current = self.head
        previous = None
        found = False
        while not found:
            if current.get_data() == item:
                found = True
            else:
                previous = current
                current = current.get_next()
        if previous == None:
            self.head = current.get_next()
        else:
            previous.set_next(current.get_next())

I want to create a class list and then i can sort the list with my "bubblesort" function. My "bubblesort" function look like this :

def bubble_sort(items):
    """ Bubble sort """
    Size = items.size()
    for i in range(Size):
        for j in range(Size-1-i):
            if items.get(j) > items.get(j+1):
                tmps = items.get(j+1)
                items.set(j, items.get(j+1))
                items.set(j+1, tmps)
    return items

Now let us create a list :

// create the list
myListTwo = UnorderedList()

// Add the elements to the list
myListTwo.add(4)
myListTwo.add(50)
myListTwo.add(6)
myListTwo.add(10)
myListTwo.add(60)

//print the list :
print(myListTwo.print_list())
[60, 10, 6, 50, 4]

In this stage all work very well but the problem is when I want to sort the list with my bubble_sort function I got this result :

// bubble_sort my list 
sorte = bubble_sort(myListTwo)
//print the list
print(sorte.print_list())

[10, 10, 10, 10, 60, 10, 6, 50, 4]

Any idea?
Thanx/Georges

Answer 1

So, you have two issues to your implementation.

The first one is the inner code of bubble sort. Change this

tmps = items.get(j+1)

to

tmps = items.get(j)

See here for more about swapping Python Simple Swap Function

The second issue is the set method. You should remove this

temp = Node(newdata)
temp.set_next(current)
if previous is None:
    self.head = temp
else:
    previous.set_next(temp)

and you should write something like this

current.set_data(newData)

(I don't know how exactly you implemented the Node class)