#
Sort

#======================================================================= # Author: Isai Damier # Title: Singly Linked List # Project: geekviewpoint # Package: datastructure # # Description: A LinkedList is a data structure that allows access # to a collection of data using pointers/references. While an # array can also be defined as above, LinkedLists and arrays differ # in how they are stored in memory and in the operations they # allow. Unlike an array that must be stored in a block of memory, # the nodes of a LinkedList can be stored anywhere because each # node has a reference to the node that succeeds it. Because the # nodes are stored so loosely, inserting nodes into a LinkedList # is easy; whereas in an array, all the succeeding elements must # be shifted. Of course, insertion also means changing the size of # the array, which means creating the entire array anew. # # Perhaps the greatest beauty of LinkedList is that it allows # accessing an entire sequence of nodes using only one variable: # a reference to the first node in the sequence. # # Countless operations can be performed on LinkedLists. Following # are a few, ranging from the common to the very interesting. #======================================================================= #===================================================================== # Time Complexity of Solution: # O(n*log n). # # Description: Sort the elements in this linked list in ascending # order. # # Technical Details: Sorting a LinkedList in place is very costly: # in the order of O(n^2# log(n)) with a good algorithm. # Therefore it makes sense to create an array from the list, # sort the array, and then empty the array into the list by # index. It's kind of like: unbutton a shirt; move the buttons # around; then button the shirt anew. (I think it's a good analogy.) #===================================================================== import collections class SinglyLinkedList( object ): def __init__( self ): self.head , self.tail = None, None def sort( self ) : if 2 > self.size(): return A = [0] * self.size() # unfasten the buttons (i.e. unbutton the shirt) x = 0 t = self.head while None != t: A[x] = t.data # list fills array x += 1 t = t.next self._mergesort( A, 0, len( A ) - 1 ) # refasten the buttons (i.e. button the shirt anew) x = 0 t = self.head while None != t: t.data = A[x] # array fills list x += 1 t = t.next def _mergesort( self, aList, first, last ): # break problem into smaller structurally identical pieces mid = ( first + last ) / 2 if first < last: self._mergesort( aList, first, mid ) self._mergesort( aList, mid + 1, last ) # merge solved pieces to get solution to original problem a, f, l = 0, first, mid + 1 tmp = [None] * ( last - first + 1 ) while f <= mid and l <= last: if aList[f] < aList[l] : tmp[a] = aList[f] f += 1 else: tmp[a] = aList[l] l += 1 a += 1 if f <= mid : tmp[a:] = aList[f:mid + 1] if l <= last: tmp[a:] = aList[l:last + 1] a = 0 while first <= last: aList[first] = tmp[a] first += 1 a += 1 class Node( object ): def __init__( self, data, next = None ): self.data = data self.next = next

import unittest from algorithms.SinglyLinkedList import SinglyLinkedList import random class Test( unittest.TestCase ): #===================================================================== # Test of sort method, of class SinglyLinkedList. #===================================================================== def testSort( self ): tape = [9, 4, 5, 2, 1, 12, 6, 7, 4, 8, 3, 0, 16, 19, 11] linkedList = SinglyLinkedList() for i in range( len( tape ) ): linkedList.addToTail( tape[i] ) self.assertEquals( tape, linkedList.toArray() ) tape.sort() self.assertNotEquals( tape, linkedList.toArray() ) linkedList.sort() self.assertEquals( tape, linkedList.toArray() )