Python의 링크 된 목록에 SelectionSort와 InsertionSort를 어떻게 구현합니까?

Question

Linked List 클래스를 구현했으며 일반 목록에서 작동하는 selectionSort 및 insertionSort 함수를 만들었습니다. selectionSort 및 insertionSort를 가져와 링크 된 목록에서 작업 할 필요가 있지만, 정직한 경우 어디서부터 시작해야할지 모르겠습니다.

class Node: 
    def __init__(self, initdata): 
     self.data = initdata 
     self.next = None 

    def getData(self): 
     return self.data 

    def getNext(self): 
     return self.next 

    def setData(self,newdata): 
     self.data = newdata 

    def setNext(self, newnext): 
     self.next = newnext 

class unorderedList: 
    def __init__(self): 
     self.head = None 

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

    def add(self, item): 
     temp = Node(item) 
     temp.setNext(self.head) 
     self.head = temp 

    def length(self): 
     current = self.head 
     count = 0 
     while current != None: 
      count = count + 1 
      current = current.getNext() 

     return count 

    def search(self, item): 
     current = self.head 
     found = False 
     while current != None and not found: 
      if current.getData() == item: 
       found = True 
      else: 
       current = current.getNext() 

     return found 

    def remove(self, item): 
     current = self.head 
     previous = None 
     found = False 
     while not found: 
      if current.getData() == item: 
       found = True 
      else: 
       previous = current 
       current = current.getNext() 

     if previous == None: 
      self.head = current.getNext() 
     else: 
      previous.setNext(current.getNext() 

여기 선택 정렬과 삽입 정렬에 대한 내 코드입니다 :

여기 내 연결리스트 클래스입니다. 정규리스트에서는 정상적으로 작동하지만, 링크드리스트 (정렬되지 않은리스트)에서 작업 할 수있는 곳을 알아내는 데 어려움을 겪고 있습니다.

def selectionSort(alist): 
    for fillslot in range(len(alist)-1,0,-1): 
      positionOfMax = 0 
      for location in range(1,fillslot+1): 
        if alist[location]>alist[positionOfMax]: 
          positionOfMax = location 

      temp = alist[fillslot] 
      alist[fillslot] = alist[positionOfMax] 
      alist[positionOfMax] = temp 

def insertionSort(alist): 
    for index in range(1,len(alist)): 

      currentvalue = alist[index] 
      position = index 

      while position>0 and alist[position-1]>currentvalue: 
        alist[position] = alist[position-1] 
        position = position-1 

      alist[position] = currentvalue 

모든 의견이나 제안을 보내 주시면 감사하겠습니다.

Answer 1

insertionSort을 구현하려고 시도했지만 코드를 읽을 수 있습니다. SelectionSort이 유사해야하며 구현해야합니다.

def insertionSort(h): 
    if h == None: 
     return None 
    #Make the first node the start of the sorted list. 
    sortedList= h 
    h=h.next 
    sortedList.next= None 
    while h != None: 
     curr= h 
     h=h.next 
     if curr.data<sortedList.data: 
      #Advance the nodes 
      curr.next= sortedList 
      sortedList= curr 
     else: 
      #Search list for correct position of current. 
      search= sortedList 
      while search.next!= None and curr.data > search.next.data: 
       search= search.next 
      #current goes after search. 
      curr.next= search.next 
      search.next= curr 
    return sortedList 

def printList(d): 
    s='' 
    while d: 
     s+=str(d.data)+"->" 
     d=d.next 
    print s[:-2] 

l= unorderedList() 
l.add(10) 
l.add(12) 
l.add(1) 
l.add(4) 
h= l.head 
printList(h) 

result= insertionSort(l.head) 
d= result 
printList(d) 

출력 :

4->1->12->10 
1->4->10->12