Sort

21년, 노션에 정리했던 노마드코더 알고리즘 강의 요약노트

✔️ 버블정렬 : O(n^2)

• 바로 옆이랑 비교해서 작으면 스왑

✔️ 선택정렬 : O(n^2)

• 전체 아이템 중 가장 작은 아이템 위치 변수에 저장. 차차 비교하다가 젤 작은 위치에 도착하면 0번자리랑 바꿔주고 사이클 끝. 그 다음 사이클은 정렬된거 빼고! 또 젤 작은거 위치 찾고, 비교하고 바꿔주고 반복함
• 버블과 달리 최악의 경우 N번의 스왑을 하지 않음

✔️ 삽입정렬 : O(n^2)

• 1번자리에서 시작. 왼쪽에 더 작은수가 있나보고 크면 바꿔줌. (1번 사이클)
• 2번자리보고 왼쪽이랑 비교. 작으면 냅두고 크면 바꿔줌. 바꾼애가 또 왼쪽으로 비교비교 하면서 자리 바꿈
• 삽입정렬은 선택정렬보다 빠름
• 삽입정렬은 필요한 아이템만 스캔, 선택정렬은 모든 아이템 스캔

Big O가 똑같은 이유 >> 평균시나리오를 봐야함 (최악/최고의 시나리오는 드뭄)

선택, 삽입은 작은 DB에선 훌륭한 알고리즘..☆