[Algorithm] 거품 정렬 (Bubble Sort)

2024. 4. 4. 18:29·CS/자료구조 & 알고리즘
반응형
거품 정렬(Bubble Sort)

 

거품 정렬(Bubble Sort)은 선택 정렬(Selection Sort)과 유사한 알고리즘으로,

서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않는다면 자리를 교환하면 정렬하는 알고리즘입니다.

 

이름의 유래로는 정렬 과정에서 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어졌다고 합니다.

 

 


 

Process(Ascending)

 

1.

1회전에서 첫 번째 원소와 두 번째 원소를,
두 번째 원소와 세 번째 원소를,
세 번째 원소와 네 번째 원소를, ...

이런 식으로 (마지막-1)번째 원소와 마지막 원소를 비교하여조건에 맞지 않는다면 서로 교환합니다.

 

 

2.

1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동합니다.
2회전에서는 맨 끝에 있는 원소는 정렬에서 제외됩니다.
2회전을 수행하고 나면 끝에서 두 번째 원소까지는 정렬에서 제외됩니다.

이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어납니다.

 


 

Java Code (Ascending)

 

void bubbleSort(int[] arr){
	int temp = 0; 
    for(int i = 0; i < arr.length; i++){ // 1
    	for(int j = 1; j < arr.length; j++){ // 2
        	if(arr[j-1] > arr[j]){ // 3
            	// swap(arr[j-1], arr[j])
                
                temp = arr[j-1];
                arr[j-1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    System.out.println(Arrays.toString(arr));
}

 

1. for(int i = 0; i < arr.length; i++)

 

제외될 원소의 갯수를 의미합니다.

1회전이 끝난 후, 배열의 마지막 위치에는 가장 큰 원소가 위치하기 때문에 하나씩 증가시켜줍니다.

 

2. for(int j = 1; j < arr.length; j++)

 

원소를 비교할 index를 뽑을 반복문입니다. 

j는 현재 원소를 가리키고, j-1은 이전 원소를 가리키게 되므로, j는 1부터 시작하게 됩니다.

 

3. if(arr[j-1] > arr[j])

-> (이전 함수 > 현재 원소)

 

현재 가르키고 있는 두 원소의 대소를 비교합니다.

 

해당 코드는 오름차순 정렬이므로 현재 원소보다 이전 원소가 더 크다면 이전 원소가 뒤로 가야하므로

서로 자리를 교환해줍니다.

 

 


 

시간복잡도

 

시간복잡도를 계산하면, (n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2이므로, O(n^2) 입니다.

 

또한, 거품 정렬(Bubble Sort)은 정렬이 되어 있던 안 되어있던 2개의 원소를 비교하기 때문에

최선, 평균, 최악의 경우 모두 시간복잡도가 O(n^2) 으로 동일합니다.

 

공간복잡도

 

주어진 배열 안에서 교환(swap)을 통해, 정렬이 수행되므로 O(n) 입니다.

 


 

장점

 

  • 구현이 매우 간단하고, 소스코드가 직관적입니다.
  • 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않습니다.

      => 제자리 정렬 (in-place sorting)

  • 안정 정렬(Stable Sort) 입니다.

 

단점

 

시간복잡도가 최악, 최선, 평균 모두 O(n^2)으로, 굉장히 비효율적입니다.

정렬 되어있지 않은 원소가 정렬됐을 때의 자리로 가기 위해서, 교환 연산(swap)이 많이 일어나게 됩니다.

 


 

Reference

 

https://github.com/GimunLee/tech-refrigerator/blob/master/Algorithm/%EA%B1%B0%ED%92%88%20%EC%A0%95%EB%A0%AC%20(Bubble%20Sort).md#%EA%B1%B0%ED%92%88-%EC%A0%95%EB%A0%AC-bubble-sort

 

tech-refrigerator/Algorithm/거품 정렬 (Bubble Sort).md at master · GimunLee/tech-refrigerator

🍰 기술 냉장고입니다. 🛒 기술 면접 , 전공 시험 , 지식 함양 등 분명 도움될 거예요! 🤟 - GimunLee/tech-refrigerator

github.com

 

반응형
저작자표시 비영리 변경금지 (새창열림)

'CS > 자료구조 & 알고리즘' 카테고리의 다른 글

[자료구조] 스택 vs 큐  (0) 2024.11.11
[자료구조] Array, Array List, Linked List  (0) 2024.11.04
[Algorithm] 선택 정렬(Selection Sort)  (0) 2024.04.09
'CS/자료구조 & 알고리즘' 카테고리의 다른 글
  • [자료구조] 스택 vs 큐
  • [자료구조] Array, Array List, Linked List
  • [Algorithm] 선택 정렬(Selection Sort)
Dev Chu
Dev Chu
  • Dev Chu
    Log_Double 7
    Dev Chu
  • 전체
    오늘
    어제
    • LOG LIST (201)
      • log Double 7 (2)
        • notice (1)
        • 회고록 (1)
      • Study (112)
        • 과제 (2)
        • 코딩 테스트 (105)
        • 대규모 시스템 설계 기초 (5)
      • CS (10)
        • 자료구조 & 알고리즘 (4)
        • Design Pattern (2)
        • TIL (4)
      • FrontEnd (26)
        • HTML & CSS (16)
        • JavaScript & jQuery (9)
        • React (1)
      • BackEnd (24)
        • Java (4)
        • Python (6)
        • Database (0)
        • Spring (6)
      • Infra & DevOps (3)
        • AWS (3)
        • Git (8)
      • Project (4)
        • repo_bis (2)
        • WhiteMonday (2)
      • ETC (20)
        • TIP (13)
        • Error (5)
        • SQLD (2)
  • 블로그 메뉴

    • 코딩 테스트
  • 링크

    • GitHub
  • 공지사항

    • Log Double 7
  • 인기 글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
Dev Chu
[Algorithm] 거품 정렬 (Bubble Sort)
상단으로

티스토리툴바