[Data_Structure]Hash, Sort

Hash

• 저장하고자 하는 정보 Value
• Value를 구분할 수 있는 고유한 data : Key → 어떤 데이터를 쓸지에 따라 정할 수 있으며, 중복되지 않아야 함
• 해시함수
  • key를 입력으로 넣어주면 해시값이라는 결과 출력. 해시값을 인덱스화 하여 데이터 저장
  • 임의의 데이터(KEY)를 특정 값(해시값)으로 매핑시키는 함수
  • 데이터가 많아도 위치를 바로 찾을 수 있음
  • 시간복잡도 O(1)
• Hash table내 데이터가 저장되는 공간을 buckets
• 해싱
  • 데이터를 빠르게 가져오고 저장하는 기법
• 해시 테이블
  • Key, Value 쌍을 저장
  • 순서는 존재하지 않음
• KEY
  • ex)아이디, 주민번호와 같은 고유한 정보
• 좋은 해시 함수
  • 키 값을 고르게 분포 시키기
  • 해시 값을 계산해주는 속도 빠름 - 스캔하는 속도보다 해시함수 속도가 느리면 의미 없음
  • 해시 충돌(키 값이 다른데, 해시 함수의 결과값이 동일한 경우) 최소화
    • 해시 자료구조 성능을 떨어지게 하는 가장 큰 원인
    • 충돌해결 방식 - LinkedList를 이용한 chaining방식 이용
      • 특정 키에 해시함수로 낳은 해시값을 인덱스화 하여 데이터 저장
      • 다른 키를 넣었는데 똑같은 해시값이 나오면 같은 인덱스 위치를 가르키게 되고, 데이터가 있다면 데이터가 저장된 버킷이 다음 노드를 가르키게 함. → 계속해서 새로운 노드를 연결하는 것임
      • chaining 방식으로 해시충돌 회피할 경우 인덱스 위치를 찾는데 O(1)의 시간복잡도가 걸린다 하더라고, 인덱스의 위치에서 값을 찾기 위해 리스트를 탐색하는 과정을 거쳐야 함. 최악의 경우 O(N)의 시간복잡도.
      • 리스트 대신 tree라는 자료구조를 사용함
    • Open Addressing
      • 충돌이 발생할 경우 다른 버킷에 데이터 저장하는 방식
      • 선형 탐색 : 해시 충돌 시 n칸을 건너뛴 다음 버킷에 저장
        • 단순계산, 시간 소요多, 데이터들의 특정 위치 밀집(→ 밀집 될 수록 충돌로 데이터의 위치를 재탐색 하는 일이 많아짐 : 성능 저하) 데이터가 밀집되는 현상 : 클러스터링
        • 클러스터링을 피하기 위해 → 제곱 탐색 : N^2칸을 건너뛰어 저장⇒ 이중 해시 라는 방법이 나옴 : 해시 값에 다른 해시 함수를 한번 더 적용
          • Hashfunction1() : 최초의 해시 값을 구하는 함수
          • Hashfunction2() : 충돌이 발생했을 때 돌리는 해시함수
            • 충돌이 발생했을 때 몇 칸을 이동할지 이 해쉬 함수를 통해 구하게 됨
            • 최초의 해시값이 같아도 이동 폭이 달라 클러스터링 문제 해결 가능
        • ⇒ Ex) 1, 4, 9, 16, ... → But, 처음 해시함수를 통해 나온 해시값이 동일하다면 마찬가지로 건너뛴 칸의 갯수도 똑같음
  • 비둘기 집 원리
    • N+1개 물건을 N개의 상자에 넣을때 하나의 상자는 두개 이상의 물건이 들어있음
    • 해시테이블은 인덱스의 수가 한정되어 있지만 키 값은 훨씬 많음
  • Birthday Problem
    • N명이 모였을 때 생일이 같은 두 명이 존재할 확률
    • 수학적 확률로 계산했을 때 23명만 모여도 50.7% 존재
    • 50명인 경우 97%

1. 이진 탐색(Binary Search)
   1. 오름차순으로 정렬되어 있는 리스트에서 특정 값의 인덱스를 찾는 알고리즘
   2. 속도가 빠름 (시간복잡도 O(logN)) //N=100 일때 logN=6.64
   3. 정렬된 리스트에서만 사용 가능

정렬(Sort)

• 안정 정렬 vs 불안정 정렬 : 중복된 값의 순서 보장 여부
  • 순서가 보장 되면 안정정렬(STABLE)
  • 순서가 보장 되지 않으면 불안정 정렬(UNSTABLE)
• In-place 정렬 vs Out-of-place 정렬
  • 원본 데이터 내 정렬 : In-place 정렬
  • 원본 데이터가 아닌 새로운 배열로 정렬 : Out-of-place 정렬

1. 버블 정렬(Bubble Sort)

   1. 인접한 두 elements를 비교하고 정렬되어 있지 않다면 두 elements의 위치를 바꿔줌
   2. 정렬이 완료된 elements를 제외하고 반복 수행
   3. (n-1)+(n-2)+(n-3)+...+2+1=n(n-1)/2
   4. 시간 복잡도O(N^2)
   5. 단순하고 직관적, 생김새는 거품 같다고 하여 버블

2. 삽입 정렬(Insertion Sort)

   1. 리스트의 앞에서부터 이미 정렬된 서브 리스트의 값들과 비교를 통해 자신의 위치에 값을 삽입
   2. 서브 리스트는 정렬이 되어 있으니 삽입 되어야 할 위치가 정해져 있을 것
   3. 사이즈가 1인 배열이 있다면 여기서는 어떤 값이 들어 있어도 정렬 되어 있는 것 → 여기에서부터 출발하게 됨
   4. 리스트에서 가장 앞에있는 하나의 원소를 이미 정렬된 서브 리스트로 보고 정렬 시작
   5. 실질적으로 리스트에 두 번째 값부터 정렬 시작
   6. 안정 정렬이며 단순하다
   7. 데이터의 이동이 많음. But, 리스트 내의 데이터가 어느정도 정렬되어 있으면 이동 횟수 적어짐
   8. 시간 복잡도O(n^2)/최선O(n)/최악O(n^2)

3. 합병 정렬(Merge Sort)

   1. 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법
   2. 합병 정렬은 다음의 단계들로 이루어진다.
   • 분할(Divide): 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다.
   • 정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출 을 이용하여 다시 분할 정복 방법을 적용한다.
   • 결합(Combine): 정렬된 부분 배열들을 하나의 배열에 합병한다.
   3. 보통 재귀함수를 통해 구현
   4. 시간 복잡도O(NlogN)

4. 퀵 정렬(Quick Sort)

   1. 하드웨어 특성 때문에 더 빠름 : 참조 지역성 원리
   2. 알고리즘 특성 상 동일한 배열 내에서 자리를 이동 시킴 → 인접한 데이터들 사이의 이동이 발생함. ⇒ 제일 처음 배열에 접근 할 때만 실제 메모리에서 가져오고 이후에는 캐시로 접근.
   3. 한번 결정된 pivot 값은 이후의 연산에서 제외 : 분할이 될 수록 계산해야 할 데이터의 수가 줄어듦 → 정렬 속도 줄여줌
   4. 추가 메모리 공간 필요없음
   5. Divide and conquer
   6. 평균 O(NlogN) / 최악 O(N^2) : pivot값이 리스트의 최소값이나 최대값이면 효율을 낼 수 없음
   7. pivot값을 고를 때 후보를 두고 가장 중간 값을 사용하는 알고리즘을 사용하기도 함
      → Median of Three

프로그램은 CPU에 의해 실행 → 실행에 필요한 데이터는 메모리에 있음 → CPU 메모리에 접근하는데 그 전에 캐시공간 먼저 탐색 → 데이터가 있다면 캐시공간에서 데이터를 가져옴 → 아니면 메모리로

• 보조배열 : 메인메모리에 생성 됨
• 퀵 정렬 : 제일 처음 제외 모두 캐시공간

QUICK SORT

1. pivot값을 정하는 것 부터 시작(가장 앞, 뒤 원소 상관없음)
2. pivot값 기준 원소 재배치 → 왼쪽은 pivot보다 작은 값, 우측은 pivot보다 큰 값
3. 각각 서브리스트가 생성 → pivot값 정해주기 시작
4. 이후 다시 원소 재배치 이루어짐