[정렬] Bubble Sort (버블정렬) - Java

2024. 9. 5. 16:27· 알고리즘 공부
목차
  1. 1. 버블정렬이란?
  2. 2. 시간복잡도
  3. 3. 핵심이론
  4. 4. 예시
  5. 예시 코드
반응형

1. 버블정렬이란?

인접한 두 요소를 비교하여 정렬하는 간단한 알고리즘이다. 왜 버블정렬일까? 가장 큰 요소가 배열의 마지막 위치로 버블처럼 떠오른다고 하여 '버블정렬' 이라는 이름으로 유래됨.

 

2. 시간복잡도

각 정렬 과정마다 다시 한번 배열을 순회하여 인접한 두 요소를 비교해야 하므로 O(N^2) 의 시간복잡도를 가진다.

 

3. 핵심이론

1) 배열 사이즈가 N이라고 가정한다.

2) 버블 정렬은 총 (N - 1)번의 과정을 거친다.

3) 각 정렬 과정마다 맨 끝 요소는 정렬이 된 상태이므로 (N - i - 1)번 순회한다.

4) 이전 요소가 다음 요소보다 크면 swap 진행

5) 위 과정 반복

 

4. 예시

아래 N이라는 배열이 있다고 가정하자.

5 4 3 2 1

1) 첫번째 순회

4 5 3 2 1
4 3 5 2 1
4 3 2 5 1
4 3 2 1 5
(가장 큰 요소가 배열의 끝에 옴)

첫번째 순회는 총 4번 (N - 0 - 1) 번 진행한다.

 

2) 두번째 순회

3 4 2 1 5
3 2 4 1 5
3 2 1 4
(그 다음 큰 요소가 배열의 끝에 옴)
5
(이미 정렬 완료)

두번째 순회는 총 3번 (N - 1 - 1)번 순회한다.

 

3) 세번째 순회

2 3 1 4 5
2 1 3
(그 다음 큰 요소가 배열의 끝에 옴)
4
(이미 정렬 완료)
5
(이미 정렬 완료)

세번째 순회는 총 2번 (N - 2 - 1)번 순회한다.

 

4) 네번째 순회

1 2
(그 다음 큰 요소가 배열의 끝에 옴)
3
(이미 정렬 완료)
4
(이미 정렬 완료)
5
(이미 정렬 완료)

총 네 번 (N - 1번)의 정렬 과정의 (N - i - 1)번의 비교 과정으로 버블정렬은 종료된다.

 

예시 코드

public class Main {
    public static void bubbleSort(int[] arr){
        // 버블정렬 수행
        for(int i = 0; i < arr.length - 1; i++){
            for(int j = 0; j < arr.length - i - 1; j++){
                if(arr[j + 1] < arr[j]){
                    swap(arr, j + 1, j);
                }
            }
        }
    }
	
    // swap 함수
    public static void swap(int[] arr, int t1, int t2){
        int temp = arr[t1];
        arr[t1] = arr[t2];
        arr[t2] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {5, 4, 3, 2, 1};

        bubbleSort(arr);

        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}
출력 결과 : 1 2 3 4 5

 

반응형

'알고리즘 공부' 카테고리의 다른 글

[정렬] 퀵정렬 (Quick Sort) - Java  (0) 2024.09.07
[정렬] 선택정렬 (Selection Sort) - Java  (0) 2024.09.07
[백준] 11659번 문제 구간 합 구하기 4 - JAVA  (0) 2024.08.30
[프로그래머스] 타겟 넘버 - JAVA  (0) 2024.08.23
[프로그래머스] K번째수  (0) 2024.08.17
  1. 1. 버블정렬이란?
  2. 2. 시간복잡도
  3. 3. 핵심이론
  4. 4. 예시
  5. 예시 코드
'알고리즘 공부' 카테고리의 다른 글
  • [정렬] 퀵정렬 (Quick Sort) - Java
  • [정렬] 선택정렬 (Selection Sort) - Java
  • [백준] 11659번 문제 구간 합 구하기 4 - JAVA
  • [프로그래머스] 타겟 넘버 - JAVA
Developer KTU
Developer KTU
Developer KTU
KTU 개발 블로그
Developer KTU
전체
오늘
어제
  • 분류 전체보기
    • 웹 개발 공부 : Back-end
      • JAVA
      • JPA
      • JAVA - Spring
      • MySQL
      • Docker
      • Redis
      • JSP
      • DevOps
      • 파이썬 - 장고
      • 운영체제
      • WEB
    • 블록체인
    • 웹 개발 공부 : Front-end
      • React
      • Javascript
      • JQuery
      • Ajax
    • 알고리즘 공부
    • 나의 커리어

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 알고리즘
  • 백엔드
  • BOJ
  • Python
  • 백준
  • 자바스크립트
  • Back-end
  • 파이썬
  • 스프링부트
  • 코딩테스트
  • 알고리즘공부
  • 알고리즘공부기
  • Java
  • JavaScript
  • 웹개발
  • 백엔드개발자
  • SpringBoot
  • 자바
  • Algorithm
  • 컴퓨터공학

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
Developer KTU
[정렬] Bubble Sort (버블정렬) - Java
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.