[알고리즘] 버블정렬 쉽게 생각하기

정렬(Sort)를 할 때 가장 기초적으로 생각할 수 있는 것은 "오른쪽부터 제일 큰 수를 차근차근 쌓아올리겠다" 입니다.

왼쪽을 기준으로 숫자를 세어나가면서 큰 수를 만나면 바로 오른쪽으로 밀어버리면서 정렬을 진행하는 것입니다.

 

 

즉, 오른쪽 기준점에 가장 큰 수 i를 두겠다는 목표를 두고 j가 0부터 i가 있는 지점(i-1)까지 하나하나씩 바로 오른쪽에 숫자와 비교를 하여 큰 수를 오른쪽에 두면 됩니다. 그렇게 하면 결국 j가 0에서 i-1이 되었을 때에는 i번째와 비교하면서 i번째까지 중에 가장 큰 수를 오른쪽에 둘 수 있게 됩니다.

 

 

j가 0부터 i-1까지 갈 때 오른쪽과 비교하면서 오른쪽이 크면 왼쪽과 자리를 바꾼다. 그러면  i-1에 이르러 i점에서 큰 수가 나타난다.

 

 j가 0에서부터 i-1까지 한 번 가면 기준점 i에 가장 큰 수가 배치되게 됩니다. 그 다음에는 기준점 i의 다음점 i+1에 가장 큰 수를 찾아야 되고, j는 0에서부터 i-2까지 가게 되고, i+1은 오른쪽 기준으로 두번재로 가장 큰 수가 됩니다.

 

제일 오른쪽이 값은 찼다.

 

그러면 식은 아래와 같게 됩니다. 여기서 중요한 점은 i가 0인 이유는 i가 오른쪽 기준으로 카운트가 올라간다는 점입니다.

for (int i=0; i < n-1; i++){
	for(j=0; j<n-i-1; j++){
		if(arr[j] > arr[j+1]){
		swap(&arr[j], &arr[j+1]);
		}
	}
}

 

i가 하나씩 늘어가는 부분을 잘 보면 달팽이 집이 커가는 것과 비슷합니다.