Introduction
Sort algorithms are most commonly used in today world.Almost in every program we do some kind of sorting.selection sort is one of most simplest algorithm in implementation. the selection sort algorithm starts by finding the minimum value in the array and moving it to the first position. This step is then repeated for the second lowest value, then the third, and so on until the array is sorted. some time in programming language we are not sure about size of data under these conditions we use linked list.In linked list we can implement selection as follow
- swapping values
- swapping pointer
swapping with values is very simple approach. we can swap values of nodes to arrange values,but swapping with pointer is not straight forward like swapping with values
Background
some time we have to deal with nodes of large size in linked list. swapping these node by value is very costly in term of memory .but in pointer we do swapping my pointer since pointer is only 4 bytes or 8 bytes depend of operating system we are using. which is much smaller then size of node which may be in kbs. this is reason why we use pointer swapping under these condition.
implementation
first we have to create a node factory which will make node for list class and some public method to access private members of node class
import inspect
import weakref
class Node:
'''
Node class for defining Nodes that contain data and address of next element
'''
def __init__(self):
'''constructor of Node Factory'''
self.__data=0
self.__Next=None
def getData(self):
return self.__data
def getNext(self):
return self.__Next
def setData(self,data):
self.__data=data
def setNext(self,Next):
self.__Next=Next
node class has two private data member pointer to next element and data element to hold data of node. we have some methods to access private member of class each method functionality is define with comment before method.
After creating node class we have to define a list class which is used to maintain linked list with private and public methods and memebers
class List:
'''List
this class will use Node class to create a link list
'''
def __init__(self):
'''constructor of list class'''
self.__headNode=Node()
self.__headNode.setNext(None)
self.Current=self.__headNode
self.lastCurrent=None
self.length=0
def headNode(self):
return self.__headNode
def lastCurrent(self):
return self.lastCurrent
def Add(self,object):
newNode=Node()
newNode.setData(object)
newNode.setNext(None)
self.length=self.length+1
if self.Current==self.headNode:
self.__headNode.setNext(newNode)
self.lastCurrent=self.Current
self.Current=newNode
else:
self.Current.setNext(newNode)
self.lastCurrent=self.Current
self.Current=newNode
def remove(self):
if self.length>0:
self.lastCurrent.setNext(self.Current.getNext())
self.Current.setNext(None)
del self.Current
self.Current=self.lastCurrent.getNext()
self.length=self.length-1
def delete(self,data):
self.lastCurrent=self.__headNode
self.Current=self.__headNode.getNext()
for i in range(0,self.length):
if self.Current.getData() == data:
print self.Current.getData()
self.lastCurrent.setNext(self.Current.getNext())
self.Current.setNext(None)
del self.Current
self.Current=self.lastCurrent.getNext()
self.length=self.length-1
break
self.lastCurrent=self.Current
self.Current=self.Current.getNext()
def __len__(self):
return self.length
def next(self):
if self.Current.getNext()!=None:
self.lastCurrent=self.Current
self.Current=self.Current.getNext()
return self.Current
else:
return None
def start(self):
self.lastCurrent=self.__headNode
self.Current=self.__headNode.getNext()
return self.Current
def nstart(self):
self.Current=self.__headNode
def get(self):
return self.Current.getData()
def isEmpty(self):
if self.length==0:
return True
def show(self):
self.Current=self.__headNode
while self.Current.getNext()!=None:
self.Current=self.Current.getNext()
print str(self.Current.getData()) ,
def last(self):
self.Current=self.__headNode
while self.Current.getNext()!=None:
self.Current=self.Current.getNext()
return self.Current
def __str__(self):
return str(self.Current.getData())
in list class we have privateheadnode
publiccurrent
,lastcurrent
,leght
properties.We have define public methods to access private members and for list operation like delete, remove add etc which do what their names means. delete will delete selected node where remove with delete current node.add method will add element to list and last element will return last element of list
Selection sort
after making linked list and providing user with its basic functionality we are now ready of implement selection sort for linked my swapping pointer.
- selection sort use two loop to iteration through the list
- outer loop select hold index/node to place in it correct position
- inner check a the node if it is not in right place swap it with node who is correct candidate for that place in liknked
- inner loop start from the next pointer of pointed by the selected node of outer loop
swapping a node to place its in right position can have different condition depending upon its position with with outer loop selected node
After one cycle through inner loop
after one complete iteration through inner we will have all values in corresponding pointer
- there are there condition of minimum value pointer
- case 1 outer loop node is minimum value pointer in this case will do no swap
- case 2 node next to selected node of outer loop is with minimum value
- case 3 minimum node is some where else in the linked list in this
case ii
- in this case we do not need node before the sorted node
- we do not need pointer to next node of current node
- set next of last current to next of current node
- set next of current node to next of next node
- set next of minimum to current node
- set current node to minimum nodde
case iii
- this case we need all four pointer we have created for swapping
- pre-pointer of current node
- next pointer of current node
- pre-pointer of sorted node
- pointer pointed my sorted node
- set next of lastcurrent to minimum node
- set next of minimum node to next of current node
- set node next of node before minimum to current node
- set next of current node to next of minimum node
import Node
def selectionSort(list):
'''selection sort algorithm
selection sort algorithm for linked list with swaping pointer values
'''
currentpre=list.headNode()
current=currentpre.getNext()
while current!=None:
minimum=current
nextprev=current;
beforesort=nextprev
nextinner=current.getNext()
while nextinner!=None:
if minimum.getData()>nextinner.getData():
beforesort=nextprev
minimum=nextinner
nextprev=nextinner
nextinner=nextinner.getNext()
if current.getNext()==minimum :
minimumNext=minimum.getNext()
currentpre.setNext(minimum)
minimum.setNext(current)
current.setNext(minimumNext)
current=minimum
elif current.getNext()!=minimum and current!=minimum:
currentNext=current.getNext()
minimumNext=minimum.getNext()
currentpre.setNext(minimum)
minimum.setNext(currentNext)
beforesort.setNext(current)
current.setNext(minimumNext)
current=minimum
currentpre=current
current=current.getNext()
list.show()
About Article
its is difficult to implement selection sort to my swapping pointer.but once you get idea how things are going you will find it simple.i did not remove testing code from my program just made them comment you can eliminate.my basic intention of about this article to provide beginner or those who had some experience but did not have idea about implementation of selection for linked list with swapping pointer .i try my best to give concept of swapping pointer in simplest way but no one perfect so be kind ;) ...