Javascript - 정렬 알고리즘 기초 (Bubble, Insert, Select) / swap

---

목차

1. sort

2. Bubble

3. Insert

4. Select

5. 속도비교

---

 

const arr = [8, 16, 88, 18, 343, 0, 100, 28, 90000, 0.5, 7, 13];

const testArr = [ 100,000개의 숫자가 들어있음 ]

 

 

1. sort 

- 앞에서부터 하나씩 확인하며 가장 작은 수를 새로운 배열에 넣는 방식으로 정렬했을때

function gsb(arr) {
        const tempArr = [];
        while (arr.length) {
          let minNumber;
          let tempIdx = 0;
          for (let j = 0; j < arr.length; ++j) {
            if (minNumber == undefined || arr[j] < minNumber) {
              minNumber = arr[j];
              tempIdx = j;
            }
          }
          tempArr.push(minNumber);
          arr = [
            ...arr.slice(0, tempIdx),
            ...arr.slice(tempIdx + 1, arr.length),
          ];
          //   console.log(arr);
        }
        return tempArr;
      }

• console.time() 으로 arr 와 testArr의 시간 비교

   ▼ arr일때 

console.time("gsb"); 
console.log(gsb(arr));
// arr = 0.2060546875 ms
console.log(arr.sort((a, b) => a - b));
// arr= 0.09423828125 ms
console.timeEnd("gsb");

   ▼ testArr일때 

console.time("gsb"); 
console.log(gsb(testArr));
// testArr = 89374.54516601562 ms
console.log(testArr.sort((a, b) => a - b));
// testArr = 22.052978515625 ms
console.timeEnd("gsb")

 

 

 

 

2. Bubble

- 앞과 뒤를 비교해서 작은 수가 앞으로 가면서 비교하고 정렬하는 방법

- O(n^2)

const sortBubble = (arr) => {
        const tempArr = [...arr];
        for (let i = 0; i < tempArr.length; i++) {
          for (let j = 0; j < tempArr.length - 1; j++) {
            if (tempArr[j] > tempArr[j + 1]) swap(tempArr, j, j + 1);
            // console.log(j, tempArr);
          }
        }
        return tempArr;
      };

• console.time() 으로 arr 와 testArr의 시간 비교

▼  arr일때

console.time("sortBubble");
console.log(sortBubble(arr));
//arr =0.343994140625 ms
console.timeEnd("sortBubble");

▼ testArr일때

console.time("sortBubble");
console.log(sortBubble(testArr));
//testArr = 20237.739990234375 ms
console.timeEnd("sortBubble");

 

 

 

 

3. Insert

- 삽입 정렬 ( 하나씩 인덱스를 증가시켜가면서 어디에 위치해야하는지 찾아가서 넣어주며 정렬하는 방법 )

- O(n^2)

function sortInsert(arr) {
        const tempArr = [...arr];
        for (let i = 1; i < tempArr.length; ++i) {
          for (let j = i; j > 0; j--) {
            if (tempArr[j] < tempArr[j - 1]) swap(tempArr, j, j - 1);
            // else break;
          }
        }
        return tempArr;
      }

• console.time() 으로 arr 와 testArr의 시간 비교

▼  arr일때

console.time("sortInsert");
console.log(sortInsert(arr));
//arr =0.243896484375 ms
console.timeEnd("sortInsert");

▼ testArr일때

console.time("sortInsert");
console.log(sortInsert(testArr));
//arr =5696.616943359375 ms
console.timeEnd("sortInsert");

 

 

 

4. Select

- 선택 정렬 ( 전체에서 제일 작은것을 찾아 맨 앞으로 옮기며 정렬하는 방법)

function sortSelect(arr) {
        const tempArr = [...arr];
        for (let i = 0; i < tempArr.length; ++i) {
          let tempIdx = i;
          for (let j = i; j < tempArr.length; ++j) {
            if (tempArr[j] < tempArr[tempIdx]) tempIdx = j;
          }
          swap(tempArr, i, tempIdx);
        }
        return tempArr;
      }

• console.time() 으로 arr 와 testArr의 시간 비교

▼  arr일때

console.time("sortSelect");
console.log(sortSelect(arr));
//arr =0.391845703125 ms
console.timeEnd("sortSelect");

▼ testArr일때

console.time("sortSelect");
console.log(sortSelect(testArr));
//arr = 4592.99609375 ms
console.timeEnd("sortSelect");

 

 

 

 

5. 속도비교 

const testList = [
  { name: "gsb", time: 89374 },
  { name: "sort", time: 22 },
  { name: "bubble", time: 20237 },
  { name: "insert", time: 5696 },
  { name: "select", time: 4592 },
];

console.log(testList.sort((a, b) => a.time - b.time));

sort를 쓰는게  빠르고 좋다!!

---

★ 오늘의 포인트와 남겨두기 ★

 

※ swap

function swap(arr, idx1, idx2) {
  const temp = arr[idx1];
  arr[idx1] = arr[idx2];
  arr[idx2] = temp;
}

※ Quick 정렬... → O(n log n)

※ 자바스크립트로 구현하는게 익숙해졌을때 다시 와서 보기!!!!!!

 

※ 깊은 복사와 얕은 복사 → 원본을 훼손하는지에 대한 차이

const tempArr = [...arr]; // 깊은 복사
const tempArr2 = arr; // 얕은 복사

  - 깊은 복사는 원본의 내용을 새로 만들어 사용하는 것

  - 얕은 복사는 원본의 내용을 수정해 (메모리 주소를 복사해) 사용하는 것

 

 

*** 앞으로 백엔드, 서버를 배우고 블록체인까지 배워 개발자가 되는 그날까지 화이팅!!!!!!!!!!

** 목표에 대해 생각하자!!!!!

* 만들고 싶은것의 흐름을 생각해보기