📌버블 정렬(Bubble sort)

• 정렬을 공부할 때 가장 이해하기 쉽다.
• 좋은 알고리즘은 아니어서 실제로는 많이 사용하지 않는다.

🔎버블 정렬 과정

1. 첫번째 사이클

• 앞에서부터 2칸씩 서로 비교해서 큰 수를 뒤로 보낸다.
• 결과적으로 마지막 자리에 가장 큰 수가 위치한다.

2. 마지막 위치에서 1개를 제외하고 두번째 사이클 진행

3. 마지막 위치에서 2개를 제외하고 3번째 사이클 진행

4. 이 과정을 끝까지 진행하면 숫자가 오름차순으로 정렬된다.

⏱️버블 정렬 시간 복잡도

• O(N$^2$)
  

📌선택 정렬(Slection sort)

• 전체 데이터 중에서 가장 작은 데이터 또는 가장 큰 데이터의 위치를 따로 기억하는 방식으로 작업 진행

🔎선택 정렬 과정

1. 첫번째 사이클

• 1) 맨 처음부터 시작해서 가장 작은 데이터가 있는 위치로 0을 보관한다.

• 2) 첫번째 숫자와 그 다음 숫자를 비교해서 더 작은 수의 위치를 보관한다.
  → 끝까지 이동했을 때 가장 작은 데이터의 위치값(인덱스)이 저장되어 있다.

• 3) 가장 작은 데이터를 0번째 위치에 있는 데이터와 교환한다.

2. 0번째 위치를 제외하고 1번째 위치부터 두번째 사이클 진행

3. 정렬이 될 때까지 확정된 위치를 제외하고 사이클 진행

⏱️선택 정렬 시간 복잡도

• O(N$^2$)
• 버블 정렬과 시간 복잡도가 같지만,
• 자리를 바꾸는 연산을 사이클당 1번씩만 하기 때문에 훨씬 효율적이다.

📌삽입 정렬(Insertion sort)

🔎삽입 정렬 과정

1. 앞에 있는 데이터를 보고 비교해서 더 작은 데이터를 큰 데이터 앞쪽으로 밀어넣는다.
⭐ 포인트는 교환이 아니라 밀어 넣음

2. 밀어 넣기가 끝나면 한 사이클 끝! 다음 사이클을 진행한다.

3. 배열이 정렬될 때까지 진행한다.

⏱️삽입 정렬 시간 복잡도

• O(N$^2$)
• 시간 복잡도가 같지만,
• 삽입 정렬이 버블 정렬, 선택 정렬보다 빠르다.

❓시간 복잡도가 같은데 속도 차이가 나는 이유

• 시간 복잡도가 같다 = 시간 복잡도를 단순히 측정했을 때 같다
• 알고리즘은 초기 데이터 상태에 따라 처리 속도가 달라진다.

⭐ 기계적으로 측정한 시간 복잡도는 같아도 평균적으로 빠른 알고리즘이 있을 수 있다.