자료의 정렬과 탐색

정렬 알고리즘

정렬 알고리즘을 통해 전체 또는 부분의 탐색을 바탕으로 쉽게 해를 찾을 수 있게 하여 빠른 탐색, 문제해결 등 여러 분야에 쓰인다.

블로그 이미지 참조 : https://secumation.tistory.com/19

버블정렬

두 인접한 원소 간의 비교와 교환의 과정을 반복하는 정렬 알고리즘이다. 리스트의 맨 앞에 있는 원소를 비교하여 둘중 큰 값을 뒤로 보내는 과정을 반복한다.

버블정렬 알고리즘

[버블 정렬 알고리즘: 단, d[ ]는 원소가 포함된 리스트]

n ← length_of_d[ ]
for i ← 0 to n-1 step 1
for j ← 2 to n-i step 1
if d[j]＜d[j-1] then
swap(d[j], d[j-1])
end if
end for
end for

시간복잡도

-비교 횟수

  최상, 평균, 최악 모두 일정
  n-1, n-2, … , 2, 1 번 = n(n-1)/2

-교환 횟수

  입력 자료가 역순으로 정렬되어 있는 최악의 경우, 한 번 교환하기 위하여 3번의 이동(SWAP 함수의 작업)이 필요하므로 (비교 횟수 * 3) 번 = 3n(n-1)/2 

  입력 자료가 이미 정렬되어 있는 최상의 경우, 자료의 이동이 발생하지 않는다.

-T(n) = O(n^2)

선택정렬

주어진 리스트의 원소 중에서 최솟값을 찾아 맨 앞에 위치한 값과 교체하는 과정을 반복하는 알고리즘이다.

선택정렬 알고리즘

[선택 정렬 알고리즘: 단, d[ ]는 원소가 포함된 리스트]

n ← length_of_d[ ]
for i ← 1 to n-2 step 1
min ← i
for j ← i+1 to n step 1
if d[j]＜d[min] then
min ← j
end if
end for
swap(d[i], d[min])
end for

시간복잡도

-비교 횟수

  두 개의 for 루프의 실행 횟수
  외부 루프: (n-1)번
  내부 루프(최솟값 찾기): n-1, n-2, … , 2, 1 번

-교환 횟수

  외부 루프의 실행 횟수와 동일. 즉, 상수 시간 작업
  한 번 교환하기 위하여 3번의 이동(SWAP 함수의 작업)이 필요하므로 3(n-1)번

-T(n) = (n-1) + (n-2) + … + 2 + 1 = n(n-1)/2 = O(n^2)

삽입정렬

삽입 정렬은 주어진 리스트의 원소를 한 개씩 삽입하는 과정을 반복적으로 수행함으로써 정렬을 완료하는 알고리즘이다.

삽입정렬 알고리즘

[단, d[ ]는 원소가 포함된 리스트]

n ← length_of_d[ ]
for i ← 2 to n step 1
j ← i
while j＞1 and d[j-1]＞d[j]
swap(d[j], d[j-1])
j ← j-1
end while
end for

시간복잡도
최선의 경우

-비교 횟수

  이동 없이 1번의 비교만 이루어진다.
  외부 루프: (n-1)번

-Best T(n) = O(n)

최악의 경우(입력 자료가 역순일 경우)

-비교 횟수

  외부 루프 안의 각 반복마다 i번의 비교 수행
  외부 루프: (n-1) + (n-2) + … + 2 + 1 = n(n-1)/2 = O(n^2)

-교환 횟수

  외부 루프의 각 단계마다 (i+2)번의 이동 발생
  n(n-1)/2 + 2(n-1) = (n^2+3n-4)/2 = O(n^2)

-Worst T(n) = O(n^2)

퀵(Quick) 정렬

퀵 정렬은 주어진 리스트의 원소 중 하나를 피벗(기준)으로 선택하고, 이 원소와의 크기 비교를 통해 나머지 원소들을 분할하는 과정을 재귀적으로 반복하는 정렬 알고리즘이다. 분할 이후에는 기준값(피벗)의 위치가 고정된다.

퀵 정렬 알고리즘

[단, d[ ]는 원소가 포함된 리스트]

Qsort(left, right)
if left＜right
select pi
pivot ← d[pi]
Partition(left, right) 
Qsort(left, pi-1) 
Qsort(pi+1, right)
end if
end Qsort
Partition(left, right)
if pi=left
low ← left+1
else
low ← left
end if
if pi=high
high ← right-1
else
high ← right
end if
while low＜high
while d[low]＜=pivot and low＜right
low ← low+1
end while
while d[high]＞pivot and high＞left
high ← high-1
end while
if low＜high
swap(d[low], d[high]
else
swap(d[pi], d[high]
end if
end while
pi ← high
end Partition

특징 : 일반적으로 n개의 원소를 정렬하는 가장 빠른 알고리즘으로 분류됨. 특히 어떤 원소를 피벗으로 분류하느냐에 따라 알고리즘의 효율이 달라지기 때문에 최근에도 중간값을 이용해 피벗값을 설정하는등 피벗값 설정과 관련한 다양한 연구가 진행되고 있다.

히프(Heap) 정렬

히프 정렬은 주어진 리스트의 원소를 이용하여 최대 히프를 만들고, 루트 노드에 위치한 가장 큰 값을 단말 노드 중 가장 마지막 원소의 값과 교환하는 과정을 반복하는 정렬 알고리즘이다. 또한 히프는 루트 노드의 값이 다른 노드들과 비교해 항상 큰 완전 2진트리이다.

힙(Heap)

자세한 내용 참조 https://secumation.tistory.com/18

히프 정렬 알고리즘

1. n개의 노드에 대한 완전 2진 트리를 구성한다. 이때 루트 노드부터 부모 노드, 왼쪽 자식 노드, 오른쪽 자식 노드의 순으로 구성한다.

2. 정렬되지 않은 원소를 바탕으로 최대 히프를 구성한다. 최대 히프란 부모 노드가 자식 노드보다 큰 트리를 말하는데, 단말 노드를 자식 노드로 가진 부모 노드부터 구성하며 아래부터 루트까지 올라오며 순차적으로 만들어 갈 수 있다.

3. 루트 노드와 가장 오른쪽 단말 노드의 값을 교환한다.

4. 2와 3을 반복한다.

자료의 탐색

탐색이란 목록에 포함된 원소 중에서 조건을 만족하는 특정한 원소를 찾는 것을 말한다. 탐색은 컴퓨터의 빠르고 정확한 계산 능력을 기반으로 한다. 그러나 자료의 양과 종류에 따라 적절한 탐색 전략이 존재한다.

순차 탐색

순차 탐색이란 리스트의 처음부터 끝까지 차례대로 모든 요소를 비교해서 자료를 찾는 탐색 알고리즘이다. 순차 탐색은 한쪽 방향으로만 탐색을 수행한다고 해서 선형 탐색이라고 부르기도 한다.

순차 탐색 알고리즘: 단 d[]는 원소가 포함된 리스트]
s ← key_value
n ← length_of_d[]
i ← 1
while d[i] != s && i <= n
  i ← i+1
end while
if i <= n
 print i
else
 print "Not Found"
end if

2진 탐색

2진 탐색이란 주어진 리스트를 탐색이 필요한 영역과 불필요한 영역으로 분할해 가면서 탐색을 수행하는 알고리즘이다. 특히 한 번 탐색을 수행할 떄마다 리스트의 원소들이 둘로 분할되기 때문에 2진 탐색 또는 2분 탐색이라고 부른다.

2진 탐색 알고리즘 : 단, d[]는 원소가 포함된 리스트
s ← key_value
n ← length_of_d[]
l ← 1
r ← n
while l<=r
 m ← (l+r)/2
 if s=d[m] break
 else if s > d[m]
  l ← m+1
 else 
  r ← m-1
 end if
end while
if l <= r
 print m
else
 print "Not Found"
end if

깊이 우선 탐색

깊이 우선 탐색(DFS : Depth First Search)은 트리 또는 그래프 등 비선형으로 구조화된 자료을에 대하여 적용할 수 있는 탐색 알고리즘이다. 깊이 우선 탐색은 하나의 정점을 탐색한 후 그에 인접한 정점들 중 아직 탐색하지 않은 한 정점을 탐색하는 방식을 재귀적으로 수행하는 탐색 알고리즘이다. 이떄 방향의 인접한 정점이 여러 개일 수 있으므로, 일관성 있는 선택 순서가 필요하다.

[깊이 우선 탐색 알고리즘]
//g[][]는 인접 행렬로 표현한 그래프로서 g[a][b]가 0 이면 a와 b는 연결되지 않은 정점이고 1이면 연겨로디어 있는 정점임
//s는 시작 정점
// visited[]는 정점의 탐색 여부를 기록하는 배열
n ← numberof all vertex
DFS(s)
 visited[s] ← 1
 for i ← 1 to n step 1
  if g[s][i] = 1 and visited[i] != 1
   DFS(i)
  end if
 end for
end DFS

너비 우선 탐색

너비 우선 탐색(BFS : Breadth First Search)은 인접한 정점을 모두 탐색하 ㄴ후, 탐색했던 정점 중 하나를 시작으로 다시 인접한 정점들을 차례로 방문하는 방식의 탐색 알고리즘이다. DFS와 마찬가지로 비선형 자료 구조의 탐색을 위해 사용할 수 있는 알고리즘이다. BFS는 시작 정점을 기준으로 인접한 정점들을 모두 방문한 후에 다음 인접 정점을 방문하는 바식이므로, 가까운 정점들을 먼저 방문하고 멀리 있는 정점들은 나중에 방문하는 결과를 가녀오게 된다.

[BFS]
//g[][]는 인접 행렬로 표현한 그래프로서 g[a][b]가 0 이면 a와 b는 연결되지 않은 정점이고 1이면 연겨로디어 있는 정점임
//s는 시작 정점
// visited[]는 정점의 탐색 여부를 기록하는 배열
n ← number of all vertex
BFS()
 Q_push(s)
 visited[s] ← 1
 while Q_empty() != true
  Q_pop()
  for i ← 1 to n step 1
   if g[s][i]=1 and visited[i] != 1
    Q_push(i)
    visited[i] ← 1
   end if
  end for
 end while
end BFS