꾸준2

거품 정렬(Bubble Sort)

• 인접한 두 값을 검사하여 정렬하는 알고리즘
• 두 값이 순서대로 되어 있지 않으면 서로 교환

시간 복잡도 : O(n^2)   => n(n-1)/2

공간 복잡도 : O(N)

장점

• 구현이 간단하고 가독성이 좋다
• 다른 메모리 공간이 필요하지 않다
• 안정적인 정렬이다

단점

• 시간 복잡도가 최선, 최악 모두 O(N^2)이여서 비효율적이다
• 교환 횟수가 많다

function bubbleSort(arr) {
  var temp = 0; // 교환할때 필요한 변수
  var count = 0; // 시간복잡도 계산용 변수
  for(var i=0; i<arr.length; i++) {
    for(var j=0; j<arr.length-1-i; j++) {
      count++
      console.log(`${arr}, i : ${i}, j : ${j}, 횟수 : ${count}`)
      if(arr[j] > arr[j+1]) {
        temp = arr[j]
        arr[j] = arr[j+1]
        arr[j+1] = temp
      }
    }
  }
  return arr
}

console.log(bubbleSort([4,10,3,2,6]))

// 4,10,3,2,6, i : 0, j : 0, 횟수 : 1
// 4,10,3,2,6, i : 0, j : 1, 횟수 : 2
// 4,3,10,2,6, i : 0, j : 2, 횟수 : 3
// 4,3,2,10,6, i : 0, j : 3, 횟수 : 4
// 4,3,2,6,10, i : 1, j : 0, 횟수 : 5
// 3,4,2,6,10, i : 1, j : 1, 횟수 : 6
// 3,2,4,6,10, i : 1, j : 2, 횟수 : 7
// 3,2,4,6,10, i : 2, j : 0, 횟수 : 8
// 2,3,4,6,10, i : 2, j : 1, 횟수 : 9
// 2,3,4,6,10, i : 3, j : 0, 횟수 : 10
// [ 2, 3, 4, 6, 10 ]

검색 : 특정 값을 찾는 일

선형 검색 : 정렬된 값 or 정렬되지 않은값 모두 사용가능한 검색
이진 검색 : 정렬된 값일때 사용가능한 검색

선형 검색

1. 배열의 0번째 인덱스부터 전체를 접근 하여 값을 찾는 검색

2. 시간복잡도 : O(n)

var arr1 = [1,3,5,7,9]
var arr2 = [2,4,6,8,10]

function linearSearch(arr, num) {
  for(var i=0; i<arr.length; i++) {
    if(arr[i] == num) {
      return true
    }
  }
  return false;
}

console.log(linearSearch(arr1, 3)) // true
console.log(linearSearch(arr1, 4)) // false

console.log(linearSearch(arr2, 6)) // true
console.log(linearSearch(arr2, 7)) // false

이진 검색

1. 배열의 중간 값을 확인해 큰지 작은지 구분한다

2. 큰 경우 : 중간 값보다 큰 쪽을 검색

3. 작은 경우 : 중간 값보다 작은 쪽을 검색

var arr1 = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]

function binarySearch(arr, num) {
  var lowIndex = 0;
  var highIndex = arr.length;

  while(lowIndex <= highIndex) {
    var midIndex = Math.floor((highIndex+lowIndex)/2);
    console.log(`midIndex : ${midIndex}, lowIndex : ${lowIndex}, highIndex : ${highIndex}`)

    if(arr[midIndex] == num) {
      return midIndex;
    } else if(num>arr[midIndex]) {
      lowIndex = midIndex+1;
    } else {
      highIndex = midIndex-1;
    }
  }
  return -1
}

console.log(binarySearch(arr1, 5))
// midIndex : 8, lowIndex : 0, highIndex : 16
// midIndex : 3, lowIndex : 0, highIndex : 7
// midIndex : 5, lowIndex : 4, highIndex : 7
// midIndex : 4, lowIndex : 4, highIndex : 4
// 4

console.log(binarySearch(arr1, 17))
// midIndex : 8, lowIndex : 0, highIndex : 16
// midIndex : 12, lowIndex : 9, highIndex : 16
// midIndex : 14, lowIndex : 13, highIndex : 16
// midIndex : 15, lowIndex : 15, highIndex : 16
// midIndex : 16, lowIndex : 16, highIndex : 16
// -1

집합 : 중복되지 않은 항목들의 그룹

장점
1. 유일한 항목을 확인하고 추가하기 때문에 O(1) 상수 시간이 걸린다.(해시 테이블의 구현을 기초로하기 때문)

사용법
var setA = new Set();

속성
(집합 길이)
size -> setA.size

메소드
(원소 추가)
.add -> setA.add(값)

(원소 삭제)
.delete -> setA.delete(값)

(원소 포함)
.has -> setA.has(값)

(원소 모두 삭제)
.clear -> setA.clear()

var setA = new Set()

// 추가
setA.add(1)
setA.add(3)
setA.add(5)
console.log(setA) // Set { 1, 3, 5 }

// 삭제
setA.delete(3)
console.log(setA)// Set { 1, 5 }

// 포함
console.log(setA.has(3)) // false
console.log(setA.has(1)) // true

// 길이 확인
console.log(setA.size) // 2

// 모두 삭제
setA.clear()
console.log(setA) // set{}
console.log(setA.size) // 0

교집합(interrsection)

두 집합의 공통 값 추출

var setA = new Set([1,2,3,4,5])
var setB = new Set([1,3,5])

var intersection = new Set();

for(var common of setA) {
  if(setB.has(common)) {
    intersection.add(common)
  }
}

console.log(intersection) // Set { 1, 3, 5 }

합집합(union)

두 집합의 모든 값들을 포함하고 중복된 값은 제외

var setA = new Set([2,4,6,8,10])
var setB = new Set([1,3,5,7,9,2,4,6])

var union = new Set(setA);

for(var sum of setB) {
  union.add(sum)
}

console.log(union) // Set { 2, 4, 6, 8, 10, 1, 3, 5, 7, 9 }

차집합(difference)

두 집합의 공통되지 않은 값

var setA = new Set([2,4,6,8,10])
var setB = new Set([1,3,5,7,9,2,4,6])

var difference = new Set(setA);

for(var sum of setB) {
  difference.delete(sum)
}

console.log(difference) // Set Set { 8, 10 }