알고리즘
이번 Concept은 자료구조와 관련된 알고리즘에 대하여 다뤄보겠습니다. :)
ES6를 사용한 정렬 알고리즘
정렬은 컴퓨터 과학에서 가장 많이 연구 된 개념입니다. 정렬 알고리즘은 항목 목록을 가져 와서 특정 순서 (가장 일반적으로 알파벳 또는 숫자)로 정렬합니다. 모든 주요 프로그래밍 언어에는 정렬 라이브러리가 내장되어 있지만 작동 방식을 알고 있다면 편리합니다. 요구 사항에 따라 이들 중 하나를 사용할 수 있습니다.
버블 정렬
버블 정렬은 가장 느린 정렬 알고리즘 중 하나이지만 구현하기 가장 쉬운 정렬 중 하나이기도합니다.
선택 정렬
이 정렬은 배열의 시작 부분에서 시작하여 첫 번째 요소를 나머지 요소와 비교하여 작동합니다. 모든 요소를 검사 한 후 가장 작은 요소가 배열의 첫 번째 위치에 배치되고 알고리즘이 두 번째 위치로 이동합니다. 이 프로세스는 데이터가 정렬 될 때까지 계속됩니다.
삽입 정렬
삽입 정렬은 한 번에 한 항목 씩 최종 정렬 된 배열 (또는 목록)을 작성하는 간단한 정렬 알고리즘입니다. 빠른 정렬, 힙 정렬 또는 병합 정렬과 같은 고급 알고리즘보다 큰 목록에서 훨씬 덜 효율적입니다. 그러나 삽입 정렬은 몇 가지 장점을 제공합니다.
빠른 정렬
빠른 정렬 알고리즘은 대용량 데이터 세트에 대한 가장 빠른 정렬 알고리즘 중 하나입니다. 빠른 정렬은 데이터 목록을 반복적으로 더 작은 요소와 더 큰 요소로 구성된 더 작은 하위 목록으로 나누는
분할 및 정복알고리즘입니다. 알고리즘은 목록의 모든 데이터가 정렬 될 때까지이 프로세스를 계속합니다. 알고리즘은 목록의 한 요소를 피벗으로 선택하여 목록을 하위 목록으로 나눕니다. 데이터는 피벗보다 작은 요소를 목록의 맨 아래로 이동하고 피벗보다 큰 요소를 목록의 맨 위로 이동하여 피벗을 중심으로 정렬됩니다.
병합 정렬
병합 정렬은 Divide and Conquer 알고리즘입니다. 입력 배열을 두 개의 절반으로 나누고 두 개의 절반을 자신을 호출 한 다음 두 개의 정렬 된 절반을 병합합니다. merge () 함수는 두 반쪽을 병합하는 데 사용됩니다. merge (arr, l, m, r)는 arr [l..m] 및 arr [m + 1..r]이 정렬되어 두 개의 정렬 된 하위 배열을 하나로 병합한다고 가정하는 핵심 프로세스입니다.
중요한 것은 언제 어디서 사용하는지를 알아야 한다는 것 입니다.
ES6를 사용한 검색 알고리즘
목록에서 데이터를 검색하는 방법에는 순차 검색과 이진 검색의 두 가지가 있습니다.
순차 검색
목록에서 데이터를 검색하는 가장 확실한 방법은 첫 번째 요소에서 시작하여 찾고있는 데이터를 찾거나 목록의 끝에 도달 할 때까지 목록의 각 요소로 이동하는 것입니다. 이를 순차 검색이라고하며 선형 검색이라고도합니다. 이는 무차별 대입 검색 기술의 한 예로서, 솔루션으로가는 도중에 데이터 구조의 모든 요소를 잠재적으로 방문합니다.
이진 검색
이진 검색은 정렬 된 데이터 세트에서 매우 효율적인 검색을 수행하는 데 사용됩니다. 시간 복잡도는 O (log2N)입니다. 하나의 가능한 항목으로 좁힐 때까지 항목을 포함 할 수있는 목록의 부분을 반복해서 절반으로 나누는 것이 아이디어입니다.
텍스트 데이터 검색
각 단어 사이의 공백을 구분 기호로 사용하는 split () 함수를 사용하여 텍스트를 단어로 분할합니다. 문장 부호가 파일에 남아 있고 가장 가까운 단어로 저장되기 때문에이 코드는 완벽하지 않지만 우리의 목적에는 충분합니다. 텍스트 데이터가 배열에 저장되면 순차 또는 이진 검색을 사용하여 배열 검색을 시작하여 단어를 찾을 수 있습니다.
이진 검색 트리 검색
BST에서 저장된 최소값과 최대 값을 검색하는 것은 비교적 간단한 절차입니다. 더 낮은 값은 항상 왼쪽 자식 노드에 저장되기 때문에 BST에서 최소값을 찾으려면 마지막 노드에 도달 할 때까지 BST의 왼쪽 가장자리 만 통과하면됩니다.
BST에 저장된 최대 값을 찾으려면 함수가 BST의 오른쪽 끝에 도달 할 때까지 노드의 오른쪽 링크를 통과해야합니다. 이 노드에 저장된 값은 최대 값이어야합니다.
BST에서 특정 값을 검색하려면 현재 노드에 저장된 데이터와 검색중인 값을 비교해야합니다. 비교는 검색이 왼쪽 자식 노드로 이동하는지 또는 현재 노드가 검색된 값을 저장하지 않는 경우 오른쪽 자식 노드로 이동하는지 여부를 결정합니다.
이 글은 아래 링크를 바탕으로 쓰여졌습니다.
Written
Video
Nothing