차이를 비교하고 이해해야 한다.
bubble sort, insertion sort, selection sort (merge sort 빼고)
점진적으로 본인의 위치를 찾아간다. 위로 뽀글뽀글 🧼
반복 순회하면서 왼쪽과 오른쪽을 바꿔간다.
length - 1 만큼 순회한다. 그치만 장담할 수 없다.
Time Complexity | Space Complexity | ||
---|---|---|---|
Average | Best | Worst | Worst |
O(n^2) | O(n) | O(n^2) | O(1) |
(셀병합도 html도 먹히지 않는다.. 😢)
Average, Worth O(n^2): 왼쪽에서 오른쪽으로 순회 하면서 총 횟수는 n번이다.
n번 순회가 끝나기전에 sorting이 완료 되었다 하여도 한번도 순회를 해야 순회를 끝내야하는지를 파악한다.
function bubbleSort (arr) {
for (let i = 0; i < arr.length; i++) {
let isSwap = false;
for (let j = 1; j < arr.length; j++) {
if (arr[j - 1] > arr[j]) {
[arr[j], arr[j - 1]] = [arr[j - 1], arr[j]];
isSwap = true;
}
}
if (!isSwap) return arr;
}
return arr;
}
console.log(bubbleSort([2,4,6,1,2,5]));
isSwap
으로 Best케이스일때의 O(n)을 구현[arr[j], arr[j - 1]] = [arr[j - 1], arr[j]];
es6 Destructuring Assignment 사용
Time Complexity | Space Complexity | ||
---|---|---|---|
Average | Best | Worst | Worst |
O(n^2) | O(n) | O(n^2) | O(1) |
function insertionSort(arr) {
for (let i = 1; i < arr.length; i++) {
let key = arr[i];
let j;
for (j = i - 1; j >= 0 && arr[j] > key; j--) {
arr[j+1] = arr[j];
}
arr[j+1] = key;
}
return arr;
}
console.log(insertionSort([1,5,6,2,6,7]));
왼쪽 -> 오른쪽까지 순회한다.
가장 작은 수를 찾는 순회이다.
자리를 기준으로 정렬한다.
Time Complexity | Space Complexity | ||
---|---|---|---|
Average | Best | Worst | Worst |
O(n^2) | O(n^2) | O(n^2) | O(1) |
function selectionSort (arr) {
for (let i = 0; i < arr.length - 1; i++) {
let min = i;
for (let j = i + 1; j < arr.length; j++) {
if(arr[min] > arr[j]) min = j;
}
if(min !== i) [arr[min], arr[i]] = [arr[i], arr[min]];
}
return arr;
}
console.log(selectionSort([5,3,7,4,1,7]));
Time Complexity | Space Complexity | ||
---|---|---|---|
Average | Best | Worst | Worst |
O(nlog(n)) | O(nlog(n)) | O(n^2) | O(log(n)) |
Best: 항상 중간값을 계속 pivot으로 선택할 때가 best case다.
Worst: 최악의 경우는 항상 최대, 최소의 pivot을 선택 할 때이다.
stable하고 in place다
function quickSort(arr, pivotIndex, endIndex) {
let storeIndex = pivotIndex + 1;
for(let i = storeIndex; i <= endIndex; i++) {
if(arr[i] < arr[pivotIndex]) {
if(storeIndex !== i) {
[arr[storeIndex], arr[i]] = [arr[i], arr[storeIndex]];
}
storeIndex += 1;
}
}
if(storeIndex -1 !== pivotIndex) {
[arr[pivotIndex], arr[storeIndex - 1]] = [arr[storeIndex - 1], arr[pivotIndex]];
}
if(pivotIndex < storeIndex - 2) quickSort(arr, pivotIndex, storeIndex - 2);
if(storeIndex < endIndex) quickSort(arr, storeIndex, endIndex);
return arr;
}
console.log(quickSort([5,4,8,6,1,8], 0, 5));
합쳐나가는 sorting 이다.
Time Complexity | Space Complexity | ||
---|---|---|---|
Average | Best | Worst | Worst |
O(nlog(n)) | O(nlog(n)) | O(nlog(n)) | O(n) |
Average, Best, Worst: 최대한 세세하게 나눈후 합쳐가는 뒤집어진 트리와 유사하다. 그래서 logn인데 여기다 원소의 갯수를 총 곱해서 n(logn)이다.
Divide and Conquer Algorithm Link
where sorting algorithms help us? - - 사람들을 정렬할 때 - Sorting a list of people - 중간값을 찾을 때 - Find the median - 중복을 제거할 때 - Find duplicates in some date - 이진탐색 왜 공부하는가? - - 정렬에 따른 성능의 차이 - 성능제약에...
데이터를 다룰때 사용하는 특정형태 - 어떤 상황이 가장 적합한지 찾는다면 최적화된 코드를 짤 수 있다. 언어에 국한되지 않고 보장되어 있다. Big O를 항상 생각하고 코드에서 구분한다. Stack (Last-In First-Out) - stack.png 자료를 추가했다가 뺐다가 한다. 맨 마지막으로 들어간게 첫번째로 나온다. - Last-I...
vc_logo@2x (1).jpg 바닐라코딩 프렙 코스의 후기 입니다. 이 후기는 바닐라코딩을 고민 하시는 분들의 궁금증 해소를 위하여 쓴 글입니다. 상담가기 전까지 - 이 내용은 스킵 하셔도 무방 합니다. 그때의 나는 퍼블리셔로 에이전시에 근무 중이었다. 자바스크립트가 재밌어서 퇴근 후 조금씩 이론 공부를 하였는데 이게 티끌이다 보니 모아...
합해서 나눠떨어지는 쌍 찾기 문제 정수로 이루어진 배열 ar과 양의 정수 k가 있습니다. 다음과 같은 조건을 만족하는 배열 원소들의 쌍의 개수를 반환하는 함수를 작성해주세요. i j 이다. ar[i] + ar[j] 는 k의 배수이다. 예를들어, ar = [1, 2, 3, 4, 5, 6] 이고 k = 5 일때, 조건을 만족하는 쌍은 [1, 4...
홀수 번 나타나는 정수 찾기 Codewars Link 문제 주어진 배열에서, 홀수 번 나타나는 정수를 찾아주세요. 단, 홀수 번 나타나는 정수는 항상 한개뿐입니다. 예를들어, [1, 1, 1, 1, 10] 에서 1은 4번 나타나고, 10은 1번 나타나므로, 홀수 번 나타나는 정수는 10 입니다. 이거슨.. (https://developer...