selection sort with swapping pointers in linked list

• Download selectionsort.rar - 2.3 KB
• Download selectionsort.zip - 2.3 KB

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   #initializing private variable
        self.__Next=None    #private variable for holding address of next node

    #getData function function will return value of current node
    def getData(self):
        return self.__data

    #getNext function function will return address of current node
    def getNext(self):
        return self.__Next

    #setData function function will set value of current node
    def setData(self,data):
        self.__data=data

    #setNext function function will set address field of current node
    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()          #defining private head node which i indicator of start piont
        self.__headNode.setNext(None)   #set next to null
        self.Current=self.__headNode  #set current position to start of list
        self.lastCurrent=None
        self.length=0


    def headNode(self):
        return self.__headNode
    def lastCurrent(self):
        return self.lastCurrent

    #function for adding element to the list
    def Add(self,object):   #this function will take one argument which is data for insertion
        newNode=Node()          #create new for holding new data
        newNode.setData(object) #insert data to newly created node
        newNode.setNext(None)   #set next pointer to null
        self.length=self.length+1
        #if current is pionting to head that show is it is the first element in list
        if self.Current==self.headNode:
            self.__headNode.setNext(newNode)#set next of field of headnode to newnode
            self.lastCurrent=self.Current   #moving last current to current position
            self.Current=newNode              #move current pointer to to newnode

        #if current is not pointing to headnode list is not empty
        else:
            self.Current.setNext(newNode) #set the next field of current to new object
            self.lastCurrent=self.Current
            self.Current=newNode          #move the current field to new node



    #remove function will remove current element of list list
    def remove(self):
        if self.length>0:
            self.lastCurrent.setNext(self.Current.getNext())
            self.Current.setNext(None)
            del self.Current
           # print self.__Current.getData()
            self.Current=self.lastCurrent.getNext()
            self.length=self.length-1

    #Deleting a node of a give value
    def delete(self,data):
         #   print "here"
            self.lastCurrent=self.__headNode
            self.Current=self.__headNode.getNext()
          #  print "here"
            for i in range(0,self.length):
               # print self.__Current.getData()
                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()


    #this function will print length of link list
    def __len__(self):
         return self.length



    #move current position to next element
    def next(self):
        if self.Current.getNext()!=None:
            self.lastCurrent=self.Current
            self.Current=self.Current.getNext()
            return self.Current
        else:
            return None



    #moving current position to start
    def start(self):
        self.lastCurrent=self.__headNode
        self.Current=self.__headNode.getNext()
        return self.Current
    def nstart(self):
        self.Current=self.__headNode

    #this function is used to return current node data
    def get(self):
        return self.Current.getData()

    #isEmpty function is use to check weither function is empty or not
    def isEmpty(self):
        if self.length==0:
            return True

    #function for displaying list
    def show(self):
        self.Current=self.__headNode  #move current pointer to starting position
        while self.Current.getNext()!=None:   #continue reading until the next field become empty
            self.Current=self.Current.getNext() #move current pionter to next element
            print str(self.Current.getData()) ,#print data of current current element
    #geting last index of linked list
    def last(self):
        self.Current=self.__headNode  #move current pointer to starting position
         while self.Current.getNext()!=None:   #continue reading until the next field become empty
           # if self.__Current.getNext()!=None:
                self.Current=self.Current.getNext()
            #else:
        return self.Current



    def __str__(self):
        return str(self.Current.getData())

in list class we have privateheadnodepubliccurrent,lastcurrent,leghtproperties.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
  1. pre-pointer of current node
  2. next pointer of current node
  3. pre-pointer of sorted node
  4. pointer pointed my sorted node
     1. set next of lastcurrent to minimum node
     2. set next of minimum node to next of current node
     3. set node next of node before minimum to current node
     4. 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() #node before current node
     current=currentpre.getNext()   #current pionter of linked list

     #outer loop for selection sort
     while current!=None:
        minimum=current       #selecting first node as minimum values node
        nextprev=current;       #previous node for nextinner pointer
        beforesort=nextprev     #previous not for the pointer with minimum value
        nextinner=current.getNext()     #node for next inner loop of selection sort

        #inner loop of  selection sort
        while nextinner!=None:

            if minimum.getData()>nextinner.getData():   #finding minimum value pointer
                beforesort=nextprev                     #setting values of pointer to minimum value pointer
                minimum=nextinner
            nextprev=nextinner
            nextinner=nextinner.getNext()


        #after the inner loop completion of cycle we will have all values in correnponding pointer
        #there are there condition of minimum value pointer
        #(i) current pointer is minimum value pointer in this case will do no swap
        #(ii) pointer pointed to minimum value pointer in this case if will be executed
        #(iii) pointer is some where else in the linked list in this case elif will be executed

        #case ii
        #pionter are next to each other in this we did not beforesort pointer because that is current pointer
        # and we did not next next pointer of current node here is code
        if current.getNext()==minimum :
            minimumNext=minimum.getNext()   #pointer to next node pointed my minimum node
            currentpre.setNext(minimum)     #nex pointer of pointer before the current node is to minimum node
            minimum.setNext(current)        #set minimum next pointer of minimum node to current
            current.setNext(minimumNext)    #set next pointer of current to next pointer pointed my my minimum pointer
            current=minimum                 #set current to minimum

        #case iii
        #in this case we need all four pointer we have created for swapping
        #i.e i) pre-pointer of current node  ii)nex pointer of current node
        #    iii)pre-pointer of sorted node    iv) pointer pointed my sorted node
        #here is code for swapping
        elif current.getNext()!=minimum and current!=minimum:
                 currentNext=current.getNext()            #pointer pointed my the current node
                 minimumNext=minimum.getNext()           #pointer to next node pointed my minimum node
                 currentpre.setNext(minimum)               #set pre-current to minimum pointer
                 minimum.setNext(currentNext)             #set next pointer of minimum node to currentNext pointer
                 beforesort.setNext(current)                #setting pre pointer of sorted node to current pointer
                 current.setNext(minimumNext)               #current pointer next pointer set to next of minimumNext
                 current=minimum                             #set current to minimum
        currentpre=current              #set pre-current to current
        current=current.getNext()       #set current to current ->next
     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 ;) ...