Algorithms (Sorting & Hash)

---

1. Sorting

• Selection

• Insertion

• Shell

• Merge

• Count

• Radix

---

2. Hash

해쉬의 confilct대처방식과 주소매핑과정에 따른 정책

• 선형오버플로우

• 더블해시

• 뻐꾸기해시

---

3. 파일여는법

Selection Sort

최소값을 가지고 정렬한다.

1. 0~n까지 요소 중 최소값을 찾고 0번째에 넣는다
2. 1~n까지 요소 중 최소값을 찾고 1번쨰에 넣는다
3. 배열이 다 할 때까지 반복한다.

Insertion Sort

그룹을 만들어 그룹 내에서 정렬한다
그룹은 갈수록 커지며 그룹 내의 비교 교환은 인자 내의 가장 큰 인자부터 구현하였다.

[ 8 5 6 2 4 ] 라고 가정하자

1. [0 , 1] 인자로 그룹을 만들어 2개의 값을 비교하여 정렬한다.

   • [ 8 5 6 2 4 ] -> [ 5 8 6 2 4 ]

2. [0 , 2] 0~2까지의 인자로 그룹을 만들어 비교

   • [ 5 8 6 2 4 ] -> [ 5 6 8 2 4 ]

3. [0 , 3] 0~3까지의 인자로 그룹을 만들어 비교

   • [ 5 6 8 2 4 ] -> [ 5 6 2 8 4 ] -> [ 5 2 6 8 4 ] -> [ 2 5 6 8 4 ]

• 삽입정렬 : 1주차 2회 26:00

Shell Sort

삽입정렬의 친구. 삽입정렬은 바로 앞의 원소와 비교했기 때문에 가장 작은 원소가 마지막에 있을 경우 지연된다.

h개만큼 떨어진 원소들과 비교 후 정렬한다. 삽입정렬에서 간격이 생긴 정렬이라고 생각하자.

간격은 h = 3*h + 1로 일반적으로 지정된다.

1. h를 구하고 h는 가장 큰 값을 기준으로 정렬한다. ( 1 4 13 53 이었다면 53부터)

2. 교환할 인자들이 h만큼 떨어져 있는 것 빼곤 삽입정렬과 같다.

3. 부분배열을 형성하고 부분배열은 처음인자와 h만큼 떨어져있는 원소들의 집합이다.

4. 부분배열 내에서의 비교는 마지막 원소부터 처음원소까지 비교한다.

• Shell sort Feedback

  • Shell sorting 만드는데 하루하고 2시간이 더 걸렸다.
  • 초기단계
    • NullPoint/IndexboundOut이 나를 괴롭혔다
    • 코드를 작성하다 보니 삽입정렬이 뭔지 헷갈리게 되었다
    • 결국, 나만의 새로운 소팅방식을 만들게됨.
  • 중반단계
    • 나의 잘못된 점을 파악하고 코드를 다시 짜기로 결정.
    • 부분배열을 만들어 그 배열 내에서 비교를 해야한다는 걸 깨달음
  • 후반단계
    • 부분배열을 만드는 for문
    • 배열내 마지막 인자부터 시작하는 변수를 뭐와 관련시킬지
    • 부분배열 내에서는 마지막 인자부터 처음인자까지 모두 비교하면서 진행하는 for문
    • 위의 3가지가 Shell sort의 제일 큰 장애물 부분이었다.
  • 교훈 : 생각을 한 다음에 Eclips를 키자(손부터 먼저 움직였기 때문에 더욱 헤맸던 걸로 판단한다)

• 삽입정렬과 같지만 h가 있고 구간별로 정렬진행

Merge-Sort

병합정렬으로 두개의 정렬된 배열이 있고, 그 배열들을 정렬한다.

Count-Sort

값들의 비교로 인한 정렬이 아닌, KEY값으로 정렬하는 알고리즘.

• [2 4 1 1 2 3 ] 이 있다고 하자.

0. 주어진 배열의 최대값을 찾고, b[max] 배열을 생성한다
1. 각각의 인덱스를 카운트한다
   • 0:0개 / 1:2개 / 2:2개 / 3:1개 / 4:1개
   • b [ 0 2 2 1 1 ]
2. b배열의 누적합의 배열을 하나 만든다
   • c [ 0 2 4 5 6 ]
3. 주어진 배열의 마지막 인자부터 시작해 해당 a배열의 마지막 인덱스의 값에 해당하는 누적배열을 참조한다. - 주어진 배열 [2 4 1 1 2 3] 마지막 요소 3부터 접근해 c배열의 3이 있는 인덱스 = 5이고 - 주어진 배열과 같은 크기의 배열에 5번째 인덱스에 3을 넣고 3의 누적카운트에는 --한다. - 위의 과정을 반복한다
   

• Count Sort

Radix-Sort

2가지 기준으로 정렬방식이 나뉘어지는데, 2번의 방식이 별도의 정렬알고리즘을 사용하지 않아도 되므로 LSD로 한다.

1. MSD (높은 자리 우선정렬)
2. LSD (낮은 자리 우선정렬)
   • K2기준으로 정렬 (K2는 1의자리 숫자부터 10의자리 100의자리 순으로비교 즉, K2 = 낮은자리)
   • 1의자리 -> 10의자리 -> 100의자리 ...
     • 1의자리
       • 1의자리 숫자 카운팅해서 배열에 넣기
       • 카운팅한 배열 누적합 배열생성
       • 원배열의 마지막인덱스부터 처음까지 누적배열과 비교해서 정렬
     • 10의자리
       • 10의자리 숫자 카운팅해서 배열에 넣기
       • 카운팅한 배열 누적합 배열생성
       • 원배열의 마지막인덱스부터 처음까지 누적배열과 비교해서 정렬
     • 100의자리
       • 100의자리 숫자 카운팅해서 배열에 넣기
       • 카운팅한 배열 누적합 배열생성
       • 원배열의 마지막인덱스부터 처음까지 누적배열과 비교해서 정렬

• Radix Sort

---

2. Hash

해시를 사용하면 무작위 데이터를 삽입 삭제할 때 시간복잡도 O(1)로 처리할 수 있다.
하지만 해시테이블 주소매핑 과정 시 충돌이 발생하면 검색시간에 영향을 미칠 수 있고 더 나아가 테이블 적재도가 높아지게 되면 rehash를 해야하는 데 이때 비용이 크기 때문에 가급적이면 중복방지에 신경을 써야한다.

Linear Probing

• 주소매핑과정에서 Overflow가 발생하면 그 다음 주소에 매핑하는 방식.
• 데이터의 Clustering 현상이 발생한다.
  
  

Double Hashing

• 주소매핑과정시 주소중복을 막기위해 2개의 해시함수를 사용한다.
• 삭제과정 구현이 어렵다
  
  

Cuckoo Hashing

• 주소중복이 있을 때 자리를 뺏고 뺏는 형태의 해시매핑방식.
• 뺏고 뺏다보면 무한루프가 발생하는 데, 이때 rehash를 한다.

---

파일사용법

1. 압축을 푼다
2. src폴더 > sort or hash폴더에서 java file을 열고 실행한다.