문제

1. 6장 6.3 예제의 연결된리스트 클래스 LinkedList에 정렬 연산 sort()를 추가하라. 정렬 알고리즘으로는 7장 7.2 버블정렬을 이용하라.

class Node:                                 
    def __init__ (self, elem, link=None):   
        self.data = elem                    
        self.link = link```


class LinkedList:           
    def``` __init__```( self ):         
        self.head = None

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

    def size( self ):           
        node = self.head        
        count = 0
        while not node == None :
            node = node.link    
            count += 1          
        return count            

    def display( self, msg='LinkedList:'): 
        print(msg, end='')              
        node = self.head                
        while not node == None :        
            print(node.data, end=' ')   
            node = node.link            
        print()

    def getNode(self, pos) :             
        if pos < 0 : return None
        node = self.head;                
        while pos > 0 and node != None :
            node = node.link             
            pos -= 1                     
        return node 

    def getEntry(self, pos) :           
        node = self.getNode(pos)        
        if node == None : return None   
        else : return node.data         

    def replace(self, pos, elem) :      
        node = self.getNode(pos)        
        if node != None: node.data = elem   

    def find(self, data) :          
        node = self.head;
        while node is not None:     
            if node.data == data : return node  
            node = node.link
        return node         

    def insert(self, pos, elem) :
        before = self.getNode(pos-1)            
        if before == None :                     
            self.head = Node(elem, self.head)   
        else :                                  
            node = Node(elem, before.link)      
            before.link = node      


    def delete(self, pos) :
        before = self.getNode(pos-1)        
        if before == None :                 
            if self.head is not None :      
                self.head = self.head.link  
        elif before.link != None :          
            before.link = before.link.link  

s = LinkedList()

s.display('단순연결리스트로 구현한 리스트(초기상태):')

s.insert(0, 10);    s.insert(0, 20);     s.insert(1, 30)

s.insert(s.size(), 40); s.insert(2, 50)

s.display("단순연결리스트로 구현한 리스트(삽입x5): ")

s.replace(2, 90)

s.display("단순연결리스트로 구현한 리스트(교체x1): ")

s.delete(2);    s.delete(s.size() - 1); s.delete(0)

s.display("단순연결리스트로 구현한 리스트(삭제x3): ")

s.clear()
s.display("단순연결리스트로 구현한 리스트(정리후): ")          

 - **버블 연산**


def bubble_sort(A) :

    n = len(A)
    for i in range(n-1, 0, -1) :        
        bChanged = False
        for j in range (i) :            
            if (A[j]>A[j+1]) :          
                A[j], A[j+1] = A[j+1], A[j] 
                bChanged = True 

        if not bChanged: break;     
        printStep(A, n - i);