버블정렬

오늘은 버블정렬을 공부하였다. 

 

버블정렬은 선택정렬과 아주 유사한 방법을 사용한다.

 

선택정렬은 오름차순으로 정렬할때에 가장 작은 값을 가장 앞으로 가져온다는 해결방법을 사용했다.

 

이와 유사하게 버블 정렬은 나의 옆(주로 오른쪽)의 값과 비교하여 더 작은 값을 앞으로 배치하는 것이다.

 

예를 들어서 

 

5 4 3 2 1 이라는 배열에서 위의 내용을 한번 하게 되면 결과값은 4 5 3 2 1 이렇게 5와 4 두 값만을 비교한 후에 그 두개의 위치만 바꾸는 것이다. 이를 배열을 한 번 다 순회를 하면 가장 큰 값이 가장 뒤로 가게 된다.

 

따라서 선택정렬은 가장 작은 값을 가장 앞으로 배치하는 것 이였지만, 버블정렬은 반대로 가장 큰 값들을 가장 뒤로 보낸다 라고 생각해도 될것 같다.

 

따라서 코드를 작성해 본다면

이렇게 작성 해 볼 수 있다. 

 

가장 큰값을 뒤로 가장 뒤로 배치하면서 순회하는 배열의 인덱스의 마지막을 하나씩 줄여 나간다.

 

시간복잡도는 이 역시 반복문을 두번 수행하기에 N^2라고 할수 있다.