기억보단 기록을

같은 숫자내에서의 인덱스에 대해 , 정렬과정에서 인덱스가 바뀌면 unstable, 그렇지않으면 stable.

해쉬(Hash) : 자료의 검색과 저장을 빠르고 효과적으로 진행하기위한 데이터를 다루는 기법

해시함수(Hash function):  자료를 해쉬테이블에 저장할때, value 값을 특정 key로 치환하여 저장. 이때 쓰이는 함수를 해쉬함수라고 하고 division, mid-square, folding, integer 등의 여러 기법이 존재

충돌(collision) : 결국 해쉬테이블은 자료를 인덱스로 치환하여 저장하게되는데, 이 과정에서 다른해쉬값이 같은인덱스로 치환된다면, 인덱스가 겹치게 되는데 이를 충돌이라고 한다.

충돌해결법

1.선형조사법

2.이차조사법

선형조사법이랑 구현은 비슷하지만, 특정영역에 원소가 몰릴경우 그 영역을 더 빨리 벗어날 수 있음

3.랜덤조사법

뭐 이런것도 있나보다.

난수발생시켜서 ran배열에 저장후, s(i)값으로 이용한다.

4.체이닝

그냥 연결리스트형식으로써 같은인덱스에 때려박음

시간복잡도로 nlogn 을 가지고있는 알고리즘이다.

maxheap을 구성해서 가장 위에있는 노드를 뽑아내는 식인데, maxheap을 구성하는단계 logn, 총 n번 반복해서 nlogn 이다. 

단계 손으로 그리기가 과제였음;;;

Radix sort란 가장 낮은 자릿수부터 해서 정렬해나간다는 원리이다. 다른정렬과 다르게 별도로 비교연산이 없고, 

따라서 시간복잡도는 굉장히 빠른 O(N)이다.

최대자릿수 까지 N번 탐색을 한다고 하면

즉, 10개의 값이 있고 최대자릿수가 3이라고 가정했을 때

일의 자릿수를 찾는 과정에서 = 10번 탐색

십의 자릿수를 찾는 과정에서 = 10번 탐색

백의 자릿수를 찾는 과정에서 = 10번 탐색

즉 3 x 10 번 탐색을 하게된다. 이를 식으로 써보면 K * N번 탐색을 하는 것이고 이를 빅오 표기법으로 나타내면 O(KN)이 된다.

하지만 자릿수마다 정렬을 하기때문에 정렬된 수를 큐에 담고 또 빼내는 과정해서 추가적인 메모리소요가 많다.

본래있던 기수정렬의 출력방식을 조금 응용해서  link를 통한 출력방식을 사용하였다.

원래는 자릿수에 맞는 인덱스의 큐에 들어가서 뺴낼때 하나씩 빼내는것이 본래였다면, link를 통해 간단히 다음큐의 front만 가리킨다면, 쉽게 출력을 할 수 있을 것이다.

윗부분에선 먼저 링크배열은 바로다음인덱스를 가리키도록 초기화시키고,

digit 함수로 끝자리를 검사해 bin에 담아 bin 인덱스의 큐에 삽입한다.

큐는 rear와 front만 존재하게 되는데, 같은 자릿수가 2개이상 들어올 경우 그 사이의 링크는 link[rear[bin]] = current를 통해 링크함수로 이어놓는다. 따라서 큐는 front와 rear 둘의 성분만 가지고있어도 된다.

digit은 자릿수에 맞는 값을 반환해준다.

이 코드부분은 실질적으로 link배열을 통해 큐안에서 rear와 다음인덱스 front를 이어주는 역할을 한다.

<참고>

퀵정렬은 '피벗(pivot)'이라는 기준점을 두어 왼쪽서부터는 피벗보다 큰 원소를 고르고 오른쪽서부터는 피벗보다 작은 원소를 골라 교체해 나가는 원리이다.

이렇게 교체가 되면 어느순간 왼쪽서부터온 피벗보다 큰 원소와 오른쪽서부터온 피벗보다 작은원소의 위치가 뒤바뀌게 되는데 이를 기준으로 분할하여 다시 퀵정렬을 수행하게 된다.

*피벗(위키백과) : 선형대수학에서 피벗(pivot) 또는 피벗 성분(pivot entry,pivot element)는 특정 계산을 수행하기 위한 임의의 알고리즘 (예 : 가우스 소거법, 단순 알고리즘 등)에 의해 먼저 선택된 행렬의 성분(항,원소)이다.