알고리즘:[bubble sort] Sorting Bubble

문제

• start looping from the end of the array towards the beginning with a variable called 'i'
• start an inner loop with a variable called 'j' from the beginning until i-1
• if arr[j] is greater than arr[j+1], swap those two values
• return the sorted array

예시

[12,4,5,2,23] // [2,4,5,12,23] 

풀이

function bubbleSort(arr) {
	const swap = (arr, idx1, idx2) => {
    [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]]; 
    }
    for (let i = arr.length; i > 0; i--) {
    	for(let j = 0; j < i-1; j++) {
        	if(arr[j] > arr[j+1] {
            	swap(arr, j, j+1);   
            }
        }
    }
	return arr;
}

bubbleSort([12, 4, 5, 2, 23]
// i = 5, j = 0, arr[0] > arr[1] // [4,12,5,2,23]
// i = 5, j = 1, arr[1] > arr[2] // [4,5,12,2,23]
// i = 5, j = 2, arr[2] > arr[3] // [4,5,2,12,23]
// i = 5, j = 3, arr[3] > arr[4] => false
// i = 4, j = 0, arr[0] > arr[1] => false
// i = 4, j = 1, arr[1] > arr[2] // [4,2,5,12,23]
// i = 4, j = 2, arr[2] > arr[3] => false
// i = 3, j = 0, arr[0] > arr[1] // [2,4,5,12,23] // 실질적으로 끝!
// i = 3, j = 1, arr[1] > arr[2] => false
// i = 2, j = 0, arr[0] > arr[1] => false

한 줄 평

• i를 arr.length까지로 limit을 정하고 하나씩 범위를 줄이는 방법
  - 배열 내에서 가장 큰 숫자는 for문을 처음으로 돌 때 맨 끝으로 정렬되게 되어있으므로 for문을 두번째로 돌 때 다시 체크할 필요가 없음