빠른 정렬(퀵 정렬, Quick Sort) 빠른 정렬(퀵 정렬)은 기준점을 획득한 다음 해당 기준점을 기준으로 배열은 나눈다. (한 쪽에는 기준점보다 작은 항목들이 위치하고 다른 쪽에는 기준점보다 큰 항목들이 위치한다.) 이런 식으로 모든 항목이 정렬될 때까지 이 과정을 반복한다. 우선 기준점을 나타내는 변수를 pivot이라고 지정하고, 기준점을 기준으로 왼쪽에는 기준점보다 작은 항목들이 위치하도록 하고 오른쪽에는 기준점보다 큰 항목들이 위치하도록 한다. 나뉘어진 하위 배열에 대해 재귀적으로 퀵 정렬을 호출하여, 모든 배열이 기본 배열(요소가 하나뿐인 배열)이 될 때까지 반복하면 된다. 이 때 기준점을 정하는 기준은 없으며 보통의 경우에는 배열의 첫번째 원소 / 배열의 마지막 원소 / 물리적으로 중앙에 ..

버블 정렬(거품 정렬, Bubble Sort) 버블 정렬이란? 버블 정렬은 전체 배열을 순회하면서 항목이 다른 항목보다 큰 경우 두 항목을 교환한다. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다. 시간 복잡도 O(n^2) 공간 복잡도 O(1) 장점 in-place 알고리즘이기 때문에 메모리가 절약된다. 구현하기가 쉽다. 단점 다른 정렬 알고리즘은 배열의 이미 정렬된 부분을 활용하는데 비해 거품 정렬은 모든 가능한 짝을 비교하기 때문에 성능이 안좋은 정렬 중에서도 가장 안좋은 편에 속한다. function bubbleSort(array) { let temp; for (let i = 0; i < array.length - 1; i++) { for (let j = 0; j..

삽입 정렬 삽입 정렬이란? 배열을 순차적으로 검색하면서 정렬되지 않은 항목들을 배열의 왼쪽의 정렬된 부분으로 이동시킨다. 동작 과정 예를 들어 [3, 7, 2, 5, 1, 4]의 배열을 오름차순으로 정리한다고 하면 첫번째 숫자는 놔두고 두번째 자리 숫자부터 뽑아서 그 숫자가 첫 숫자보다 크면 첫 숫자 오른쪽에, 작으면 왼쪽에 넣는다. 세번째 자리 숫자를 뽑아서 앞의 두 숫자와 크기를 비교해서 알맞은 자리에 넣는다. 이렇게 끝까지 계속 한다. 시간 복잡도 Worst Case: O(n^2): 정렬이 하나도 안되어있는 경우 Best Case: O(n): 이미 정렬이 되어있는 경우 공간 복잡도 O(1) 장점 메모리가 절약된다. (배열을 새로 만들 필요 없이 주어진 배열 안에서 정렬시키면 되기 때문, in pla..

정렬 중에 그나마 빠른 힙정렬의 경우에도 시간복잡도 O(Nlog₂N)인데 계수정렬은 시간복잡도가 O(N)으로 굉장히 빠르다. 💥그러나 정렬해야할 수의 범위가 작을 때에만 유리하다는 것을 유의해야 한다 -> 정렬해야할 수가 0,100,2,10,1000 이라면 고작 5개의 수를 정렬하는데 0부터 1000까지 배열을 만들어야 하기 때문에 메모리가 낭비되고 반복문도 불필요하게 돌아야 한다. 방법은 간단하다. 정렬해야 할 수가 [5,2,3,1,4,2,3,5,1,7] 이라면 1. 주어진 원소들을 반복문으로 돌며 각 원소의 개수를 카운팅한다. 2. 카운팅한 개수만큼 원소들을 나열해준다. 이 때 각 원소의 개수를 카운팅 하기 위해서 원소 중에 가장 큰 수 + 1의 배열 array를 만들어서 모두 0으로 채워주고 (+1..

변수 - primitive 타입과 object 타입 변수의 차이점 🍋 리액트를 공부할 때 PureComponent와 관련해서 shallow comparison 을 이해하기 위해 먼저 알아두어야 할 개념이다. 1. primitive(원시 타입) 변수 primitive(원시 타입) 변수 : number, string, boolean, null, undefined, symbol let number = 2; 이렇게 primitive 타입 변수는 변수를 선언함과 동시에 메모리에 공간이 생기게 되고 그 공간에 데이터가 적재되어진다. let number = 2; let number2 = number; console.log(number); // 2 console.log(number2); // 2 이렇게 number2 ..

내가 작성한 코드 (자바스크립트) let fs = require("fs"); let input = fs.readFileSync("/dev/stdin").toString().split("\n"); const size = Number(input[0]); class Heap { constructor() { this.items = []; } //swap swap(index1, index2) { let temp = this.items[index1]; this.items[index1] = this.items[index2]; this.items[index2] = temp; } //parentIndex parentIndex(index) { return Math.floor((index - 1) / 2); } //left..