[알고리즘] 정렬 - 버블정렬

버블정렬

데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 방식

핵심이론

버블정렬은 두 인접한 데이터의 크기를 비교해 정렬하는 방법
루프를 돌면서 인접한 데이터 간의 swap연산으로 정렬

시간복잡도

O(n^2)
-> 다른 정렬 알고리즘보다 속도가 느린편

버블 정렬 과정

1. 비교 연산이 필요한 루프 범위 설정
2. 인접한 데이터 값 비교
3. swap조건에 부합하면, swap연산 수행
4. 루프 범위가 끝날 때까지 위의 2~3 반복
5. 정렬 영역 설정. 다음 루프 실행할 때는 이 영역 제외
6. 비교 대상이 없을때까지 위의 1~5 반복

-> 특정 루프의 전체 영역에서 swap이 한 번도 발생하지 않았다면 그 영역 뒤에 있는 데이터가 모두 정렬됐다는 뜻 : 프로세스 종료하기

JAVA에서 sort()를 이용해 쉽게 오름차순 정렬할 수 있지만, 직접 구현해보자.

구현 포인트

for(int i=0; i<N-1; i++){ // loop
	for(int j=0; j<N-1-i; j++){ // swap
    	if(A[j] > A[j+1]) {
        	swap수행
        }
    }
}