[2주차 TIL] KnockOn Bootcamp 정렬 알고리즘

💡 정렬 알고리즘이란?

어떤 데이터가 주어졌을 때 특정한 기준에 따라 순서대로 나열하는 방법을 말한다.

대표적인 정렬 알고리즘으로는 버블 정렬, 선택 정렬, 삽입 정렬이 있다.

---

🔎 버블 정렬 (Bubble Sort)

시간 복잡도 : O(n²) 

 

인접한 두 값을 비교해 큰 값을 뒤로 보내 정렬하는 방법이다.

정렬을 한번 진행할 때마다 뒤에서부터 하나씩 정렬되는 모습이 마치 거품이 올라는 모습같아 버블 정렬이라는 이름이 붙었다.

구현 난이도는 쉬우나 매번 값을 비교해서 정렬하므로 시간이 오래걸리는 편이다. 다만 정렬이 된 데이터에서는 한번의 순회로 정렬을 완료하는 성능을 보여준다.

 

버블 정렬 과정

---

🔎 선택 정렬 (Selection Sort)

시간 복잡도 : O(n²)

 

데이터 전체에서 가장 작은 것을 찾아 차례로 맨 앞에 정렬하는 방법이다.

어떻게 정렬이 되어있든 (n(n-1))/2에 비례하는 시간이 걸리며 버블 정렬보다는 2배 정도 빠르다.

 

선택 정렬 과정

---

🔎 삽입 정렬 (Insertion Sort)

시간 복잡도 : O(n²)

 

앞에서부터 값을 하나씩 정렬된 부분에 삽입하면서 정렬하는 방법이다.

데이터의 양이 적을수록 높은 성능을 보여준다.

 

삽입 정렬 과정