시간과 공간 그리고 진실의 방

homes.sort(
   function(a, b) {          
      if (a.city === b.city) {
         // Price is only important when cities are the same
         return b.price - a.price;
      }
      return a.city > b.city ? 1 : -1;
   });

This was a small issue I came across recently and the solution I found was so brilliant I thought it was worth sharing on here.

So the problem was that I had an array like this:

var obj = [
    {
        "one": 1,
        "two": 9
    }, {
        "one": 3,
        "two": 5
    }, {
        "one": 1,
        "two": 2
    }
];

and I wanted to sort it by "one" and then by "two" to get a result like this:

var obj = [
    {
        "one": 1,
        "two": 2,
    }, {
        "one": 1,
        "two": 9
    }, {
        "one": 3,
        "two": 5
    }
];

sounds simple enough right? I thought so too, but the sorting algorithm that the browser is using limits your options when it comes to sorting by multiple fields. After a bit of researching I stumbled upon this wonderful solution: http://stackoverflow.com/questions/13211709/javascript-sort-array-by-multiple-number-fields

obj.sort(function(a, b) {
    return a["one"] - b["one"] || a["two"] - b["two"];
});

This will sort your array by "one" and if they are the same (ie. 0) then it will sort by "two". It's simple, concise, readable, and best of all - works perfectly.

자바스크립트의 2차원 배열이란?

아래의 예제 중 상황에 맞는 방법을 사용하면 된다

초기값을 할당하여 배열 생성

// arr[5][2]
var arr = [['a','b'], ['c', 'd'], ['e', 'f'], ['g', 'h'], ['i', 'j']]; 

반복문을 사용하여 빈 배열 생성

// arr[5][2]
var arr = new Array(5);

for (var i = 0; i < arr.length; i++) {
    arr[i] = new Array(2);
}

2차원 배열 생성 함수를 만들어서 사용

function create2DArray(rows, columns) {
    var arr = new Array(rows);
    for (var i = 0; i < rows; i++) {
        arr[i] = new Array(columns);
    }
    return arr;
}

// arr[5][2]
var arr = create2DArray(5, 2);

Array 객체에 배열 생성 함수를 추가하여 사용

Array.matrix = function (m, n, initial) {
    var a, i, j, mat = [];
    for (i = 0; i < m; i += 1) {
        a = [];
        for (j = 0; j < n; j += 1) {
            a[j] = initial;
        }
        mat[i] = a;
    }
    return mat;
};

// matrix('행', '열', '기본값')
var arr = Array.matrix(5, 2, 0);

- 자바스크립트 핵심 가이드 (더글라스 크락포드) p109

ES6를 지원하는 최신 브라우저라면 사용 가능한 방법

// arr[5][2] (빈 배열 생성)
const arr1 = Array.from(Array(5), () => new Array(2)

// arr[5][2] (null로 초기화하여 생성)
const arr2 = Array.from(Array(5), () => Array(2).fill(null))

자바스크립트의 2차원 배열은 1차원 배열에 또 다른 배열 객체를 추가하여 2차원 배열 만드는 방법을 사용한다. 자바스크립트 배열의 특성을 잘 모른다면 조금 이상한 방법으로 보일 수도 있다.

자바스크립트의 배열은 동적으로 배열의 크기를 조절할 수 있으며, 배열에는 모든 유형의 변수 그리고 함수, 객체도 담을 수 있어서 유연하게 사용할 수 있지만 그만큼 충분히 이해를 하고 사용해야 한다.

In this article, we cover breakdown Bubble Sort and then also share its implementation in Javascript.

Firstly, let's get it out of the way. When we say "sort", the idea is to re-arrange the elements such that they are in ascending order.

If you are new to the concept of sorting, each section of the article would be useful - concept of bubble sort, its algorithms, efficiency, etc. However, If you are here to refresh your knowledge, jump straight to the javascript implementation of the sort. Go to code

Table of Contents

• Explanation of Bubble Sort
• Code - Implementing Bubble Sort using Javascript
• Visualization
• Complexity of Bubble Sort
• Other Related Concepts

Explanation of Bubble Sort

If you are a newbie to sorting, Bubble sort is a great place to start! It is one of the more intuitive sorting methods as its algorithm mirrors how our brain generally thinks about sorting - by comparing.

Let's remove the vagueness and delve deeper into it.

A. What Bubble Sort Does?

To achieve sorting in Bubble Sort, the adjacent elements in the array are compared and the positions are swapped if the first element is greater than the second. In this fashion, the largest value "bubbles" to the top.

Usually, after each iteration the elements furthest to the right are in correct order. The process is repeated until all the elements are in their right position.

B. What Bubble Sort Does?

1. Starting with the first element, compare the current element with the next element of the array.

2. If the current element is greater than the next element of the array, swap them.

3. If the current element is less than the next element, just move to the next element.

4. Start again from Step 1.

C. Illustrating the Bubble sort method

Iteration 1: [6,4,2,5,7] → [4,6,2,5,7] → [4,2,6,5,7] → [4,2,5,6,7] → [4,2,5,6,7]

Iteration 2:[4,2,5,6,7] → [2,4,5,6,7] → [2,4,5,6,7] → [2,4,5,6,7] → [2,4,5,6,7]

Iteration 3: [2,4,5,6,7] → [2,4,5,6,7] → [2,4,5,6,7] → [2,4,5,6,7] → [2,4,5,6,7]

Other Alternatives

As you might have noticed, Bubble Sort only considers one element at a time. Thus, it is highly time consuming and inefficient. Due to its inefficiency, bubble sort is almost never used in production code.

You can use a built in function Array.prototype.sort() for sorting. This is an inplace algorithm just like bubble sort which converts the elements of the input array into strings and compares them based on their UTF-16 code unit values. Also, if you are interested, you can read about index sort which is another simple comparison based sort method that has a better performance than Bubble sort.

Implementing Bubble Sort using Javascript

Now as we have seen the logic behind bubble sort, we can write the code for it in a straightforward manner, using two nested loops.

let bubbleSort = (inputArr) => {
    let len = inputArr.length;
    for (let i = 0; i < len; i++) {
        for (let j = 0; j < len; j++) {
            if (inputArr[j] > inputArr[j + 1]) {
                let tmp = inputArr[j];
                inputArr[j] = inputArr[j + 1];
                inputArr[j + 1] = tmp;
            }
        }
    }
    return inputArr;
};

As you can see here, the sorting function will run until the variable "i" is equal to the length of the array. This might not be the most efficient solution as it means the function will run on an already sorted array more than once.

A slightly better solution involves tracking a variable called "checked" which is initially set to FALSE and becomes true when there is a swap during the iteration. Running this code on a do while loop to run the sorting function only when "checked" is true ensures that the function will not run on a sorted array more than once.

let bubbleSort = (inputArr) => {
    let len = inputArr.length;
    let checked;
    do {
        checked = false;
        for (let i = 0; i < len; i++) {
            if (inputArr[i] > inputArr[i + 1]) {
                let tmp = inputArr[i];
                inputArr[i] = inputArr[i + 1];
                inputArr[i + 1] = tmp;
                checked = true;
            }
        }
    } while (checked);
    return inputArr;
 };

Visualization

If you are finding it hard to visualize Bubble Sort, you can check this website https://visualgo.net/bn/sorting?slide=1.

You can play around with the code and see the specific function of each part of the code and how they play together to get the final sorted array.

Complexity of Bubble Sort

The worst case scenario: quadratic O(n²): this is the case when every element of the input array is exactly opposite of the sorted order.

Best case scenario: linear O(n): when the input array is already sorted. Even in this case, we have to iterate through each set of numbers once.

The space complexity of Bubble Sort is O(1).