최적화된 버블정렬 알고리즘 구현

내가 작성한 코드

//원래라면 이중반복문을 사용하여 해결했을 것이다.

function bubbleSort(arr){
	let count = arr.length;
	while(count){
    for(let i = 0; i < arr.length; i++){
			if(arr[i + 1] > arr[i])[arr[i],arr[i+1]] = [arr[i+1],arr[i]];
		}
		count--;
	}
	return arr;
}
//하지만 이 경우에는 이미 정렬이 완료되었음에도 계속 내부의 for문이 수행(조건문 검사)되기 때문에
//비효율적이다. 따라서 정렬이 완료되었다면 중간에라도 스탑하는게 맞다.
//그렇다면 정렬이 완료가 되었다는 것을, 어떻게 컴퓨터에게 알려줄 수 있는가?
//정렬이 완료되었다는 정보를 다른 변수에 따로 저장해놓고, 그 변수의 값을 기준으로, 
//내부 반복문을 더 수행할지 말지 결정하면 되지 않을까?

//정렬이 완료가 되었다는 건, 더 이상 교환을 할 필요가 없다는 것. 즉 교환횟수가 0이라는 것이다.
//그렇다면 교환 횟수에 대한 변수를 선언하고 0을 할당하자.
//그리고 그것을 기준으로 변수의 값이 0이라면 전체 반복문을 완전 중지시켜버린다. (break)
//완전 중지시켜도 되는 이유는, 더 이상 정렬할 필요가 없다는 뜻이기 때문이다. 

function bubbleSort(arr){
	let switch = 0;
	for(let j = 0; j < arr.length; j++){
    for(let i = 0; i < arr.length; i++){
			if(arr[i + 1] > arr[i]){
				[arr[i],arr[i+1]] = [arr[i+1],arr[i]];
				switch++;
			}
		if(!switch) break;
	}
	return arr;
}

//리팩토링: 
위 부분에서 또 줄일 수 있는 부분은 내부의 반복문이다. 
이미 정렬된 부분에 대해서까지 비교를 할 필요가 없기 때문에 반복 횟수를 줄여야한다. 
j =0 일때는 정렬된 부분이 하나도 없어서 i를 배열의 길이 - 1까지 반복시켜야함
j= 1 일때는 이미 정렬된게 하나 있으므로 i를 배열의 길이 -1 -1까지 반복
j= 2 일때는 이미 정렬된게 두개 있으므로 i를 배열의 길이 -1 -2까지 반복
...
이렇게 해보면
j일때는 이미 정렬된게 j개 있으므로 i를 배열의 길이 -1 -j까지 반복함을 알수있다.
따라서 더 시간을 적게 소요하는 코드를 만들수있다
function bubbleSort(arr){
	let switch = 0;
	for(let j = 0; j < arr.length; j++){
    for(let i = 0; i < arr.length - 1- j; i++){
			if(arr[i + 1] > arr[i]){
				[arr[i],arr[i+1]] = [arr[i+1],arr[i]];
				switch++;
			}
		}
		if(!switch) break;
	}
	return arr;
}