버블 정렬과 선택 정렬

버블 정렬 (Bubble Sort)

• 서로 인접한 두 원소를 비교하며 자리를 변경시키는 알고리즘

시간 복잡도 : N^2

- 기본적인 버블 정렬은 정렬이 되어있든 안되어있든 두개의 원소를 비교하기 때문에

최선, 평균, 최악 모두 시간복잡도가 같다

 

   장점

1. 구현이 간단하다
2. 배열 안에서 교환하는 방식이므로, 별도의 공간이 필요없다
3. 안정 정렬(Stable Sort)이다

   단점

1. 시간복잡도가 항상 N^2이기 때문에 매우 비효율적이다

---

선택 정렬 (Sellection Sort)

• 원소를 넣을 위치를 정해놓고 어떤 원소를 넣을지 선택하는 알고리즘

시간 복잡도 : N^2

- 최선, 평균, 최악 모두 시간복잡도가 같다

 

   장점

1. 구현이 간단하다
2. 배열 안에서 교환하는 방식이므로, 별도의 공간이 필요없다
3. Swap이 많이 일어나야 하는 경우 버블 정렬에 비해 효율적이다

   단점

1. 시간복잡도가 항상 N^2이기 때문에 매우 비효율적이다
2. 불안정 정렬(Unstable Sort)이다

---

안정 정렬 (Stable Sort)

- 중복된 값을 입력 순서와 동일하게 정렬하는 알고리즘 특성

불안정 정렬 (Unstable Sort)

- 중복된 값이 입력 순서와 동일하게 정렬되지 않는 알고리즘 특성

 

참고 - Gyoogle