Bubble Sort

버블소트
소팅되어져 가는 플로우가 마치 방울모양같다해서 지어진 이름.
앞에서 부터 원소 2개씩 자기앞에 있는 것과 비교해서 자리를 작은것은 앞에 큰것은 뒤로 바꿔주는 과정(오름차순기준)

시간복잡도
O(n^2) -> 왜 why, 원소마다 다한번씩 비교를 해주기 때문
뒤로채워질때마다 원소의 갯수가 하나씩 주는데 왜 n^2? -> 그렇다고 해도 결국엔 n!의 복잡도를 가지므로 빅오표기법에 따라 n^2이 맞다.

with java

package bubble;

public class Main {

	public static void sort(int[] args,int size) {
		if(size>0) {
			for (int i = 1; i <= size; i++) {
				if(args[i-1]>args[i]) {
					int tmp=args[i-1];
					args[i-1]=args[i];
					args[i]=tmp;
				}
			}
			sort(args,--size);
		}
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		int val[]= {5,2,4,1,3};
		sort(val,val.length-1);
		
		for (int i = 0; i < val.length; i++) {
			System.out.print(val[i]);
		}
	}

}