오늘은 3 대장 (삽입, 선택, 버블) 이후 좀 더 복잡하지만 빠른 합병 정렬에 대해서 정리해 보겠습니다. 합병 정렬 (MergeSort) 합병 정렬 원리는 배열을 각각 하나의 원소까지 나누어 줍니다. 즉 [3,2,1] 이라는 배열이 있으면 => [3] [2] [1] 이렇게 나눠진 배열을 다시 정렬하면서 하나에 배열로 합치는 과정입니다. [1,2,3] Example [6,3,1,5,2] 라는 배열이 있다고 가정하고 예시를 들어 보겠습니다. 중앙값을 기준으로 왼쪽과 오른쪽을 나눠줍니다. 배열 원소가 한개가 남을 때까지 나눠줘야 합니다. // 왼쪽 [6,3,1,5,2] => [6,3] [1,5,2] [6,3] => [6] [3] // 오른쪽 [1,5,2] => [1] [5,2] [5,2] => [5][2] ..
오늘은 거품 정렬 , 삽입 정렬 등 과 함께 3 대장으로 불리는 선택 정렬을 정리해 보겠습니다. 선택 정렬 (SelectionSort) 작동원리는 배열에 맨 첫 번째 요소를 작다고 가정하고 그 이후 값들과 비교해 가면서 제일 작은 값의 인덱스를 찾은 후 그 제일 작은 값을 배열에 첫번째 요소에 넣어줍니다. 그러면 배열에 첫 번째 요소에는 작은 값이 정렬되어 있으므로 그 이후부터는 배열 첫 요소 이후인 두 번째 요소에 그다음으로 작은 값을 넣어야 겠죠 ? 이런 식으로 배열을 순회하면서 정렬하는 알고리즘입니다. 예시를 들면서 설명하겠습니다. Example [6,3,1,2,5]라는 배열이 있다고 가정하겠습니다. 1 PASS 배열에 어느 값이 제일 작은지 알 수 없습니다. 고로 배열에 첫 번째 요소인 6을 제일..
오늘은 버블 정렬에 이어서 삽입 정렬 알고리즘을 정리하겠습니다. 삽입 정렬은 어떠한 기준 값을 잡고 배열 요소들이 기준값보다 큰지 작은지 확인해 가면서 값을 중간에 알고리즘 이름처럼 삽입하는 알고리즘입니다. 개인적인 느낌으로는 버블 정렬이나 , 선택 정렬보다는 조금 어려운 것 같습니다. [4,2,3,1]라는 배열이 있다고 가정해봅시다. 처음에 기준점으로는 2을 기준으로 둡니다. 기준이 되는 숫자는 배경을 초록으로 바꾸겠습니다. 기준과 비교하는 숫자는 밑줄로 표시하겠습니다. Example 1 PASS [4,2,3,1] 처음에는 0번째 인덱스가 아닌 1번째 인덱스를 기준점으로 잡고 앞 배열과 비교해 나갑니다. 그 이유는 기준점을 두고 그 앞에 배열들과 값을 비교해 나가기 때문입니다. 기준점 : 2 [4,2,..
오늘은 정렬 알고리즘 중 버블 정렬에 대해서 정리해 보고자 합니다. 버블 정렬 (Bubble Sort) 인접한 두 원소를 비교해 가면서 조건에 따라서 정렬을 해줍니다. 장점 구현하기가 쉽다. 단점 성능이 안 좋다. 예를 들어서 밑에 예시가 있다고 가정해봅시다. [3,1,4,2,5]를 버블 정렬 사용해 정렬하는 과정입니다. 주황색 : PASS 후 정렬된 숫자 1 PASS (1) 첫 번째 요소(3) 두 번째 요소(1) 비교해서 3 > 1 크기 때문에 두 요소를 교환을 해줍니다. (2) 두번째 요소(3) 세 번째 요소(4) 비교했는데 3이 4보다 더 작기 때문에 교환 하지 않습니다. (3) 세번째 요소(4) 네 번째 요소(2) 비교해서 4 > 2 크기 때문에 두 요소를 교환을 해줍니다. (4) 네번째 요소(4..
검색 알고리즘 다른 말로 탐색 알고리즘이라도 불리는 이 알고리즘에 대해 정리해보고자 한다. 기본적으로 공부한 내용에 의하면 두가지로 나뉘어지는데 1. 선형검색(Linear Search) 2.이진검색(Binary Search) 1. 선형 검색 (Linear Search) 선형검색은 기본적으로 맨 앞쪽부터 차례대로 검색하면서 타겟값과 맞는지 확인한다. 배열에 0 번째 인덱스 부터 검색하면서 올라간다. function LinearSearch(arr, target) { for (let i = 0; i < arr.length; i++) { if (arr[i] === target) { return i; } } return -1; } console.log(LinearSearch([1, 2, 3, 4, 5, 6, 8]..