버블 정렬

버블 정렬에 대해 무엇을 이해하고 있습니까?

2개의 for 루프를 사용합니다.

외부 루프 루프 감소

내부 루프 루프가 점진적으로 증가함

스와핑을 수행하는 루프이기도 합니다

.

스왑 확인이 간단합니다.

내부 루프

에서 비교를 수행합니다.

전류를 전류

옆의 1 위치와 비교합니다.

크면 오른쪽으로, 작거나 같으면 건너뜁니다

.

시간 복잡도

O(n^2)

공간 복잡성

오(1)

    function BubbleSort(arr) {
        for (let i = arr.length; i >= 0; i--) {
            //! condition to check if we still proceed with the inner loop
            let alreadySorted = true;

            //! NOTE:
            //! Since the previous loops already pushed the largest number to the right of the loop
            //! the inner loop does not need to loop all the way to the end again.
            for (let j = 0; i < i - 1; j++) {

                //! compare left to right
                if (arr[j] > arr[j + 1]) {
                    //! if nothing comes thru the if condition
                    //! means everything behind are already sorted
                    //! stop looping and break from the outer loop
                    alreadySorted = false;

                    //! SWAP
                    // this is the es6 syntax for swapping
                    // other languages may have the same
                    // I know Golang has something similar
                    [arr[j], arr[j+1]] = [arr[j+1], arr[ij];
                }
            }

            if (alreadySorted) {
                break;
            }
        }

        //* return the result after all the loops have been done.
        return arr;
    }

NOTE: There is a way of writing the swap logic in a more universal way for most other languages to implement as well.

// a more universal swap logic
const temp = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = temp;