[Python 자료구조 #정렬과 탐색1] 선택정렬, 삽입정렬, 버블정렬, 정렬 응용한 집합

* 정렬(sorting)

• 오름차순( ascending order)
• 내림차순(descending order)
• 레코드(record) : 정렬시켜야 될 대상
• 필드(field) 레코드는 여러 개의 필드로 이루어지고, 필드는 속성들이다.
• 키(key) 또는 정렬 키(sort key) : 정렬의 기준이 되는 필드
• 정렬 : 레코드들을 키(key)의 순서로 재배열하는 것

 

* 정렬 장소에 따른 분류

• 내부(internal)정렬 : 모든 데이터가 메인 메모리에 올라와 있는 정렬
• 외부(external)정렬 : 외부 기억 장치에 대부분의 데이터가 있고 일부만 메모리에 올려 정렬하는 방법으로 대용량 자료를 정렬하기 위해 사용한다.

 

* 구현 복잡도와 알고리즘 효율성에 따른 분류

• 단순하지만 비효율적인 방법 : 삽입정렬, 선택정렬, 버블 정렬 등
• 복잡하지만 효율적인 방법 : 퀵 정렬, 힙 정렬, 병합 정렬, 기수 정렬 등

 

* 안정성에 따른 분류

• 안정성(stability)이란 입력 데이터에 동일한 킷값을 갖는 레코드가 여러 개 존재할 경우, 정렬 후에도 이들의 상대적인 위치가 바뀌지 않는 것. 안정성을 충족하는 정렬에는 삽입정렬, 버블정렬, 병합정렬 등이 있다.

 

* 선택 정렬(selection sort)

• 리스트에서 가장 작은 숫자를 선택해서 앞쪽으로 옮기는 방법. 오른쪽 리스트에서 가장 작은 숫자를 선택하여 왼쪽 리스트의 맨 뒤로 이동하는 작업
• 오른쪽 리스트 : 아직 정렬되지 않은 리스트
• 왼쪽 리스트 : 정렬 완료된 리스트
• 실제로 두 개의 배열을 사용하진 않는다. 정렬이 안 된 리스트에서 최솟값이 선택되면 이 값을 배열의 첫 번째 요소와 교환하면 되기 때문이다.
• 선택 정렬은 입력 배열 이외에 추가적인 배열을 사용하지 않는다. 이러한 정렬 방법을 제자리 정렬(in-place sorting)라고 한다.
• 시간 복잡도 O(n^2)이고 알고리즘이 간단하고, 입력 자료의 구성과 상관없이 자료 이동 횟수가 결정된다는 장점있음.

def selection_sort(A):
    n = len(A)  # 리스트 n의 길이
    for i in range(n - 1):  # i = 0 ~ n-2
        least = i  # 최솟값의 인덱스
        for j in range(i + 1, n):  # j = i+1 ~ n-1
            if A[j] < A[least]:
                least = j	#최솟값의 인덱스를 찾음
        A[i], A[least] = A[least], A[i]	
        printStep(A, i + 1)


def printStep(arr, val):
    print("  Step %2d = " % val, end="")
    print(arr)

data = [5, 3, 8, 4, 9, 1, 6, 2, 7]
print("Original  :", data)
selection_sort(data)
print("Selection :", data)
-----------------------------------------------
Original  : [5, 3, 8, 4, 9, 1, 6, 2, 7]
  Step  1 = [1, 3, 8, 4, 9, 5, 6, 2, 7]
  Step  2 = [1, 2, 8, 4, 9, 5, 6, 3, 7]
  Step  3 = [1, 2, 3, 4, 9, 5, 6, 8, 7]
  Step  4 = [1, 2, 3, 4, 9, 5, 6, 8, 7]
  Step  5 = [1, 2, 3, 4, 5, 9, 6, 8, 7]
  Step  6 = [1, 2, 3, 4, 5, 6, 9, 8, 7]
  Step  7 = [1, 2, 3, 4, 5, 6, 7, 8, 9]
  Step  8 = [1, 2, 3, 4, 5, 6, 7, 8, 9]
Selection : [1, 2, 3, 4, 5, 6, 7, 8, 9]

 

* 삽입 정렬(insertion sort)

• 삽입 정렬의 복잡도는 입력 자료의 구성에 따라서 달라진다. 이미 정렬되어 있는 경우는 가장 빠르다 O(n)
• 최악의 경우는 입력 자료가 역으로 정렬된 경우이다.O(n^2)
• 대부분의 레코드가 이미 정렬되어 있는 경우 효율적으로 사용될 수 있다.
• 삽입된 카드로 인해 항목들이 뒤로 이동됨.

def insertion_sort(A):
    n = len(A)
    for i in range(1, n):  # 위부 루프 i = 1 ~ n-1
        key = A[i]  # key는 삽입 대상
        j = i - 1
        while j >= 0 and A[j] > key: # 내부 루프
            A[j + 1] = A[j] # 항목들을 뒤로 한 칸씩 이동
            j -= 1
        A[j + 1] = key  # 항목 삽입
        printStep(A, i)


def printStep(arr, val):
    print("  Step %2d = " % val, end="")
    print(arr)

data = [5, 3, 8, 4, 9, 1, 6, 2, 7]
print("Original  :", data)
insertion_sort(data)
print("insertion :", data)
---------------------------------------
Original  : [5, 3, 8, 4, 9, 1, 6, 2, 7]
  Step  1 = [3, 5, 8, 4, 9, 1, 6, 2, 7]
  Step  2 = [3, 5, 8, 4, 9, 1, 6, 2, 7]
  Step  3 = [3, 4, 5, 8, 9, 1, 6, 2, 7]
  Step  4 = [3, 4, 5, 8, 9, 1, 6, 2, 7]
  Step  5 = [1, 3, 4, 5, 8, 9, 6, 2, 7]
  Step  6 = [1, 3, 4, 5, 6, 8, 9, 2, 7]
  Step  7 = [1, 2, 3, 4, 5, 6, 8, 9, 7]
  Step  8 = [1, 2, 3, 4, 5, 6, 7, 8, 9]
insertion : [1, 2, 3, 4, 5, 6, 7, 8, 9]

 

* 버블정렬(bubble sort)

• 인접한 2개의 레코드를 비교하여 크기가 순서대로가 아니면 서로 교환하는 방법. 비교-교환 과정이 한번 완료되면( 한 번의 스캔) 가장 큰 레코드가 리스트의 오른쪽 끝으로 이동된다. 

 

def bubble_sort(A):
    n = len(A)
    for i in range(n - 1, 0, -1):   # 외부 루프 : n-1 ~ 1
        bChanged = False    
        for j in range(i):  # 내부 루프 : 0 ~ i-1
            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) # 중간 과정 출력용 문장


def printStep(arr, val):
    print("  Scan %2d 완료 = " % val, end="")
    print(arr)

data = [5, 3, 8, 4, 9, 1, 6, 2, 7]
print("Original  :", data)
bubble_sort(data)
print("insertion :", data)
--------------------------------------------
Original  : [5, 3, 8, 4, 9, 1, 6, 2, 7]     
  Scan  1 완료 = [3, 5, 4, 8, 1, 6, 2, 7, 9]
  Scan  2 완료 = [3, 4, 5, 1, 6, 2, 7, 8, 9]
  Scan  3 완료 = [3, 4, 1, 5, 2, 6, 7, 8, 9]
  Scan  4 완료 = [3, 1, 4, 2, 5, 6, 7, 8, 9]
  Scan  5 완료 = [1, 3, 2, 4, 5, 6, 7, 8, 9]
  Scan  6 완료 = [1, 2, 3, 4, 5, 6, 7, 8, 9]
insertion : [1, 2, 3, 4, 5, 6, 7, 8, 9]

 

* 정렬 응용 : 집합 다시보기

• 집합의 원소들이 정렬되어 있으면 집합의 비교나 합집합, 차집합, 교집합 등을 훨씬 효율적으로 구현할 수 있다. 그래서 정렬을 이용해서 집합의 원소들을 항상 정렬된 순으로 저장하려고 한다.
• 집합의 삽입연산 등의 ADT(추상 데이터 타입)을 변경해야한다.

 

class Set:                      

    def __init__( self ):      

        self.items = []        

    def size( self ):          

        return len(self.items)  

    def display(self, msg):    

        print(msg, self.items)  

#    def contains(self, item) :

#       return item in self.items

    def contains(self, item) :

        for i in range(len(self.items)):

            if self.items[i] == item :  

                return True

        return False        

    def insert(self, elem) :

        if elem not in self.items :

           self.items.append(elem)

    def delete(self, elem) :

        if elem in self.items :

           self.items.remove(elem)

    def union( self, setB ):            

        setC = Set()                    

        setC.items = list(self.items)  

        for elem in setB.items :        

            if elem not in self.items :

                setC.items.append(elem)

        return setC                    

    def intersect( self, setB ):    

        setC = Set()

        for elem in setB.items :    

            if elem in self.items :

                setC.items.append(elem)

        return setC

    def difference( self, setB ):      

        setC = Set()

        for elem in self.items:        

            if elem not in setB.items:  

                setC.items.append(elem)

        return setC

 

* Set_insert : 삽입 연산

    def insert(self, elem) :               # 삽입연산 
        if elem in self.items : return      # 이미 있는 경우 
        for idx in range(len(self.items)) : 
            if elem < self.items[idx] :     # 삽입할 위치 idx를 찾음
                self.items.insert(idx, elem)
                return
        self.items.append(elem)

 

* Set_ _eq_ _() : 비교 연산

    def __eq__( self, setB ):       	# 비교 연산
        if self.size() != setB.size() :	
            return False
        for idx in range(len(self.items)): 			
            if self.items[idx] != setB.items[idx] :	
                return False
        return True

정렬되지 않은 상태에서 두 집합이 같은지 비교하려면 O(n^2) 알고리즘이 된다. 배열이 정렬되었다면 원소의 개수를 확인하고 순서대로 원소를 비교하면 된다. 정렬되어 있으면 시간 복잡도는 O(n)이 된다.

_ _eq_ _() 파이썬에서 미리 정의된 특별한 메소드로 ==연산자에 대한 연산자 중복 함수이다. Set 클래스에서 이 메소드를 구현하면 두 Set 객체 A와 B를 A==B와 같이 ==연산자를 이용해 비교할 수 있다. 산술 연산자(+,-,/,*)나 비교 연산자 등을 포함한 다양한 연산자 중복 메소드가 정의되어 있는데, 이들은 모두 _ _로 시작하여 _ _로 끝나는 이름을 갖는다.

 

* Set_insert : 삽입 연산

• 두 집합의 원소들이 크기순으로 정렬되어 있으므로, 가장 작은 원소들부터 비교하여 더 작은 원소를 새로운 집합에 넣고 그 집합의 인덱스를 증가시킨다.
• 만약 두 집합의 현재 원소가 같으면 하나만을 새 집합에 넣으면 된다. 인덱스는 모두 증가시킨다.
• 한쪽 집합이 모두 처리되면 나머지 집합의 남은 모든 원소를 순서대로 새 집합에 넣는다.

    def union( self, setB ):        	
        newSet = Set()					# 반환할 합집합
        a = 0							# 집합 self의 원소에 대한 인덱스
        b = 0							# 집합 setB의 원소에 대한 인덱스
        while a < len( self.items ) and b < len( setB.items ) :
            valueA = self.items[a]		# 집합 self의 현재 원소 
            valueB = setB.items[b]		# 집합 setB의 현재 원소
            if valueA < valueB :		
                newSet.items.append( valueA )	
                a += 1					
            elif valueA > valueB :		
                newSet.items.append( valueB )	
                b += 1			
            else : 				
                newSet.items.append( valueA )	
                a += 1					
                b += 1
        while a < len( self.items ):	
             newSet.items.append( self.items[a] )
             a += 1
        while b < len( setB.items) :	
             newSet.items.append( setB.items[b] )
             b += 1
        return newSet