[알고리즘] 버블 정렬

버블 정렬이란?

• 정의: 인접한 두 개를 비교하여 정렬하는 방식
• 시간 복잡도가 n*n으로 크지만 로직이 단순하다.

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

만약 중간에 특정한 루프 "전체 영역"에서 swap이 더이상 일어나지 않는다? => 정렬됐다 => 프로세스 종료ok

---

실전 적용! (백준 2750) 문제 풀이

import java.util.Scanner;

class Main{
    public static void main(String args[]) {
        
        Scanner scanner = new Scanner(System.in);
        int range = scanner.nextInt();
        int[] numbers = new int[range];

        for (int i = 0; i < range; i++) {
            numbers[i] = scanner.nextInt();
        }

        for (int k = 0; k < range-1; k++) {
            for (int i = 0; i < range-1-k; i++) {
                if (numbers[i] > numbers[i + 1]) {
                    int temp = numbers[i + 1];
                    numbers[i + 1] = numbers[i];
                    numbers[i] = temp;
                    temp=0;
                }
            }
        }

        for(int i =0 ; i< range;i++){
            System.out.println(numbers[i]);
        }
    }
}

위의 풀이에서 중요 포인트: k < range-1 과 i < range-1-k
채워야할 점: for문에서 index값 신경쓰기( 배열[range]라면 실제 구현된 배열의 index는 0~range-1 ) + 구체적 숫자 대입해서 몇 번 반복해야하는지 이미지 or 그려보기