정렬 알고리즘

정렬의 종류

 

• 버블 정렬 (bubble sort)
  - 가장 기본적인 정렬로 인접한 i번째 키와 i + 1번째 키를 비교하여 교환하는 방법
  - 초기 데이터가 원하는 정렬 순서로 입력되면 정렬을 도중에 멈출 수 있으며 정렬 도중 완료된 경우에도 확인할 수 있음
  - 평균 시간복잡도 : O(n^2) / 최악 시간복잡도 : O(n^2)

초기값	50	20	30	10	40
1단계	20	30	10	40	50
2단계	20	10	30	40	50
3단계	10	20	30	40	50

 

• 선택 정렬 (selection sort)
  - 키 중 최소값을 선택하여 첫 레코드와 교환하고, 다음에는 2번부터 n번까지에서 같은 과정을 수행
  - 비교횟수가 많을 수 있으나 모든 키가 한 단계에 한번만 이동하면 되므로 이동횟수는 적음
  - 평균 시간복잡도 : O(n^2) / 최악 시간복잡도 : O(n^2)

초기값	50	20	30	10	40
1단계	10	20	30	50	40
2단계	10	20	30	50	40
3단계	10	20	30	50	40
4단계	10	20	30	40	50

 

• 삽입 정렬 (insertion sort)
  - 첫 번째 레코드를 정의된 것으로 보고 첫 번째와 두 번째 키를 비교해 순서대로 나열하고, 세 번째키를 첫 번째, 두 번째 키와 비교해 순서대로 나열하고, 계속해서 n번째 키를 앞의 n - 1개의 키와 비교하여 알맞은 순서에 삽입하여 정렬하는 방식
  - 정렬된 입력데이터에 대해서는 최수 비교횟수가 발생하며 (O(n)), 반대로 정렬된 입력에 대해서는 최대 비교횟수가 발생
  - 평균 시간복잡도 : O(n^2) / 최악 시간복잡도 : O(n^2)

초기값	50	20	30	10	40
1단계	20	50	30	10	40
2단계	20	30	50	10	40
3단계	10	20	30	50	40
4단계	10	20	30	40	50

 

• 퀵 정렬 (quick sort)
  - 파일을 두 개의 부파일로 나누는데 키를 기준으로 작은 값은 왼쪽에, 큰 값은 오른쪽 서브파일로 분해시키는 방식으로 정렬
  - 피벗(기준)값을 하나 정해서 low, high를 비교해 나가는 방식인데 보통 첫번째나 마지막 인덱스를 기준으로 두는 것이 편하지만 위치와 상관없이 임의의 키를 분할 원소로 사용할 수 있음
  - 정렬 방식 중에서 가장 빠르며 스택이 필요
  - 피벗을 중심으로 문제를 분할하고, 피벗을 기준으로 해서 작은 값과 큰 값을 나열하는 정복 과정을 거친 뒤 결과를 결합
  - 평균 시간복잡도 : O(nlogn) / 최악 시간복잡도 : O(n^2)
  - 배열을 이용해 퀵 정렬을 설명하자면,
  1. 초기값 50 20 60 40 80 70 30 10 90의 값이 있을 때 0번째 인덱스를 피벗으로 두고 start와 end 인덱스를 각각 1, 8로 설정
  2. 먼저 start 인덱스 값(20)과 피벗 인덱스 값(50)을 비교 -> 이때 (피벗 > start)이면 start 인덱스를 오른쪽으로 한 칸 이동 / (피벗 < start)일 때는 end 인덱스를 비교 => 해당 예시는 50 > 20이므로 start 인덱스를 한 칸 이동
  3. 다시 피벗의 값과 비교 => 50 < 60이므로 start 인덱스는 그대로 둠
  4. end 인덱스의 값과 비교 -> (피벗 < end)이면 end 인덱스를 왼쪽으로 한 칸 이동  / (피벗 > end)이면 종료 => 50 < 90이므로 end 인덱스 왼쪽으로 한 칸 이동
  5. 50과 10을 비교 => 피벗 > end이므로 종료 후 start와 end의 위치가 역전된 상태인지 확인 -> 역전되지 않았다면 start 인덱스 값과 end 인덱스 값 교환 => 60과 10을 교환하여 50 20 10 40 80 70 30 60 90으로 바뀜
  6. 현재 위치에서 다시 위 과정을 반복 -> 만약 5번에서 start와 end 인덱스가 역전된 상태라면 피벗 값과 end 인덱스가 가리키는 값을 교환한 후 두 개의 배열로 다시 쪼개서(가운데 들어간 피벗값을 기준으로) 1 ~ 6번 과정 반복
  
  
• 힙 정렬 (heap sort)
  - 완전 이진 트리를 이용한 정렬 방식
  - 최대 힙(루트의 값이 가장 큰 값) or 최소 힙(루트의 값이 가장 작은 값)을 이용하여 정렬함
  - 평균 시간복잡도 : O(nlogn) / 최악 시간복잡도 : O(nlogn)
  - 최대 힙을 예로 설명하자면,
  1. 완전 이진 트리에 값을 삽입하고 부모 노드가 자식 노드보다 작지 않도록 값을 교환
  2. 루트의 최대값을 마지막 노드와 교환
  3. 나머지 값들로 최대힙을 다시 구성

초기값

30

20

50

10

40

최대힙 생성

<1단계> 적용 후 50 결정

 

• 2-Way 합병 정렬 (merge sort)
  - 이미 정렬되어 있는 두 개의 파일을 한 개의 파일로 합병하는 정렬 방식
  - 평균 시간복잡도 : O(nlogn) / 최악 시간복잡도 : O(nlogn)
  - 71, 2, 38, 5, 7, 61, 11, 26, 53, 42의 레코드가 존재
  1. 두 개씩 묶은 후 각각의 묶음 안에서 정렬
  (71, 2) (38, 5) (7, 61) (11, 26) (53, 42) -> (2, 71) (5, 38) (7, 61) (11, 26) (42, 53)
  2. 묶여진 묶음을 두 개씩 묶은 후 각각의 묶음 안에서 정렬
  ((2, 71) (5, 38)) ((7, 61) (11, 26)) (42, 53) -> (2, 5, 38, 71) (7, 11, 26, 61) (42, 53)
  3. 현재 과정을 반복
  
  
• 기수 정렬 (radix sort = bucket sort)
  - 비교가 아닌 분배에 의한 정렬
  - 레코드의 키 값을 분석하여 같은 수 또는 같은 문자끼리 그 순서에 맞는 버킷에 분배하였다가 버킷의 순서대로 레코드를 꺼내어 정렬
  - 평균 시간복잡도 : O(n) / 최악 시간복잡도 : O(n)

 

※ 알고리즘 시각화 사이트

https://visualgo.net/en/sorting?slide=1

Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix) - VisuAlgo

 

 

 

 

탐색

 

- 어떤 특정한 원소를 찾기 위해 자료구조나 파일을 조사하는 과정

 

* 탐색 장소에 따른 분류

- 내부 탐색 : 메모리 내의 자료에 대해 탐색 수행

- 외부 탐색 : 보조기억장치 내의 자료에 대해 탐색 수행

* 탐색 방식에 따른 분류

- 비교 탐색 방식 : 탐색 대상의 키를 비교하여 탐색 수행(순차 탐색, 이진 탐색, 이진 탐색트리)

- 계산 탐색 방식 : 계수적인 성질을 이용한 계산으로 탐색 수행(해싱)

 

 

 

 

 

탐색의 종류

 

• 순차 탐색 (Sequential Search)
  - 하나의 레코드씩 차례로 키 값이 k와 같은지 비교하여 찾는 탐색
  - 정렬되지 않은 파일도 탐색할 수 있는 방법
  - 탐색 시간 복잡도 : O(n)
  
  
• 이진 탐색(Binary Search)
  - 파일이 반드시 정렬되어 있어야만 가능
  - 파일의 중앙의 키 (mid = low + high / 2) 값이 찾고자하는 레코드의 키 값 K보다 크면 찾고자 하는 레코드는 중앙보다 앞쪽에만 있을 가능성이 있음
  - 한 번의 비교로 탐색대상이 반으로 감소
  - 탐색 시간이 적게 걸리며 최악의 비교횟수도 평균 비교횟수보다 한번만 더 수행하므로 레코드 수가 많을수록 효과적
  - 데이터의 삽입이나 삭제가 빈번할 시 적합하지 않고 주로 고정된 데이터에 적합
  - 탐색 시간 복잡도 : O(longn)
  
  
• 이진 탐색 트리(BST)
  • 이진 탐색 트리의 정의
    - 모든 원소는 키를 가지며, 어떤 두 원소도 동일한 키를 갖지 않음
    - 왼쪽 서브트리에 있는 키들은 그 루트의 키보다 작음
    - 오른쪽 서브트리에 있는 키들은 그 루트의 키보다 큼
    - 왼쪽과 오른쪽 서브트리도 모드 이진 탐색 트리
    - 탐색 시간 복잡도 : O(log2n) (균형적) / O(n) (불균형적)
    
    
  • 삽입 연산
    - 파일 내의 레코드 순서가 10, 30, 20, 25, 28인 경우에 불균형 이진탐색트리가 됨
    - 파일 내의 레코드 순서가 28, 20, 25, 10, 30일 경우 균형 이진탐색트리가 됨
    - 삽입되는 노드는 항상 단말 노드가 되며 이진 탐색트리의 삽입에 필요한 시간은 높이에 비례
    
    
  • 탐색 연산
    - BST에서 특정 키 값을 가진 노드를 찾기 위해서는 먼저 주어진 탐색키 값과 현재의 루트 노드의 키 값을 비교
    - 비교한 결과가 같으면 탐색이 성공적으로 끝남
    - 주어진 키 값이 루트 노드의 키 값보다 작으면 탐색은 이 루트 노드의 왼쪽 자식을 기준으로 다시 시작
    - 주어진 키 값이 루트 노드의 키 값보다 크면 탐색은 이 루트 노드의 오른쪽 자식을 기준으로 다시 시작

탐색과 삽입 예시

 

• AVL 트리
  - 항상 균형을 유지하는 이진 탐색 트리
  - 삽입, 삭제가 일어날 때마다 트리의 균형 상태를 점검하고 균형이 깨지면 트리 모습을 변형함으로 항상 균형을 유지
  - 균형인수(노드의 왼쪽 하위트리의 높이 - 오른쪽 하위트리의 높이)는 항상 0, +-1을 유지
  - 탐색 시간 복잡도 : O(log2n)

불균형 트리를 AVL 트리로 바꾸는 과정

 

• M차 B-Tree
  - B-Tree는 보통 B트리를 뜻하며 하나의 노드에 많은 정보를 가지거나, 두 개 이상의 자식을 가질 수 있는 트리를 뜻함
  - 이렇게 차수라는 개념이 등장하며 최대 M개의 자식을 가질 수 있는 B-Tree를 M차 B-Tree라고 부르게 됨
  - 항상 정렬된 상태로 존재
  - 내부 노드는 ceil(M / 2) - 1 ~ M개의 자식을 가질 수 있음
  - 특정 노드의 데이터가 k개라면 자식 노드의 개수는 k + 1
  - 모든 외부 노드들은 같은 레벨에 있음
  
  • M차 B-Tree의 삽입
    - 새로운 값은 항상 단말노드에 삽입
    - 빈공간이 있을 경우에는 단순삽입
    - 빈공간이 없을 경우 중간 값을 갖는 노드가 부노드가 되고 원래의 노드를 두 개의 노드로 분할
    
    
  • M차 B-Tree의 삭제
    - 삽입과 같이 리프 노드에서 수행
    - 삭제키가 리프가 아닌 노드에 있을 때는 후행키 값과 자리교환하여 리프노드에서 삭제
    - 삭제로 인해 언더플로가 발생하면 재분배나 합병으로 최소키 개수를 유지

 

※ 참고

▶︎ B-Tree의 생성과 삭제를 눈으로 확인할 수 있는 사이트

https://www.cs.usfca.edu/~galles/visualization/BTree.html

B-Tree Visualization

▶︎ B-Tree의 삽입, 탐색, 삭제의 과정을 보다 상세히 설명한 글

https://code-lab1.tistory.com/217

[자료구조] B-트리(B-Tree)란? B트리 그림으로 쉽게 이해하기, B트리 탐색, 삽입, 삭제 과정

 

 

 

 

 

해싱 (Hashing)

 

• 해싱의 개요
  - 탐색목표가 아닌 다른 레코드의 키 값과 비교할 필요가 없는 탐색 방법
  - 파일 내의 각 키에 대응하는 인덱스로 작성된 해시표에서 단 한번의 접근으로 레코드를 탐색하는 방법
  - 탐색 시간복잡도 : O(1)
  - 충돌이 발생하면 탐색 시간복잡도 : O(n)

* 해싱 용어
- 버켓(bucket) : 자료를 저장할 기억장소로 1개 이상의 슬롯으로 구성
- 해시표 : 해시함수에 의해 산출된 해시주소의 위치에 해당 자료를 기억시킨 표로 일반적으로 배열로 선언되고, 버킷과 슬롯으로 구성
- 해싱함수 : 키에 대한 해시주소를 구할 때 적용되는 함수
- 해시주소 : 해싱함수에 의해 계산된 번지로 자료가 저장되는 주소
- 충돌 : 서로 다른 데이터가 동일한 해시 주소를 가지는 경우
- 동의어 : 충돌이 발생한 서로 다른 값을 가지는 두 개 이상의 데이터
- 오버플로 : 충돌이 발생하여 자료를 저장할 공간이 없는 경우

 

• 해싱함수
  ▶︎ 제산법(Division)
  - 키의 특성이나 분포가 미리 알려져 있지 않을 때 많이 사용
  - % 연산, 나머지를 해시주소로 이용하는 방법
  - 버켓의 크기에 근접하는 수로 키값을 나눈 나머지를 해시 주소로 사용

Key	해시주소
57 24 21 32	57 % 7 = 1 24 % 7 = 3 21 % 7 = 0 32 % 7 = 4

 

      ▶︎ 제곱법(Mid square) : 키값을 제곱하여 그 수의 중간 일부분을 추출하여 해시주소로 사용

Key	k^2	해시주소
524 714 184 327	274576 509796 033856 106929	45 97 38 69

 

      ▶︎ 폴딩법(folding)
      - 키 값 k를 몇 개의 부분으로 분할하여 다 더한 결과를 해시 주소로 하는 것

      - 쉬프트(shift) 폴딩 : 순서대로 더하는 방법 / 경계(boundary) 폴딩 : 한번은 그대로 한번은 숫자를 거꾸로 더하는

         방법

키 = 82082623940812

LSD부터 3자리씩 구분하면 82, 82, 623, 940, 812

쉬프트 폴딩 : 82 + 82 + 623 + 940 + 812 = 2539

경계 폴딩 : 82 + 280 + 623 + 49 + 812 = 1846

 

      ▶︎ 자리수 분석법(digit analysis)

 

      - 키 특성이나 분포가 미리 잘 알려져 있을 때 유용      

      - 많은 자리수의 키 값 중에서 다른 레코드의 키와 같은 값을 가질 확률이 높은 자리의 값을 제외하고, 키마다 서로

         다른 값을 가지리라고 예상되는 위치의 값을 해시주소로 택함

Key	해시주소
1234-584-1604 1234-837-6418 1234-924-2442 1234-786-8311	514 868 922 781

 

* 오버플로 해결 방법

1. 개방 주소법 : 가까운 다른 해시번지의 버켓에 들어가는 것을 허용하는 방법

- 선형 조사법 : 계산된 해시주소 h(x)에 1을 더하고 또 오버플로가 발생하면 h(x)에 2를 더하는 방법 (1, 2, 3, 4 ...)

-> 알고리즘은 간단하나 키 값들이 한 곳에 모이는 제1밀집 현상 일어남

- 이차 조사법 : 계산된 해시주소 h(x)에 1^2을 더하고 또 오버플로가 발생하면 h(x)에 2^2를 더하는 방법 (1^2, 2^2, 3^3 ...)

- 이중 해싱 : 계산된 해시주소 h(x)에 또다른 해시함수를 이용하여 구한 변위를 더하는 방법으로 키마다 변위가 다름

2. 폐쇄 주소법 : 오버플로가 발생해도 새로운 해시주소를 구하지 않고 포인터에 의하여 같은 해시주소를 연결리스트로 만드는 연쇄방법(chaining)으로 표현

 

Q. 다음 조건에 따라 입력 키 값을 해시 테이블에 저장하였을 때 해시 테이블의 내용으로 옳은 것은?

<조건>

- 해시 테이블의 크기는 7이다.

- 해시 함수는 h(x) = k mod 7이다.

- 충돌은 이차 조사법으로 처리한다.

- 키 값의 입력 순서 : 9, 16, 2, 6, 20

 

-> 

1. 9 % 7 = 2 (2번째 인덱스에 9 저장)

2. 16 % 7 = 2 (충돌 발생!!) => 2 + 1^2 = 3 (3번째 인덱스에 16 저장)

3. 2 % 7 = 2 (충돌 발생!!) => 2 + 1^2 = 3 (충돌 발생!!) => 2 + 2^2 = 6 (6번째 인덱스에 2 저장)

4. 6 % 7 = 6 (충돌 발생!!) => 6 + 1^2 = 7 (버켓 범위 벗어남) => 7 % 7 = 0 (0번째 인덱스에 6 저장)

5. 20 % 7 = 6 (충돌 발생!!) => 6 + 1^2 = 7 (버켓 범위 벗어남) => 7 % 7 = 0 (충돌 발생!!) => 6 + 2^2 = 10 % 7 = 3 => 6 + 3^2 = 15 => 15 % 7 = 1 (1번째 인덱스에 20 저장)

 

0	1	2	3	4	5	6
6	20	9	16			2