버블 정렬 알고리즘

현재 값과 다음값을 비교해서 더 큰 값을 뒤로 배치한다. 

=> 이 과정을 반복하다 보면 

 

가장 큰 값인 5가 맨 뒤로 가게 됐다. 

이 과정을 반복해보자

가장 큰 값인 4가 맨 뒤로 가게 됐다. 

이 과정을 반복해보자. 

 

이 쯤 눈치를 챘는가? 

배열 전체를 통해 숫자를 비교하는 횟수가 점점 줄어들고 있다. 

이유) 

- 한번 배열 훑는 과정거칠 때마다 가장 큰 값이 맨 뒤에 고정된다. 

=> 그러니, 그 숫자 이전까지만 배열을 훑어주면 된다. 

 

특징 

- 시간 복잡도는 O(N^2)

- 선택 정렬 알고리즘도 시간 복잡도는 O(N^2)이지만, 버블 정렬 알고리즘 수행시간이 더 오래 걸린다. 

=> 이유: 버블 정렬은 매 순간 숫자들의 위치를 이동시키기 때문이다. 선택 정렬은 전체 배열 훑은 다음에 가장 작은 값을 맨 앞에 위치시키는 연산 한번 할 뿐이다. 

 

 

코드