정렬 알고리즘

정렬 알고리즘

: 데이터를 일정한 순서로 배치하는 것 

1. 버블 정렬

for 문을 두번 사용해서 시간복잡도는 O(n^2)

배우기가 간단함

 

2. 삽입정렬

버블정렬보다는 효율적일지도?

-> 어느정도 정렬이 되어있을 때의 시간복잡도가 O(n)으로 상당히 효율적임

3. 병합정렬 (Merge sort)

리스트를 계속해서 반으로 나눠 요소가 한 개뿐인 리스트로만 남았을 때, 이들을 올바른 순서대로 다시 합치는 재귀정렬 알고리즘.

 

🔶 O(logN) == O(log₂N)을 의미한다. 

O(n * log(n)) 의 시간복잡도

이진 검색이 정확히 O(logN) 알고리즘 방식으로 동작한다.

이진 검색을 빅 오 표기법의 관점에서 어떻게 설명할까?

배열의 크기가 3일 때 이진 검색은 2단계
배열의 크기가 7일 때 이진 검색은 3단계
배열의 크기가 15일 때 이진 검색은 4단계
배열의 크기가 100일때 이진 검색은 7단계
배열의 크기가 10,000일때 이진 검색은 13단계
배열의 크기가 1,000,000일때 이진 검색은 20단계