버블 정렬

버블 정렬이란

버블 정렬은 정렬 알고리즘입니다. 정렬 알고리즘은 데이터 구조(일반적으로 배열)를 정렬하는 데 사용됩니다. 버블 정렬

작동 방식

버블 정렬에서는 배열의 각 요소를 반복합니다. 내부 루프에서 요소를 다음 요소와 비교합니다. 현재 요소가 더 크면 요소를 교환합니다.

1 단계

배열을 받는 함수를 만듭니다. 배열을 순환하는 for 루프를 만듭니다.

function bubbleSort(array) {

    for(let i = 0; i < array.length; i++) {

    }
}

2 단계

첫 번째for 루프 내부에 내부 루프를 만듭니다.

function bubbleSort(array) {

    for(let i = 0; i < array.length; i++) {
       for(let j = 0; j < array.length; j++) {

        }
    }
}

3단계

현재 요소가 다음 요소보다 큰지 확인하십시오. 그렇다면 교환해 드리겠습니다. 그것들을 바꾸려면 현재 요소를 저장할 temp 변수를 만듭니다. 그런 다음 다음 요소의 값을 현재 요소의 값으로 설정합니다. 마지막으로 다음 요소를 첫 번째 요소를 저장한 temp 값으로 설정합니다.

function bubbleSort(array) {

    for(let i = 0; i < array.length; i++) {
        for(let j = 0; j < array.length; j++) {
            if(array[j] > array[j + 1]) {
                temp = array[j];
                array[j] = array[j + 1]
                array[j + 1] = temp
            }
        }
    }
}

4단계

정렬된 배열 반환

함수 버블 정렬(배열) {

for(let i = 0; i < array.length; i++) {
    for(let j = 0; j < array.length; j++) {
        if(array[j] > array[j + 1]) {
            temp = array[j];
            array[j] = array[j + 1]
            array[j + 1] = temp
        }
    }
}

return array;

}

리팩토링 및 최적화

이것은 매우 간단합니다. 자세히 보면 루프 전체를 진행하면서 끝에 있는 요소가 이미 정렬되어 있지만 전체 배열을 계속 반복하고 있습니다. 간단한 리팩터링 하나로 코드를 훨씬 더 좋게 만들 수 있습니다. 첫 번째 루프에서는 처음부터 반복하는 대신 끝에서 반복할 수 있습니다. 이렇게 하면 끝에 정렬된 요소를 다시 반복하는 것을 방지할 수 있습니다.

for(let i = array.length; i > 0; i--) {
       for(let j = 0; j < array.length; j++) {
            if(array[j] > array[j + 1]) {
                temp = array[j];
                array[j] = array[j + 1]
                array[j + 1] = temp
            }
        }
 }

우리가 할 수 있는 또 다른 조정은 외부 루프의 'i' - 1이 내부 루프의 'j'보다 큰 한 내부 루프가 실행되어야 한다는 것입니다. 따라서 이제 내부 루프도 정렬된 요소를 제외합니다. 비교되는 요소 자체를 계산하지 않기 위해 -1을 수행합니다.

함수 버블 정렬(배열) {

for(let i = array.length; i > 0; i--) {
    for(let j = 0; j < i - 1; j++) {
        if(array[j] > array[j + 1]) {
            temp = array[j];
            array[j] = array[j + 1]
            array[j + 1] = temp
        }
    }
}

}

빅오 표기법

버블 정렬의 Big O 표기법은 O(n을 2로 높임)입니다.