[알고리즘] 기본 정렬 (선택정렬, 버블정렬, 삽입정렬)

📝 버블 정렬이란?

요소들이 마치 거품이 일어나듯 연쇄적으로 자기 자리를 찾아간다는 뜻, 매번 연속된 두 개 인덱스를 비교하여 정한 기준의 값을 뒤로 넘겨 정렬하는 방법이다.

🎯 버블 정렬의 특징

• n번째 정렬 회차가 끝나면 뒤에서 n번째 자리의 데이터가 확정
• Big O (시간 복잡도) => Best Case: O(n) / Worst Case: O(n^2)
• 중복 데이터가 있을 경우 데이터의 위치를 교환하지 지나가기 때문에 stable한 정렬
  ✔ stable : 중복 데이터가 있는 경우에 기존 중복 데이터의 순서가 정렬이 다 끝난 이후에도 유지되는 정렬

---

📈 버블 정렬 장점

• 버블 정렬은 in place 알고리즘이기 때문에 메모리가 절약된다.
  ✔ in place : 자료를 정렬할 때 추가적인 메모리 공간이 필요한 것이 아니고 데이터가 저장된 그 공간 내에서 정렬을 한다는 뜻
• 구현하기 매우 쉽다.
• 이미 정렬된 데이터를 순회하는 경우 O(n)번만 순회하면 되기 때문에 정렬 유무를 테스트하는 용도로 사용된다.

📉 버블 정렬 단점

• 자료의 개수가 많아질수록 성능이 매우 떨어진다.
• 주로 알고리즘 교육용을 제외하고는 사용되지 않는다.

---

📝 삽입 정렬이란?

왼쪽에서 오른쪽으로 가면서 각 요소들을 왼쪽 요소들과 비교하여 알맞은 자리에 삽입하는 형식의 정렬 방법이다.

🎯 삽입 정렬의 특징

• Big O (시간 복잡도) => Best Case: O(n) / Worst Case: O(n^2)
• 중복 데이터가 있을 경우 데이터의 위치를 교환하지 지나가기 때문에 stable한 정렬

---

📈 삽입 정렬 장점

• in place 알고리즘이기 때문에 메모리가 절약된다.
• 구현하기 매우 쉽다.
• 정렬 유무를 테스트하는 용도로 사용된다.

📉 삽입 정렬 단점

• 자료의 개수가 많아질수록 성능이 매우 떨어진다.

---

📝 선택 정렬이란?

주어진 리스트 중 최소값을 찾으면 그 값을 맨 앞의 값과 교환하고 맨 앞을 제외하고 다시 순환하면서 최소값을 찾는 정렬 방식이다.

🎯 선택 정렬의 특징

• n번째 회전이 끝날 때마다 앞에서 n번째 데이터의 위치가 정해짐
• Big O (시간복잡도) => Best Case: O(n^2) / Worst Case: O(n^2)
• 데이터가 중복된 경우 위치가 바뀔 수 있기 때문에 Unstable한 정렬

---

📈 선택 정렬 장점

• in place 알고리즘이기 때문에 메모리가 절약된다.
• 알고리즘이 직관적이므로 이해하기 쉽고 구현하기도 매우 쉽다.

📉 선택 정렬 단점

• 최선의 경우에도, 최악의 경우에도 O(n^2)의 시간이 걸리는 만큼 성능이 매우 떨어진다.

---

참고자료

• JavaScript로 버블정렬(bubbleSort) 알고리즘 구현하기