Sorting

A-Z까지 정렬하는 것

버블 정렬

인접한 원소끼리 비교하여 교환하는 방식
1. 배열의 2개를 선택.
2. 왼쪽이 오른쪽보다 크면 오른쪽으로 변경

• 배열의 모든 값을 비교해야함

선택 정렬

최솟값을 찾아서 맨 앞으로 이동하는 방식

• 전체를 회전하지 않음
• 이중 for문을 사용하여 작은 값을 찾고 비교값과 위치를 바꾼다
• 버블 정렬과 다르기 선택정렬에서는 매번 사이클마다 1번씩만 바꾸면 된다
  
• 하지만 시간복잡도는 버블정렬과 똑같다

삽입 정렬

앞에서부터 차례대로 이미 정렬된 부분과 비교하여 교환하는 방식

• 선택정렬보다 빠르다
• 필요한 아이템만 비교하여 자리를 바꾼다
• 삽입 정렬이 선택정렬보다 빨라도, 버블정렬보다 빨라도 시간 복잡도는 동일하다
  

• 모두 시간 복잡도는 O(n²)
  선택 정렬과 삽입 정렬은 사용할 메모리가 제한적인 경우에 사용하면 좋다
• 모두 동일한 시간대이지만 최고의 시나리오의 경우에서 삽입 정렬의 경우 O(n)이 발생한다

---

1. 선택 정렬

2. 버블 정렬

3. 삽입 정렬

4. LRU 캐시

5. 중복 확인

6. 장난꾸러기

7. 좌표정렬

8. 이분검색

9. 뮤직비디오

10. 마구간 정하기

참고자료
https://velog.io/@minji0801/버블정렬-vs-선택정렬-vs-삽입정렬-차이-제대로-알고가자