자료구조 (Data Structure) 01

1. 자료구조 vs 알고리즘 
2. Big-O
3. 버블 정렬
4. 삽입 정렬
5. 선택 정렬

 

1. 자료구조 vs 알고리즘 

자료구조 : 데이터를 처리하는 방법 / 알고리즘 : 문제를 해결하는 절차 

자료구조 : 내가 원하는 데이터를 좀더 쉽고 빠르게 꺼내 쓰기 위해, 잘 정리된 형태로 데이터를 정렬 해 놓은 방식 (ex.스택, 큐)

 

2. Big-O : 알고리즘 성능 측정기 

성능이 기준은 빠르다 느리다라는 시간으로 표현하는 것이 아니라, 완료까지 걸리는 절차의 수로 결정된다. BigO를 사용하면, 시간복잡도를 빠르게 이해할수있다. 

O(1) < O(log N) < O(n) < O(NlogN) < O(N^2)

 

3. Bubble Sort (버블정렬)

const list = [1, 7, 3, 6, 5];

function bubble(list) {
  let temp;

  //O(n^2)
  for (let i = 0; i < list.length; i++) {
    for (let j = 0; j < list.length - 1; j++) {
      if (list[j] > list[j + 1]) {
        temp = list[j];
        list[j] = list[j + 1];
        list[j + 1] = temp;
      }
    }
  }
  console.log(list);
  return list;
}

bubble(list);

 

4. Insertion Sort (삽입정렬)

const array = [11, 13, 5, 7, 8];

function solution(arr) {
  for (let i = 1; i < arr.length; i++) {
    let key = arr[i];
    let j = i - 1;

    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = key;
  }

  console.log(arr);
}

 

5. Selection Sort (선택정렬)

const array = [55, 66, 1, 4, 19];

function selectionSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    let minIndex = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    if (i !== minIndex) {
      let temp = arr[i];
      arr[i] = arr[minIndex];
      arr[minIndex] = temp;
    }
  }

  console.log(arr);
}

 

 

 

 

 

 

참고 

https://philosopher-chan.tistory.com/243?category=801755 

1-2 자료구조와, 알고리즘은 무엇인가?

https://philosopher-chan.tistory.com/244?category=801755 

1-3 빅오표현법 Big - O notation

https://www.youtube.com/watch?v=ZjxeOCe7uF8&t=147s 

https://portpolio.jjeun.com/11

자료 구조와 알고리즘의 차이는 무엇인가?

"Icon made by Pixel perfect from www.flaticon.com"