JAVA 버블정렬 알고리즘 이해하기

버블 정렬의 개념

거품 정렬(어: bubble sort, sinking sort)은 두 인접한 원소를 검사하여 정렬하는 방법이다. 시간 복잡도가 {\displaystyle O(n^{2})}로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용된다. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다 – 위키백과

코드와 그림으로 이해하기

//랭킹 구하는 코드인데, for문의 조건 방식만 봐도 된다.
for(int i = 0; i < s.length - 1; i++) {
    for(int j = i; j < s.length - 1 - i; j++) {
        if(total[j] > total[j + 1]) {
            ranking[j]++;
        } else if(total[j] < total[j + 1]) {
            ranking[i]++;
	}
    }
}

• 보기와 같이 가면서 계속 검사를 하기때문에 시간복잡도가 상당히 느리다.
• 그러나 알고리즘을 처음 접하기에는 그림으로 이해하기에도 간단해서 사용하기 좋다.
• i는 실행횟수로 index-1번을 실행한다. 그 이유는 1회 실행 때, 이미 뒤에까지 처리가 되었기 때문
• j는 j와 인접한 j+1간의 비교, 처리과정을 거친다.