알고리즘 (algorithm)

알고리즘은 시간 복잡도와 공간 복잡도로 나눔.

공간 복잡도는 필요한 하드디스크 기준이므로 현대에는 크게 신경쓰지 않음.

시간 복잡도는 입력 값에 따른 연산 횟수를 표현하므로 시간 복잡도 함수의 최고 차항 만으로 성능을 표현. (최고 차항을 제외한 다른 값들은 비율상 미비함으로)

빅오 표기법은 시간 복잡도 함수의 상한을 표현. (최소한 빅오 성능 이상을 보장)

오름차순 정렬 : 작은 키 값부터 올라간다.

내림차순 정렬 : 큰 키 값부터 내려온다.

정렬은 비교 - 이동 과정을 거친다.

비교 연산 성능이 같더라도 비교 후 이동해야 하는 자료의 크기가 크다면 이동이 적은 정렬이 성능이 좋다.

자료가 저장된 상태에 따라 평균 효율성과 최악 효율성에 차이가 있다면 이 또한 알고리즘 선택의 기준이 된다.

한번의 정렬시 기존 자료의 순서가 유지되면 안정 정렬

정렬 후 기존 자료의 순서가 뒤바뀌면 불안정 정렬

여러 키를 가지고 정렬을 해야할 경우 안정 정렬은 키만 바꾸면서 정렬을 여러번하면 자동으로 다중키 정렬이 된다.

불안정 정렬은 자료의 순서가 유지되지 않으므로 다중 키 정렬시 별도의 비교 로직이 필요하다.

키 값 비교 후 자료 교환 : 선택, 퀵, 버블 정렬

자료를 나누고 병합 : 병합 정렬

키 값을 여러 부분집합으로 분배하고 이를 이용해 정렬 : 기수 정렬

키 값을 비교 후 삽입 : 삽입, 셀 정렬

트리같은 특정 자료구조를 통한 정렬 : 히프 정렬

메모리에 자료를 모두 로딩 후 정렬하는 내부 정렬

보조 기억 장치에서 정렬을 수행하는 외부 정렬

내부 정렬은 빠르지만, 한번에 로딩 불가능한 대용량은 정렬 불가능

외부 정렬은 느리지만, 대용량의 자료를 정렬 가능