[알고리즘] - 거품정렬(Bubble Sort)

🫧Bubble Sort란?

• 서로 인접한 두 원소의 크기를 비교하고, 조건에 맞도록 자리를 교환하며 정렬하는 알고리즘 
• 코드가 직관적이고 간단하지만 매우 비효율적인 정렬  

 

🫧Bubble Sort 과정

1. 1회 차 : 첫 번째 원소와 두 번째 원소를, 두 번째 원소와 세 번째 원소를... (N-1) 번째 원소와 N번째 원소를 비교하여 큰 수를 뒤로 이동
2. 1회 차 후 가장 큰 수는 맨 뒤로  이동되므로 2회 차에서는 마지막 원소 제외(조건에 맞기 때문에) 다시 반복
3. 회차를 반복 할 수록 제외되는 원소가 늘어나고 모든 원소가 조건에 맞게 정렬될 때까지 반복한다.      

버블정렬 과정

🫧Bubble Sort Code

void bubbleSort(int[] arr){
	int temp=0;
	for(int i=0;i<arr.length;i++){
    	for(int j=1;j<arr.length-i;j++){
        	if(arr[j-1]>arr[j]){
            	temp=arr[j-1];
                arr[j-1]=arr[j];
                arr[j]=temp;
             }
         }
     }
 }

 

⌛시간복잡도

• (n-1) + (n-2) + ...+ 3 + 2 + 1 => n(n+1)/2  
• 2개의 원소를 비교하기 때문에 최선, 평균, 최악 모두 시간복잡도가 같다.  

최선	평균	최악
O(n^2)	O(n^2)	O(n^2)

 

[참고 자료]

• 링크