Bubble Sort

본 문서는 2022년 3월 29일 에 작성되었습니다.

Bubble Sort 는 깔끔한 코드로 작성이 가능하지만,
정렬의 과정에서 많은 횟수의 교환이 일어나 성능적으로 열악합니다.

Code

모든 순회에서 한 번의 교환 이 일어나는 것이 핵심입니다.

function insertionSort([length, numbers]) {
    const nums = [...numbers];

    for (let idx = 1; idx < length; idx++) {
        for (let jdx = idx; jdx > 0; jdx--) {
            if (nums[jdx] < nums[jdx-1])
              	[nums[jdx-1], nums[jdx]] = [nums[jdx], nums[jdx-1]]
        }
    }
  
    return nums;
}

아래를 Special Sort 라고 부릅니다.
음수와 양수를 반으로 가르는 형태 로도 구현할 수 있습니다.

function specialBubbleSort([length, numbers]) {
    const nums = [...numbers];
    
    for (let idx = 1; idx < length; idx++) {
        for (let jdx = idx; jdx > 0; jdx--) {
            if (nums[jdx] < 0 && nums[jdx-1] >= 0)
				[nums[jdx-1], nums[jdx]] = [nums[jdx], nums[jdx-1]]
        }
    }

    return nums;
}