Sorting Algorithms_BubbleSort

Udemy - 【한글자막】 JavaScript 알고리즘 & 자료구조 마스터클래스

Elementary Sorting Algorithms | 정렬 알고리즘

What is sorting?

Sorting is the process of rearranging the items in a collection (e.g. an array) so that the items are in some kind of order.

Examples

• Sorting numbers from smallest to largest
• Sorting names alphabetically
• Sorting movies based on release year
• Sorting movies based on revenue

Sorting is an incredibly common task, so it's good to know how it works
There are many different ways to sort things, and different techniques have their own advantages and disadvantages
Sorting sometimes has quirks, so it's good to understand how to navigate them

Telling JavaScript how to sort

• The built-in sort method accepts an optional comparator function
• You can use this comparator function to tell JavaScript how you want it to sort
• The comparator looks at pairs of elements (a and b), determines their sort order based on the return value

• If it returns a negative number, a should come before b
• If it returns a positive number, a should come after b,
• If it returns 0, a and b are the same as far as the sort is concerned

Examples

function numberCompare(num1, num2) {
  return num1 - num2;
}

[ 6, 4, 15, 10 ].sort(numberCompare);
// [ 4, 6, 10, 15 ]

function compareByLen(str1, str2) {
  return str1.length - str2.length;
}

[ "Steele", "Colt", "Data Structures", "Algorithms" ]
  .sort(compareByLen);
// [ "Colt", "Steele", "Algorithms", "Data Structures" ]

Before we sort, we must swap!

 

Many sorting algorithms involve some type of swapping functionality (e.g. swapping to numbers to put them in order)

// ES5
function swap(arr, idx1, idx2) {
  var temp = arr[idx1];
  arr[idx1] = arr[idx2];
  arr[idx2] = temp;
}

// ES2015
const swap = (arr, idx1, idx2) => {
  [arr[idx1],arr[idx2]] = [arr[idx2],arr[idx1]];
}

---

BubbleSort 버블 정렬

A sorting algorithm where the largest values bubble up to the top!

BubbleSort Pseudocode

• Start looping from with a variable called i the end of the array towards the beginning
• 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

// UNOPTIMIZED VERSION OF BUBBLE SORT
function bubbleSort(arr){
  for(var i = arr.length; i > 0; i--){
    for(var j = 0; j < i - 1; j++){
      console.log(arr, arr[j], arr[j+1]);
      if(arr[j] > arr[j+1]){
        var temp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = temp;         
      }
    }
  }
  return arr;
}

// ES2015 Version
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([8,1,2,3,4,5,6,7]);

||

최적화

V

// Optimized BubbleSort with noSwaps
function bubbleSort(arr){
  var noSwaps;
  for(var i = arr.length; i > 0; i--){
    noSwaps = true;
    for(var j = 0; j < i - 1; j++){
      if(arr[j] > arr[j+1]){
        var temp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = temp;
        noSwaps = false;         
      }
    }
    if(noSwaps) break;
  }
  return arr;
}

bubbleSort([8,1,2,3,4,5,6,7]);