Sorting (4)

Chapter 7.1-7.7

• Time Complexity
• Insertion Sort
• Selection Sort
• Merge Sort
• Quick Sort
• Heap Sort

1. 예제 14 풀이

• 합병정렬 알고리즘에서 레코드의 저장 횟수를 기준으로 할 때 시간복잡도는 대략 T(n) = 2n log n이 됨을 증명하기
• 알고리즘 2.2
  문제) n개의 원소를 비내림차순으로 정렬
  입력) 양의 정수 n, 배열 S (인덱스는 1부터 n까지)
  출력) 원소를 비내림차순으로 정렬한 배열 S

void mergesort ( int n, keytype S[] ) {
	if ( n > 1 ) {
    	const int h = └n/2┘, m = n - h;
        keytype U[1...h], V[1...m];
        copy S[1] through S[h] to U[1] through U[h];
        copy S[h+1] through S[n] to V[1] through V[m];
        mergesort(h,U);
        mergesort(m,V);
        merge(h,m,U,V,S);
    }
}

=> mergesort 함수는 n을 반으로 나누고, 이를 재귀적으로 정렬한다. n의 크기가 1이 될 때까지 계속해서 반으로 나누기 때문에 재귀 호출의 깊이는 log n이다. merge 함수는 두 개의 정렬된 배열을 합쳐서 하나의 정렬된 배열을 만든다. 이때 레코드를 임시 배열에 복사하고, 다시 원래 배열에 복사하는 두 번의 복사 작업이 필요하므로 레코드의 저장 횟수는 최대 2n번이 된다. mergesort 함수의 시간복잡도는 재귀 호출 횟수인 log n과 merge 함수의 레코드 저장 횟수인 2n을 곱하여 2n log n이 된다. 따라서 T(n) = 2n log n으로 표현할 수 있다.

• 알고리즘 2.4
  문제) n개의 원소를 비내림차순으로 정렬
  입력) 양의 정수 n, 배열 S (인덱스는 1부터 n까지)
  출력) 원소를 비내림차순으로 정렬한 배열 S

void mergesort2 ( index low, index high ) {
	index mid;
    if ( low < high ) {
    	mid = └(low + high)/2┘;
        mergesort2(low,mid);
        mergesort2(mid+1,high);
        merge2(low,mid,high);
    }
}

=> mergesort2 함수는 배열의 첫 인덱스와 끝 인덱스를 인자로 받는다. 배열을 반으로 나누고, 재귀적으로 호출하여 정렬한다. 재귀 호출의 깊이는 log n이 되며, 각 단계에서 merge2 함수가 호출된다. merge2 함수는 두 개의 정렬된 배열을 합쳐서 하나의 정렬된 배열을 만든다. 이때 레코드를 임시 배열에 복사하고, 다시 원래 배열에 복사하는 두 번의 복사 작업이 필요하므로 레코드의 저장 횟수는 최대 2n번이 된다. 따라서 mergesort2 함수의 시간복잡도는 재귀 호출 횟수인 log n과 merge2 함수의 레코드 저장 횟수인 2n을 곱하여 2n log n이 된다. 따라서 T(n) = 2n log n으로 표현할 수 있다.

1. Bi-Directional Search

• Procedure
  • 출발 노드와 목적지 노드로부터 각각 BFS(Breadth First Search)를 수행
  • 두 탐색 경로가 만날 때까지 계속해서 탐색
  • 만약 두 경로가 만난다면 경로를 생성
    => 빠른 속도로 최단 경로 탐색 가능
• The source vertex : 's', the target vertex : 't'

class AdjacentNode:
    def __init__(self, vertex, weight=0):
        self.vertex = vertex
        self.next = None
        self.weight = weight

class BidirectionalSearch:
    def __init__(self, vertices):
        self.vertices = vertices
        self.graph = defaultdict(list)

    def add_edge(self, u, v, weight):
        self.graph[u].append((v, weight))
        self.graph[v].append((u, weight))

    def is_intersecting(self, s_visited, t_visited):
        for i in range(len(self.vertices)):
            if s_visited[i] and t_visited[i]:
                return i
        return None

    def bfs(self, queue, visited, parent):
      if not queue:
          return None
      current_node = queue.popleft()
      for neighbor, weight in self.graph[current_node]:
          if not visited.get(neighbor, False):
              visited[neighbor] = True
              parent[neighbor] = current_node
              queue.append(neighbor)
      return current_node

def generate_path(self, current_node, start_parent, end_parent):
        path = []
        while current_node is not None:
            path.append(current_node)
            current_node = start_parent[current_node]
        path = path[::-1]
        while current_node is not None:
            path.append(current_node)
            current_node = end_parent[current_node]
        return path

def bidirectional_search(self, source, target):
    s = self.vertices.index(source)
    t = self.vertices.index(target)
    queue_s = deque()
    queue_t = deque()
    s_visited = {source: True}
    t_visited = {target: True}
    s_parent = {source: None}
    t_parent = {target: None}
    queue_s.append(source)
    queue_t.append(target)
    while queue_s and queue_t:
        current_node_s = self.bfs(queue_s, s_visited, s_parent)
        current_node_t = self.bfs(queue_t, t_visited, t_parent)
        if current_node_s is not None:
            if current_node_s in t_visited:
                return self.generate_path(current_node_s, s_parent, t_parent)
        if current_node_t is not None:
            if current_node_t in s_visited:
                return self.generate_path(current_node_t, s_parent, t_parent)
    return None

vertices = ['s', 'U', 'u', 't', 'w']
graph = BidirectionalSearch(vertices)
graph.add_edge('s', 'U', 3)
graph.add_edge('U', 'u', 3)
graph.add_edge('u', 't', 3)
graph.add_edge('s', 'w', 4)
graph.add_edge('w', 't', 4)
path = graph.bidirectional_search('s', 't')
    if path:
        print("Shortest path is:", end=" ")
        print(" -> ".join(path))
    else:
        print("No path found.")

vertices = ['s', 'U', 'u', 't', 'w']
graph = BidirectionalSearch(vertices)
graph.add_edge('s', 'U', 3)
graph.add_edge('U', 'u', 3)
graph.add_edge('u', 't', 3)
graph.add_edge('s', 'w', 5)
graph.add_edge('w', 't', 5)
path = graph.bidirectional_search('s', 't')
    if path:
        print("Shortest path is:", end=" ")
        print(" -> ".join(path))
    else:
        print("No path found.")