Algorithm

#Python #Java

Sort Algorithm 정렬 알고리즘

: 사물 특성 기준으로 재배치, 오름차순/내림차순

종류

- (code, web) 버킷 정렬 Bucket Sort

: 자료를 버킷이라는 단위 기억 장소에 정렬 하고 key 값에 따라 다시 정렬
-> 단점. 데이터가 [1, 1000] 개 일때도 1000개의 장소가 필요함

- (code) 기수 정렬 Radix Sort

: 일의 자릿수 부터 각 자릿수별 버킷 정렬 반복 수행(버킷 한계 극복)

- (code) 선택 정렬 Selection Sort

: 가장 작은 데이터와 가장 앞에 데이터를 교환 하는 과정을 반복
-> 책오류 : 책에서는 작은 수를 앞으로 오게 하는것이 아닌 큰수를 뒤로 보냄, 작은 수를 앞으로 보내는 코드로 수정

- (code) 교환 정렬 Exchange Sort

: 작은 것 부터 큰 순서로 정렬 할 경우, 작은 키를 찾아 앞으로 이동, 한번 완전히 뒤로 갔다가 다시 앞으로

- (code) 삽입 정렬 Insert Sort

: 앞에서 부터 값이 작은것 순으로 정렬 할 수 있도록 정렬, 주변값과 비교해 앞으로 놓는 방법

- (code, web) 셀 정렬 Shell Sort

: 데이터를 2개의 데이터로 분할해 정렬 수행 후, 데이터를 3개의 무리로 나누어 수행. 다음으로 삽입 정렬 수행
-> 그룹안에서 쉘 정렬 수행 후 마지막에 삽입 정렬 사용, 삽입 정렬 알고리즘 속도 보완

• 삽입 정렬이 어느정도 정렬된 자료에서 빠르게 정렬을 수행한다는 것을 이용한 알고리즘
  참고 : https://good-potato.tistory.com/40

- 병합 정렬 Merger Sort

: 데이터를 분할한 다음 계산하고 나중에 합치는 방법 - 2차 병합 정렬 알고리즘 : 이미 정렬된 데이터 무리를 하나로 정렬하기 위한 일

- (code) 퀵 정렬 Quick Sort

: 중앙 값 정렬 방식 확장, 데이터의 가장 앞에 있는 갑을 중심으로 그 값보다 작은 것은 앞에 큰것을 뒤에 위치하도록 하며 알맞을 자리에
참고 : https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

- 힙 정렬 Heap Sort

: 힙 개념 이용, 최상위 데이터를 가장 큰 수로 설정해 이를 빼고 힙ㅂ을 구성 이 방법을 반복

알고리즘 선택 기준

상황	정렬 알고리즘
항목이 적음	삽입 정렬
항목이 대부분 정렬	삽입 정렬
최저 상황 고려	힙
평균 정렬 결과	퀵(빠른) 정렬
항목을 조밀한 모집단에서 가져왔을 경우	버킷 정렬
짧은 코드 선호	삽입 정렬

• 정렬 알고리즘은 표준라이브러리로 제공되고 있음

시간 복잡도

검색 알고리즘

- (code) 순차 검색

  : 데이터를 처음부터 검색하는 방법

- 이진 검색

  : 정리된 데이터를 대상으로 중앙값 이용

- (code) 문자열 검색

  : 문자열에서 찾고자 하는 문자열이 있을 때, 해당 문자열 위치 반환

- KMP 검색 알고리즘을 사용한 문자열 검색

- BM 검색 알고리즘을 사용한 문자열 검색

기타 알고리즘