버블정렬, Bubble sort

 버블정렬:  이웃한 두 요소의 대소관계를 비교, 교환 

 

오름차순이면, 왼쪽의 요소가 오른쪽의 요소보다 반드시 작아야함

 

-> 버블정렬은 끝에서부터 앞쪽으로 스캔하면서 이웃한 두 요소를 비교, 교환

 

n = 배열의 길이

배열의 끝 요소부터 확인하여, 왼쪽요소가 오른쪽의 요소보다 클시, swap함수를 이용해서 교환을 해준다. 

 

안쪽 for문을 한번 돌면 , a[0]는 정렬이 끝났기에, a[1]까지만 정렬을 해줘도 된다. 

그러기에 i는 줄어든다. 

 

 

알고리즘 개선1

 

만약에 정렬이 마쳤어도, for문이 끝나지 않았기에 계속 무의미한 for문이 돌아간다. 

 

-> "멈춤"을 도입하여, 정렬을 마친 배열을 짧은 시간에 정렬을 끝내준다.