[요약] 자료 구조 - 5 [정렬, 검색, 해싱]

※ 주의 ※
이 블로그는 어디까지나 CS관련 지식을 정리하는 것이 목적입니다. 제가 이해한 내용이 잘못 된 것 같다면 댓글로 남겨주세요. 여러분의 관심이 저의 지식 함양에 도움이 됩니다.

>> 정렬의 개념과 정렬의 종류 

• 정렬(Sorting)은 데이터를 특정 기준에 따라 순서대로 배열하는 과정입니다. 일반적으로 두 가지 방식이 있습니다:
  1. 오름차순 (Ascending Order): 작은 값에서 큰 값으로 정렬합니다.
  2. 내림차순 (Descending Order): 큰 값에서 작은 값으로 정렬합니다.
• 정렬의 주요 개념:
  • 키(Key): 데이터를 정렬하는 기준이 되는 값입니다.
• 정렬 방식의 분류:
  1. 내부 정렬 (Internal Sorting):
     • 정의: 정렬할 자료를 메인 메모리에 올려서 정렬하는 방식입니다.
     • 장점: 속도가 빠릅니다.
     • 제한: 메인 메모리 용량에 따라 처리할 수 있는 자료의 양이 제한됩니다.
  2. 외부 정렬 (External Sorting):
     • 정의: 정렬할 자료를 보조 기억장치에서 정렬하는 방식입니다.
     • 장점: 대용량의 자료를 정렬할 수 있습니다.
     • 단점: 내부 정렬에 비해 속도가 떨어집니다.
     • 병합 방식:
       • 2-way 병합: 두 개의 정렬된 파일을 병합합니다.
       • n-way 병합: 여러 개의 정렬된 파일을 병합합니다.

>> 정렬 알고리즘의 종류 

1. 선택 정렬 (Selection Sort):
   • 작동 방식: 전체 원소들 중에서 기준 위치에 맞는 원소를 선택하여 자리를 교환하는 방식입니다.
   • 알고리즘:
     1. 배열의 첫 번째 원소부터 시작하여 최소값을 찾습니다.
     2. 최소값을 기준 위치와 교환합니다.
     3. 다음 원소에 대해 동일한 작업을 반복합니다.
   • 시간 복잡도: O(n^2)
2. 버블 정렬 (Bubble Sort):
   • 작동 방식: 인접한 두 개의 원소를 비교하고, 자리를 교환하여 정렬하는 방식입니다. 물속에서 물방울이 올라오는 듯한 모양을 형상화하여 "버블 정렬"이라 부릅니다.
   • 알고리즘:
     1. 배열의 첫 번째 원소부터 마지막 원소까지 인접한 두 원소를 비교하여 교환합니다.
     2. 마지막 원소까지 반복하여 가장 큰 원소가 제자리로 가게 됩니다.
     3. 반복 횟수를 줄이면서 정렬을 완료합니다.
   • 시간 복잡도: O(n^2)
3. 퀵 정렬 (Quick Sort):
   • 작동 방식: 정렬할 전체 원소에 대해 정렬을 수행하지 않고, 기준 값을 중심으로 왼쪽 부분 집합과 오른쪽 부분 집합으로 분할하여 정렬합니다.
   • 알고리즘:
     1. 피벗(Pivot)을 선택합니다.
     2. 피벗을 기준으로 왼쪽과 오른쪽 부분 집합으로 나눕니다.
     3. 각각의 부분 집합에 대해 재귀적으로 정렬합니다.
   • 시간 복잡도: 평균 O(n log n), 최악 O(n^2)
4. 삽입 정렬 (Insertion Sort):
   • 작동 방식: 정렬되어 있는 부분집합에 새로운 원소의 위치를 찾아 삽입하는 방식입니다.
   • 알고리즘:
     1. 두 번째 원소부터 시작하여 현재 원소를 정렬된 부분 집합에 적절한 위치에 삽입합니다.
     2. 삽입 위치를 찾기 위해 정렬된 부분 집합을 순회하며 비교합니다.
   • 시간 복잡도: 평균 O(n^2), 최선 O(n)
5. 셸 정렬 (Shell Sort)
   
   • 작동 방식: 셸 정렬은 배열의 원소를 일정한 간격(Interval)으로 나누어 부분 집합을 구성한 후, 각 부분 집합에 대해 삽입 정렬을 수행하면서 전체 배열을 정렬하는 방법입니다.
   • 알고리즘:
     1. 간격 설정: 배열의 원소를 일정한 간격으로 나누어 부분 집합을 형성합니다. 이 간격은 점진적으로 줄어들면서 최종적으로 1이 됩니다.
     2. 부분 집합 정렬: 각 부분 집합에 대해 삽입 정렬을 수행합니다.
     3. 간격 감소: 간격을 줄여가며 다시 부분 집합을 형성하고 정렬을 반복합니다.
     4. 정렬 완료: 간격이 1이 될 때까지 반복하면 전체 배열이 정렬됩니다.
   • 장점: 전체 원소에 대해 삽입 정렬을 수행하는 것보다 비교연산과 교환연산이 줄어들어 성능이 향상될 수 있습니다.
   • 시간복잡도: 평균 O(n^1.5) ~ O(n^2), 최악 O(n^2) (간격 설정에 따라 다름)
6. 병합 정렬 (Merge Sort)
   
   • 작동 방식: 병합 정렬은 배열을 여러 개의 부분 집합으로 분할한 후, 각 부분 집합을 정렬하고 다시 병합하여 하나의 정렬된 배열로 만드는 방법입니다. 분할 정복 기법을 사용합니다.
   • 알고리즘:
     1. 분할: 배열을 두 개의 부분 집합으로 나눕니다.
     2. 정렬: 각 부분 집합을 재귀적으로 정렬합니다.
     3. 병합: 정렬된 두 부분 집합을 병합하여 하나의 정렬된 배열로 만듭니다.
   • 병합 방법:
     • 2-way 병합: 두 개의 정렬된 배열을 병합합니다.
     • n-way 병합: n개의 정렬된 배열을 병합합니다.
   • 장점: 안정적인 정렬 방법이며, 큰 데이터 집합에 대해 성능이 뛰어납니다.
   • 시간복잡도: O(n log n) (최악, 평균)
7. 히프 정렬 (Heap Sort)
   
   • 작동 방식: 히프 정렬은 히프 자료구조를 이용하여 정렬을 수행하는 방법입니다.
   • 알고리즘:
     1. 히프 구성: 배열을 최대 히프(또는 최소 히프)로 변환합니다.
     2. 삭제 및 정렬: 최대 히프에서 루트 노드를 삭제하여 배열의 끝으로 이동시키고, 남은 히프를 재구성합니다. 이 과정을 반복하여 전체 배열을 정렬합니다.
     • 최대 히프: 루트 노드가 가장 큰 원소
     • 최소 히프: 루트 노드가 가장 작은 원소
   • 장점: 정렬 후 히프 구조를 유지할 수 있으며, 추가적인 메모리 공간을 거의 사용하지 않습니다.
   • 시간복잡도: O(n log n)
8. 트리 정렬 (Tree Sort)
   
   • 작동 방식: 트리 정렬은 이진 탐색 트리를 이용하여 정렬을 수행하는 방법입니다.
   • 알고리즘:
     1. 트리 구성: 정렬할 원소를 이진 탐색 트리에 삽입합니다.
     2. 중위 순회: 이진 탐색 트리를 중위 순회하여 원소를 오름차순으로 배열합니다.
   • 장점: 이진 탐색 트리를 이용해 정렬하기 때문에 삽입과 삭제가 간편합니다.
   • 시간복잡도:
     • 평균: O(n log n)
     • 최악: O(n^2) (트리가 불균형할 경우)

>> 검색의 개념과 검색 방법 

• 검색: 컴퓨터에 저장된 자료 중에서 원하는 항목을 찾는 작업입니다. 검색의 성공은 원하는 항목을 찾은 경우를 의미하고, 검색의 실패는 원하는 항목을 찾지 못한 경우를 의미합니다. 탐색 키는 자료를 구별하여 인식할 수 있는 기준값입니다.
• 검색 방법에는 두 가지 주요 분류가 있습니다:
  1. 내부 검색: 메모리 내의 자료에 대해 수행하는 검색
  2. 외부 검색: 보조 기억 장치에 있는 자료에 대해 수행하는 검색
• 검색 방식에 따른 분류는 다음과 같습니다:
  1. 비교 검색 방식: 항목을 비교하여 원하는 값을 찾는 방법
  2. 계산 검색 방식: 계산을 통해 검색을 수행하는 방법

>> 순차 검색 (Sequential Search) 

• 정의: 자료를 처음부터 끝까지 순서대로 검색하는 방법입니다.
• 특징:
  • 가장 간단하고 직접적인 검색 방법입니다.
  • 배열이나 연결 리스트로 구현된 자료구조에서 사용됩니다.
  • 검색 대상 자료가 많은 경우 비효율적입니다.
  • 검색해야 할 자료가 정렬된 상태인지 아닌지에 따라 검색 실패를 판단하는 시점이 달라집니다.
• 시간 복잡도:
  • 최악의 경우: O(n)
  • 평균적인 경우: O(n)

>> 이진 검색 (Binary Search) 

• 정의: 자료의 가운데 항목을 기준으로 키 값을 비교하여 검색 위치를 결정하고, 검색 범위를 반으로 줄여가면서 진행하는 방법입니다.
• 작동 방식:
  1. 정렬된 자료에서 중앙 값을 선택합니다.
  2. 검색 키와 중앙 값을 비교합니다.
  3. 검색 키가 중앙 값보다 크면 오른쪽 부분 집합에서 검색을 계속하고, 작으면 왼쪽 부분 집합에서 검색을 계속합니다.
  4. 이 과정을 반복하여 키 값을 찾을 때까지 검색 범위를 줄여 나갑니다.
• 장점: 정렬된 자료에 대해 매우 빠르게 검색할 수 있습니다.
• 시간 복잡도:
  • 최악의 경우: O(log n)
  • 평균적인 경우: O(log n)

>> 이진 탐색 트리 검색 (Binary Search Tree Search) 

• 정의: 이진 탐색 트리를 사용하여 검색하는 방법입니다. 이진 탐색 트리는 각 노드가 왼쪽 서브트리의 모든 노드보다 크고, 오른쪽 서브트리의 모든 노드보다 작다는 속성을 가지고 있습니다.
• 작동 방식:
  1. 현재 노드의 값을 검색 키와 비교합니다.
  2. 검색 키가 현재 노드의 값보다 작으면 왼쪽 서브트리에서, 크면 오른쪽 서브트리에서 검색을 계속합니다.
  3. 이 과정을 반복하여 검색 키를 찾거나, 서브트리의 끝까지 도달할 때까지 진행합니다.
• 장점:
  • 평균적으로 매우 빠른 검색 속도를 제공합니다.
  • 삽입과 삭제 연산에 대해 이진 탐색 트리를 재구성하는 작업이 필요합니다.
• 시간 복잡도:
  • 평균적인 경우: O(log n)
  • 최악의 경우 (트리가 불균형일 때): O(n)

>> 해싱의 개념 

• 해싱: 산술적인 연산을 이용하여 키가 있는 위치를 계산하여 바로 찾아가는 계산 검색 방식입니다. 해싱을 사용하면 키 값을 해시 함수에 입력하여 해시 테이블의 주소를 구하고, 그 주소를 통해 직접 접근하여 검색할 수 있습니다.
• 검색 과정:
  1. 해시 함수를 사용하여 검색할 키 값에 대한 주소를 계산합니다.
  2. 계산된 주소를 사용하여 해시 테이블에서 해당 위치로 이동합니다.
  3. 해당 위치에 찾는 항목이 있으면 검색 성공, 없으면 검색 실패입니다.

>> 해시 함수 

• 정의: 키 값을 해시 테이블의 주소로 변환하는 함수입니다.
• 해시 함수의 조건:
  1. 계산이 용이: 해시 함수는 빠르게 계산할 수 있어야 합니다.
  2. 충돌 최소화: 서로 다른 키 값이 같은 주소를 가지는 충돌을 최소화해야 합니다.
  3. 고른 분포: 해시 테이블에 균등하게 키를 분포시킬 수 있어야 합니다.

>> 해싱에서 오버플로우 처리 방법 

1. 선형 개방 주소법 (Linear Probing):
   • 정의: 해시 함수로 계산된 주소에 빈 슬롯이 없을 경우, 그 다음 버킷에 빈 슬롯이 있는지 조사하는 방법입니다.
   • 과정:
     1. 해시 함수로 계산한 주소가 가득 차 있으면, 그 다음 버킷을 조사합니다.
     2. 빈 슬롯이 있으면 거기에 키 값을 저장합니다.
     3. 빈 슬롯이 없으면 계속 다음 버킷을 조사하여 빈 슬롯을 찾습니다.
2. 체이닝 (Chaining):
   • 정의: 해시 테이블의 구조를 변경하여 각 버킷에 하나 이상의 키 값을 저장할 수 있도록 하는 방법입니다. 각 버킷이 연결 리스트를 가지고 있어서 슬롯을 동적으로 삽입하거나 삭제할 수 있습니다.
   • 과정:
     1. 해시 테이블의 각 버킷에 연결 리스트를 사용하여 슬롯을 관리합니다.
     2. 각 버킷의 헤드 노드를 1차원 배열로 유지하고, 그 노드는 슬롯들을 연결 리스트로 가집니다.
     3. 슬롯의 삽입이나 삭제는 연결 리스트에서 직접 수행할 수 있으며, 검색 시 연결 리스트를 선형 검색합니다.

장점과 단점:

• 선형 개방 주소법: 간단하지만, 해시 테이블이 가득 차면 성능이 저하될 수 있습니다.
• 체이닝: 슬롯의 동적 삽입과 삭제가 용이하며, 해시 테이블이 가득 차지 않으므로 성능이 상대적으로 안정적입니다. 단점은 메모리 사용이 상대적으로 많을 수 있으며, 연결 리스트의 검색 시간이 추가적으로 소요될 수 있습니다.