정렬 알고리즘 - 노마드 코더

Big O는 알고리즘의 퍼포먼스를 이해하기 쉽고 효율적으로 작성하는 방법
하지만 항상 Big O가 모든 알고리즘을 완벽하게 설명하는 건 아냐

오늘 설명하는 알고리즘들은 모두 같은 BigO를 가지지만
각각의 퍼포먼스는 매우 다름
일단 Sorting이 뭔지 설명
뭔가 정리하는 것 
A to Z로 사전처럼 정렬하거나
큰 수에서 작은 수 기준으로 정렬할 수 있다.
이진 검색처럼 빠른 알고리즘을 사용하려면 일단 먼저 배열 정렬을 해야해
Bubble Sort(버블정렬), Selection Sort(선택정렬), Insertion Sort(삽입정렬) 
오늘은 쉬워 실제로 사람들이 정렬하는 방법과도 유사
시간복잡도 계산법도 쉬움

<버블 정렬>
사실 더 좋은 알고리즘이 많고 그렇게 좋은 알고리즘은 아니라서 자주 사용되진 않아
그래도 버블정렬로 시작하는이유는 이해하기 쉽다
정렬입문으로 좋은 토픽  
배열의 2개의 아이템을 선택하고 비교할 것
왼쪽이 오른쪽보다 크면 교환. 오른쪽으로 이동해서 해당 프로세스를 반복
버블정렬의 시간복잡도는 (n-1)(n-2)(n-3)... => O(n²)

<선택 정렬>
가장 작은 숫자 찾고 위치에 맞게 이동을 반복
비교는 (n-1)
하지만 N번의 스왑을 하지 않는다 싸이클 마다 1번의 스왑만 하면 됨
즉 선택정렬이 버블정렬보다 훨~~씬 낫지
선택정렬이 버블정렬보다 2배 더 빠를 수도 있음에 불구하고
선택정렬의 시간복잡도도 역시 O(N²)

<삽입정렬>
삽입정렬은 선택정렬보다 빨라
왜냐면 필요한아이템만 스캔
선택정렬은 전체 모든 아이템을 스캔
하지만 선택정렬보다 더 빠라도 시간복잡도는 동일하게 O(N²)

3개가 전부 매우 다른데 시간복잡도는 동일 BigO는 엉터리?
이 경우, 최악의 시나리오 보지 말고 평균 시나리오를 봐야함.
최악/최고의 케이스는 자주 발생x
대부분 평균 
평균적으로 최악의 경우 2차 시간복잡도를 갖고 있다.
그러나 삽입정렬의 경우 O(N)이 최고의 시나리오에서 발생
O(N)은 이차 시간복잡도와 비교해선 최고의 알고리즘
보다시피 디테일이 중요
동일한 시간복잡도를 갖고 있어도 매우매우 다를 수 있다
삽입, 선택정렬은 작은 DB기준으로 훌륭한 알고리즘
물론 데이터가 커지면 커질수록 좀 느려지겠지만
그럼 다른 알고리즘을 살펴봐야지 Quick Sort, Merge Sort와 같은(다음 영상)

https://www.youtube.com/watch?v=Bor_CRWEIXo&list=PL7jH19IHhOLMdHvl3KBfFI70r9P0lkJwL&index=5