[자료 및 알고리즘] 7. 정렬과 탐색 (파이썬)

정렬이란? 

 

데이터를 순서대로 재배열하는 작업이다.

데이터들이 서로 비교할 수 있어야 되고, 비교할 수 있는 모든 속성들은 정렬의 기준이 된다.

오름차순과 내림차순이 있다.

 

정렬해야 하는 대상을 레코드라고 부른다.

그리고 대상에는 여러 속성들이 있을 텐데 이를 필드라고 한다. (ex. 번호,이름, 나이 등등)

이 필드 중에서 정렬의 기준이 되는 것을 키 혹은 정렬 키라고 한다.

 

비교 기반 정렬

 

대부분의 정렬 방법들로 레코드의 킷값을 비교하여 정리한다.

(기수와 카운팅 정렬은 분배에 의한 정렬이다)

 

내부 정렬과 외부 정렬

 

모든 데이터가 메모리에 올라와 정렬이 수행되는 것을 내부 정렬이라고 한다.

일부만을 올려 놓는다면 외부 정렬이라고 한다.

 

안정성에 따른 분류

 

안정성이란 동일한 킷값을 갖는 레코드가 여러 개 존재한다면,

정렬 후에도 상대적인 위치가 바뀌지 않는 성질이다.

(ex. 삽입 정렬, 버블 정렬, 병합 정렬)

 

제자리 정렬

 

입력 배열 이외에 추가적인 공간을 사용하지 않는 방법

(병합 정렬은 아니다)

 

선택 정렬 알고리즘 (selection sort)

 

가장 작은 요소를 꺼내서 순서대로 출력하는 정렬이다.

 

def selection_sort(A) :
    n = len(A)
    for i in range(n-1) :
        least = 1;
        for j in range(i+1, n) :
            if (A[j]<A[least]) :
                least = j
        A[i], A[least] = A[least], A[i];

최솟값이 선택되면 맨 앞의 요소와 교환하는 전략이다.

시간 복잡도는 O(n^2)이며, 안정성을 만족하지 않는다.

 

삽입 정렬 알고리즘 (insertion sort)

 

처음 하나를 잡고 다음부터 순서대로 끼워 넣는 거라고 생각하면 쉽다.

(카드 순서대로 정리하는 거랑 비슷하다고 생각하면 된다)

 

def insertion_sort(A) :
    n = len(A)
    for i in range(1,n) :
        key = A[i]
        j = i-1
        while j>=0 and A[j] > key :
            A[j+1] = A[j]
            j -= 1
        A[j+1] = key

 

시간 복잡도는 O(n^2)이고, 안정성도 충족한다.

만약 대부분의 레코드가 이미 정렬되어 있다면 효율적이다.

 

버블 정렬 알고리즘 (bubble sort)

 

왼쪽부터 오른쪽 갈 때까지 인접한 2개의 레코드를 비교하여

크기가 순서대로가 아니면 서로 교환하는 방식이다.

 

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

 

시간 복잡도는 O(n^2)이다. 안정성을 충족하지만 효율적이지는 않다.

 

정렬을 이용한 집합 (SortedArraySet)

 

#SetSorted.

class SetSorted:
    def __init__(self) :
        self.items=[]
        
    def size(self) :
        return len(self.items)
    
    def contains(self, item) : #이진탐색 이용
        if self.size() == 0 :
            return False
        
        low = 0
        high = self.size() - 1
        
        while(low <= high) :
            middle = (low + high) // 2
            
            if item == self.items[middle] :
                return True
            elif item > self.items[middle] :
                low=middle +1
            else :
                high=middle-1
        return False
    
    def insert(self, elem) :
        if self.contains(elem) :
            return
        
        self.items.append(elem)
        
        for i in range(self.size()-1, 0, -1) :
            if self.items[i-1] <=self.items[i]:
                break
            self.items[i-1], self.items[i] = self.items[i], self.items[i-1]
    
    def delete(self, elem) :
        self.items.remove(elem)
        
    def __eq__(self, setB) :
        if self.size() != setB.size() :
             return False
        
        for i in range(self.size()) :
            if self.items[i] != setB.items[i] :
                return False
        return True
                    
    def union(self, setB) :
        setC = SetSorted()
        i=0
        j=0
        
        while i < self.size() and j < setB.size() :
            a = self.items[i]
            b = setB.items[j]
            
            if a == b :
                setC.insert(a)
                i+=1
                j+=1
            
            elif a < b :
                setC.insert(a)
                i += 1
            
            else :
                setC.insert(b)
                j+=1
        
        while i < self.size() :
            setC.insert(self.items[i])
            i += 1
            
        while j < setB.size() :
            setC.insert(setB.items[j])
            j += 1
            
        return setC
        
    def intersect(self, setB) :
        setC = SetSorted()
        i=0
        j=0
         
        while i < self.size() and j < setB.size() :
            a = self.items[i]
            b = setB.items[j]
            
            if a == b :
                setC.insert(a)
                i+=1
                j+=1
            
            elif a < b :
                i += 1
            
            else :
                j+=1
        
        return setC

    def difference(self, setB) :
        setC = SetSorted()
        i=0
        j=0
         
        while i < self.size() and j < setB.size() :
            a = self.items[i]
            b = setB.items[j]
            
            if a == b :
                i+=1
                j+=1
            
            elif a < b :
                setC.insert(a)
                i += 1
            
            else :
                j+=1
        
        while i < self.size() :
            setC.insert(self.items[i])
            i += 1
            
        return setC

    def display(self, msg) :
        print(msg, self.items)

시간복잡도 계산

- insert(e) :

정렬되지 않은 리스트 : O(n)

정렬된 리스트 : O(n)

- __eq__(setB):

정렬되지 않은 리스트 : O(n^2)

정렬된 리스트 : O(n)

- union, intersect, difference

정렬되지 않은 리스트 : O(n^2)

정렬된 리스트 : O(n)

- contains(e) :

정렬되지 않은 리스트 : O(n) (순차 탐색)

정렬된 리스트 : O(logn) (이진 탐색)

 

탐색과 맵 구조

 

탐색은?

원하는 레코드를 레코드의 집합에서 찾는 작업

 

=> 탐색을 하는 집합을 테이블이라고 함

 

레코드가 서로 구별하여 인식할 수 있는 키를 탐색키라고 한다.

 

맵은 탐색을 위한 자료구조로 키와 값 쌍의 집합이다.

여기서 키 값 쌍을 보통 엔트리라고 부른다.

 

탐색 알고리즘

 

- 순차 탐색

테이블이 정렬되어 있지않다면 사용하는 방법이다.

def sequentioal_search(A, key, low, high) :
    for i in range(low, high+1) :
        if A[i] == key :
            return 1
    return -1

시간 복잡도는 O(n)이다.

 

- 이진 탐색

한 단계씩 검사할 때마다 검사 범위가 반으로 줄어드는 검사법이다.

// 순환 구조
def binary_search(A, key, low, high) :
    if(low>high) :
        return -1
        
    middle = (low + high) // 2
    
    if(key == A[middle]) :
        return middle
    elif(key < A[middle]) :
        return binary_search(A, key, low, middle -1)
    else :
        return binary_search(A, key, middle + 1, high)

// 반복 구조
def binary_search_iter(A, key, low, high) :
    while(low<=high) :
        middle = (low + high) // 2
        
        if key == A[middle] :
            return middle
        elif(key > A[middle]) :
            low = middle + 1
        else :
            high = middle - 1
    return -1

 

시간 복잡도는 O(logn)이다.

 

- 보간 탐색

탐색 값과 위치는 비례한다는 가정을 바탕으로 탐색 위치가 킷값이 있는 곳에

근접하도록 가중치를 주는 방법이다.

 

이 경우 middle만 수정하면 된다.

 

middle = int(low + (high-low) * (key-A[low].key) / (A[high].key - A[low]. key))

보간 탐색도 시간 복잡도는 O(logn)이다.

 

해싱이란?

 

킷값에 산술적인 연산을 적용하여 레코드가 저장되어야

할 위치를 직접 계산한는 것이다.

 

킷값을 이용해 함수를 돌려 레코드가 저장될 위치를 계산하는데

이때 이 함수를 해시 함수라고 한다.

 

해시 함수가 적용되어 계산된 위치에 저장된 테이블을 해시 테이블이라고 한다.

 

해시 함수가 적용되어 나온 값을 해시 주소라고 한다.

 

해시테이블은 M개의 버킷으로 이루어져 있는데, 쉽게 공간이라고 생각하면 된다.

버킷이 부족하면 서로다른 키가 해시 함수에 의해 같은 주소로 계산되는 상황이 있다.

이것을 충돌이라고 한다. 

 

충돌이 슬롯 수보다 많은 경우를 오버플로라고 한다.

 

해시 함수의 특징과 예시

 

1. 충돌이 적어야 한다.

2. 주소가 테이블에서 고르게 분포되어야 한다.

3. 계산이 빨라야 한다.

 

=> 보통 제산 함수를 사용

 

Mod(%)를 이용하는 편이다.

그 외에도 폴딩 함수, 중간 제곱 함수 등들이 있다.

 

오버 플로우 해결 방법

 

두 가지로 나뉜다.

 

-  개방 주소법

오버 플로우가 일어나면 해시 테이블의 다른 위치에 저장하는 방법이다.

예시로는 선형 조사법, 이차 조사법,  이중해싱법 등이 있다.

 

밑에 코드는 예시이다.

//선형 조사법
M=13
table = [None]*M

def hashFn(key) :
    return key % M

def insert(key) :
    i = hashFn(key)
    count = M
    while count > 0 :
        if table[i] == None :
            break
        i = (i + 1) % M
        count -= 1
        
    if table[i] == None or table[i] == -1 :
        table[i] = key
        
def search(key) :
    i = hashFn(key)
    count = M
    while count > 0 :
        if table[i] == None:
            return None
        if table[i] == key :
            return table[i]
        i = (i+1) % M
        count -= 1
        
    return None

def delete(key) :
    i = hashFn(key)
    count = M
    while count > 0 :
        if table[i] == key :
            table[i] = -1
            return
        if table[i] == None :
            return
        i = (i+1) % M
        count -= 1

 

이중 조사법 :

원래 위치에다가 제곱수를 더하고 해시 함수를 돌리는 과정이다.

군집화를 1차는 막을 수 있지만 2차는 확실하지가 않다.

군집화는 레코드가 한쪽에만 몰리는 과정을 말한다.

 

이중 해싱법 : 

재해싱이라고도 한다. 원래의 해시 함수를 적용한 다음에 다른 해시 함수를 적용시키는 과정이다.

 

-  체이닝

 

하나의 버킷에 여러 개의 코드를 저장하는 방법이다.

def insert(key) :
    k - hashFn(key)
    n - Node(key)
    n.link = table[k]
    table[k] = n

def search(key) :
    k = hashFn(key)
    n = table
    while n is not None :
        if n.data == key :
            return None
            
def delete(key) :
    k = hashFn(key)
    n = table
    before = None
    while n is not None :
        if n.data == key :
            if before == None :
                table[k] = n.link
            else :
                before.link = n.link
            return
        before = n
        n = n.link

 

적재 비율이란?

저장된 항목의 개수 / 해시테이블의 버킷 개수를 의미한다.

 

위 해싱의 시간복잡도를 알아보면 최선의 경우 O(1)을, 최악의 경우에는 O(n)이 걸린다.