탐색

선형 탐색(linear search)

• 원하는 원소가 발견될 때까지 처음부터 마지막까지 차례대로 탐색
• 정확하지만 비효율적
• 자료가 정렬되어 있지 않거나 그 어떤 정보도 없이 하나씩 찾아야 하는 경우에 유용

이진 탐색(binary search)

• 정렬이 되었을때 log n

정렬(sort)

• 비교 횟수가 많다는건 컴퓨터 자원(메모리 등)을 더 많이 필요로 한다는 것
• 기술이 발전함에 따라 완화됨

버블 정렬(bubble sort)

• 두 개의 인접한 자료 값을 비교하면서 위치를 교환하는 정렬
• n개의 원소에 대해서 버블 벙렬을 한번 수행할 때마다 n번째의 원소가 제 자리를 찾게 됨

선택 정렬(selection sort)

• 배열 안의 자료 중 가장 작은 수를 찾아 첫 번째 위치의 수와 교환해주는 방식의 정렬
• 교환 횟수를 최소화하는 반면 각 자료를 비교하는 횟수는 증가

삽입 정렬(insertion sort)

• 정렬되지 않은 부분의 자료가 정렬된 부분의 자리로 삽입되는 형태의 정렬
• 자료의 양이 적을 때 성능이 우수, 이미 정렬이 되어 있는 경우 효율.
• 이미 정렬된 자료에 새로운 자료를 삽입해야 하는 경우가 발생하면, 정렬된 자료들이 자리를 이동해야 하므로 안전성이 낮음

합병 정렬(merge sort)

• 원소가 한 개가 될 때까지 계속해서 반으로 나누다가 다시 합쳐나가며 정렬하는 방식(O(n log n)) 합쳐지는 중간 단계의 배열을 임시로 저장하고 함수가 종료될 때까지 기억하고 있어야 하기 때문에 메모리 사용이 늘어난다

시간 복잡도

• Big O : 최악의 경우
• Big Ω : 최선의 경우
• Big θ : 최악과 최선이 같은 경우