4. 버블 정렬(Bubble Sort) - O(n2)

이쯤에서 슬슬 앞의 정렬을 까먹은분을 위해 짧막 상식
우리가 배웠던 정렬의 방식을 짧게 설명하고자 한다

1. 계수 정렬
 = 들어온 숫자를 배열로 받아서 들어온 숫자를 카운트하여 정렬
2. 선택 정렬
 = 인덱스의 순서대로 숫자를 지정하며 해당 숫자를 직접 찾아 둘이서 교환
3. 삽입 정렬
 = 뒷자리 숫자와 앞자리 숫자를 비교하고 더 작은 숫자를 비교하고 해당 숫자의 앞자리가 본인보다 작은것을 찾을때 까지 비교한다.

 

과정(우리는 오름차순을 기준으로 한다.)

1. 앞에서부터 현재 원소와 바로 다음의 원소를 비교한다.

2. 현재 원소가 다음 원소보다 크면 원소를 교환한다.

3. 다음 원소로 이동하여 해당 원소와 그 다음 원소를 비교한다.

 

거품 정렬은 정렬규칙이 있다 

총 라운드는 (배열 크기 - 1)번 진행하고

라운드에서 비교 횟수는 (배열 크기 - 라운드 횟수) 만큼 비교한다.

 

코드[ JAVA ] 

구현은 나의 깃허브에 해놓았다 시간이 된다면 보는것을 적극 추천한다

https://github.com/ProblemSolveStudy/Tae_sik/tree/master/Sorts

GitHub - ProblemSolveStudy/Tae_sik

 

거품 정렬의 장단점

 

◐ 장점

 = 추가적인 메모리 소비가 적다.

 = 구현이 매우 간단하다

 = 안정 정렬이다.

 

◑ 단점

 = 다른 정렬 알고리즘에 비해 교환 과정이 길다. 즉, 많은 시간을 소비한다는것이다.

    시간 복잡도가 크다.

 

 

정리

두개의 인접한 원소를 비교하여 정렬하는 방식의 버블정렬은 정렬과정이 마치 거품처럼 톡톡 올라오는것처럼 생겨서 생긴 별명이라고 할 수 있다.

그리고 딱 보기만 해도 굉장히 기초적인 정렬 알고리즘이자 잘 사용하지 않는 정렬이라는것을 눈치 챌수 있다.

구현 난이도 또한 굉장히 쉬운 난이도에 속한다.

 

버블정렬의 특징 중에 비교 정렬을 한다는것과 제자리 정렬을 하는것은 우리가 앞서 배운 선택 정렬과 매우 흡사하다.

하지만 안정 정렬이라는것이 가장 큰 차이 이다.

 

 

	최악	최선	평균
Counting Sort(계수 정렬)			O(n)
Selection Sort(선택 정렬)	O(n2)	O(n2)	O(n2)
Insertion Sort(삽입 정렬)	O(n2)	O(n)	O(n2)
Bubble Sort(거품 정렬)	O(n2)	O(n)	O(n2)