• 첫번째 요소가 두번째 요소보다 크면 위치를 바꾼다.
• 두번째 요소가 세번째 요소보다 크면 위치를 바꾼다.
• 위 과정을 반복한다.
• 오름차순으로 정렬되어 있는 형태이다.
• 버블 정렬의 **시간복잡도는 O(n^2)**이다.
  • 버블 정렬은 배열의 크기만큼 비교가 일어나기 때문에 **어떤 경우에도 시간복잡도는 O(n^2)**이다.
  • 버블 정렬은 느리기 때문에 잘 쓰이지 않는다.
  • 이미 정렬 되어있는 상태의 배열의 경우 처음 한번만 비교가 일어나서 **시간복잡도는 O(n)**이 된다.

sort() 메서드를 사용한 버블 정렬 구현

• sort() 메서드를 이용하여 오름차순으로 정렬할 수 있다.

const bubbleSort = (arr) => {
	let newArr = arr.sort((a, b) => {
		return a-b;
	});
}

이중 for문을 이용한 버블 정렬 구현1

• 버블 정렬을 구현하라고 하면 생각할 수 있는 가장 기본적인 코드라고 생각한다.
• 전체적으로 계속해서 비교하기 때문에 효율적인 코드라고는 할 수 없다.

const bubbleSort = (arr) => {
	let newArr = [];
	let tmp = 0;

	for(let i=0; i<arr.length; i++) {
		for(let j=i+1; j<arr.length; j++) {
			if(arr[i] > arr[j]) {
				tmp = arr[i];
				arr[i] = arr[j];
				arr[j] = tmp;
			}
		}
		newArr.push(arr[i]);
	}
	return newArr;
}

이중 for문을 이용한 버블 정렬 구현2

• 이미 정렬이 되어있는 상태를 파악해서 정렬이 되어있는 경우는 바로 리턴해준다.
• 전체적으로 계속해서 비교하지 않아도 되기 때문에 효율적인 코드라고 할 수 있다.
• 새로운 변수를 만들어서 push한 다음 그 변수를 리턴해도 상관없고 그냥 입력받은 arr을 리턴해도 상관없다.

const bubbleSort = (arr) => {
	let smallerEl = 0;
	let biggerEl = 0;

	for(let i=0; i<arr.length; i++) {
		// 현재 인덱스의 요소가 다음 인덱스의 요소보다 큰 경우 정렬이 일어나야 한다.
		// 정렬이 일어나는 경우를 카운트 해주는 변수를 선언해준다.
		let cnt = 0;
		for(let j=0; j<arr.length; j++) {
			if(arr[j] > arr[j+1]) {
				// 정렬이 일어난 경우 cnt를 1씩 증가시켜준다.
				cnt++;
				smallerEl = arr[j+1];
				biggerEl = arr[j];
				arr[j] = smallerEl;
				arr[j+1] = biggerEl;
			}
		}
		// cnt가 0이라는 것은 정렬이 이루어 지지 않은 것이다. 
		// 정렬이 이루어지지 않은 경우라면 arr을 바로 리턴한다.
		if(cnt === 0) {
			return arr;
		}
	}
	return arr;
}