Bubble Sort

Bubble Sort

• 한번 횟수에 맨 뒤에 가장 큰 수가 정렬된다.(한번 정렬이 일어날때 마다 맨뒤에 가장 큰 순으로 정렬된다)
• 두 인접한 원소를 비교하여 정렬하는 방법

로직

1. 7개의 숫자가 정렬된 배열이라고 하고, 0번부터 순서가 있다고 하면(0123456)
2. 처음 비교에서는 0~5번째 까지 for문을 돌면서 양옆을 비교한다
3. 다음은 0~4번째 까지 ... 이런식으로 반복 비교를하면 뒤에서 부터 숫자가 큰 순서대로 정렬이 일어난다.

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {
    static int count=0;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int arr[] = new int[n];
        for(int a_i=0; a_i < n; a_i++){
            arr[a_i] = in.nextInt();
        }
        BubbleSort(arr);
    }
    public static void BubbleSort(int []arr){
        int temp;
        for(int i=0;i<arr.length-1;i++){
            for(int j=0;j<arr.length-(i+1);j++){
                if(arr[j]>arr[j+1]){
                    temp=arr[j+1];
                    arr[j+1]=arr[j];
                    arr[j]=temp;
                    count++;
                }
            }
        }
        System.out.println("Array is sorted in "+count+" swaps.");
        System.out.println("First Element: "+arr[0]);
        System.out.println("Last Element: "+arr[arr.length-1]);
    }
}

시간 복잡도와 공간 복잡도

• 버블 정렬의 비교 횟수 = (n-1)+(n-2)+...+2+1=(n-2)n/2

• 시간 복잡도 : O(n^2)

• 공간 복잡도 : O(n)

• 최선의 경우(이미 정렬이 되어있는 경우)

  • 자리교환횟수 0번

• 최악의 경우(역순 정렬)

  • 자리 교환 횟수 n(n-2)/2번
  • 비교 횟수는 n(n-1)/2번으로 같음