퀵소트
i+1 = 피봇의 위치
파티션한번 돌때마다 피봇의 위치가 확정됨 - 왼쪽은 자기보다 작은거 오른쪽은 자기보다 큰거
그리고 return하는 건 피봇의 위치
해싱
데이터 특성이 잘 짜여진 해시함수를 통해 해시 테이블에 조정된다.
자원을 이용하여 속도를 높인다.
충돌대처
- chaining 해당 인덱스에 값이 이미 차있을때 리스트같은 자료구조를 통해 해당 값 뒤에 붙인다.
- Linear Probing 이어 붙이지 않고 남아있는 테이블 자리에다가 데이터를 넣는다.
- Resizing 테이블의 크기를 늘리고 다시 데이터들을 해시함수로 보내 다시 예쁘게 정렬한다.
단순 선택 정렬
제일 작은 값을 선택해 정렬 되지 않은 맨 앞 요소와 바꾼다.
- 미정렬된 부분 최소요소의 인덱스를 먼저 설정해놓고 for문 돌려서 최소값을 가진 인덱스를 찾아서 세팅한다.
- 미정렬된 인덱스(i)와 최소값을 가진 인덱스(min)을 swap한다.
단순 삽입 정렬 : 아직 정렬되지 않은 부분의 첫번째 요소를 정렬된 부분의 알맞은 위치에 삽입한다.
단순 삽입 정렬은 2번째 요소(i=1)부터 선택하여 진행한다.
배열의 요소를 알맞은 위치에 삽입한다??
- 아직 정렬되지 않은 부분의 첫번째 요소값을 tmp변수에 설정
- 정렬되어있는 요소중에서 tmp보다 작은 값을 만날때까지 요소값들을 오른쪽으로 옮긴다.
- 멈춰진 요소인덱스에 tmp변수 대입
요소의 비교 횟수와 교환 횟수는 n^2/2회입니다.
셸 정렬
정렬할 배열의 요소를 그룹으로 나눠 각 그룹별로 단순 삽입 정렬을 수행하고, 그 그룹을 합치면서 정렬을 반복하여 요소의 이동 횟수를 줄이는 방법
셸 정렬 과정에서 수행하는 각각의 정렬을 'h-정렬'이라고 한다.
어려워...ㅠㅠ
안녕하세요