과학으로 컴퓨팅을 향한 발걸음

JS의 간단한 알고리즘 및 데이터 구조

Un-splash에 J. Craig의 사진

알고리즘은 문제를 해결하기 위해 취한 단계입니다. 데이터 구조는 효율적인 액세스를 위해 구성된 데이터입니다. 알고리즘을 사용하여 주어진 데이터 구조에 대한 모든 종류의 문제 (즉, 데이터 조각 검색 또는 데이터 모음 정렬)를 해결할 수 있습니다.

따라서 컴퓨터와 관련하여 알고리즘은 수행중인 작업의 방법 (즉, 선형 검색, 이진 검색, 버블 정렬, 선택 정렬, 삽입 정렬 등)이지만 데이터 구조는 수행하는 것입니다 (예 : 배열, 키-값 쌍 객체 등). 따라서 체계적으로 데이터 세트를 검색, 정렬 또는 생성 할 수 있습니다.

간단한 데이터 구조

정렬

배열은 가장 낮은 (0)에서 가장 높은 (2) 레이블로 정렬 된 번호가 매겨진 상자 (색인)와 같습니다. 각 상자는 제자리에 고정되어 있으며 레이블 순서대로 유지됩니다.

레이블이있는 상자로 이동하여 내용을 보거나 (arrayName [2]) 내용을 추가하거나 내용을 바꿉니다 (arrayName [2] = "Sherlock Holmes"). 새로 상자에 담긴 내용을 컬렉션의 끝까지 밀어 넣을 수 있습니다 (arrayName.push (“Sherlock Holmes의 회고록”)).

그러면 수신 상자에 순서 (3)의 다음 레이블이 제공됩니다. 원래 박스 모음으로 돌아가려면 끝 부분 (arrayName.pop ())을 튀어 나올 수 있습니다.

첫 번째 상자 (arrayName.shift ())를 이동할 수도 있지만 다른 모든 상자의 레이블을 다시 지정해야합니다.

Sherlock Holmes 컬렉션은 이제 1이라는 상자에 있습니다. 상자 컬렉션을 이동 해제하면 컬렉션의 시작 부분에 새로운 내용 상자 (arrayName.shift ( "Dr. Strange"))를 추가 할 수 있습니다.

이것은 우리에게 0 & 2라고 표시된 상자에 Dr. Strange & Sherlock Holmes 컬렉션을 제공합니다.

데이터 구조 검색

선형 검색

선형 검색은 일련의 상자 (0-16)를 따라 걷다가 각 덮개를 열어 내용물이 원하는 내용인지 확인합니다 (예 : 37).

출처

따라서 컬렉션의 시작 (0이라고 말함)부터 끝 (길이가 1보다 작음)에 이르는 색인의 경우 상자에서 원하는 내용을 검색하고 다음으로 넘어갈 수 있습니다. 일치하는 것을 찾을 때까지 한 상자에서 다음 상자로 증분 할 수 있습니다.

이진 검색

이진 검색은 중간 상자로 중간으로 이동하여 원하는 항목에 대한 내용을 확인하여 내용이 정렬 된 (즉, 숫자 또는 알파벳순으로) 상자 배열을 검색하는 것과 같습니다. 너무 밟으면 현재 위치와 시작점 사이의 중간으로 뒤로 이동합니다. 그렇지 않으면 현재 위치와 끝점 사이의 중간으로 도약합니다.

출처

따라서 할 수있는 일은 낮은 (초기 0), 중간 (8) 및 높은 (초기 16) 인덱스 위치를 추적하는 것입니다. 중간 위치는 항상 낮은 지수와 높은 지수의 합의 절반입니다. 중간 상자가 일치하는지 확인합니다 (예 : 37). 예상보다 적은 경우 (<37), 앞으로 나아갑니다. 현재 중간 위치가 1 (8 + 1 = 9)로 전달되도록 낮은 지수를 재설정합니다. 그런 다음 새 중간 위치 ((9 + 16) / 2 ≈ 12)를 다시 계산하십시오.

다시 말해, 낮은 지수를 재설정하고 새로운 중간 지수를 다시 계산하여 검색에서 도약 할 수 있습니다. 반대로, 너무 밟으면 높은 지수를 재설정하고 새로운 중간 지수를 다시 계산하여 뒤로 이동할 수 있습니다.

선형 검색과 달리이 유형은 이진입니다. 당신은 항상 당신의 아이템이 박스 컬렉션의 상반기에 있는지 추측하고 있습니다.

데이터 구조 정렬

버블 정렬

버블 정렬은 높은 값을 인접한 작은 값과 지속적으로 교환하여 컬렉션을 정렬하여 최고 값의 버블 링 효과를 맨 위까지 가져옵니다.

출처

따라서 색인 0에서 시작하여 콜렉션 길이에 대해 이전 색인의 값이 더 큰 경우 현재 색인 (i)의 내용을 이후 색인 (i + 1)의 내용으로 교체합니다. 그런 다음 다음 색인 세트 (i + 1 대 i + 2) 등으로 이동합니다.

어떤 시점에서, 당신은 당신의 컬렉션에서 가장 높은 가치를 가진 상자에 도착했을 것입니다. 따라서 앞으로 계속 바뀌는 내용이 될 것입니다. 따라서 위쪽으로 거품이납니다. 낮은 값에서 높은 값으로 컬렉션이 정렬 될 때까지이 프로세스를 반복합니다.

각 반복의 마지막 상자가 가장 높은 값으로 끝나므로 마지막 상자를 제외하여 프로세스를 반복합니다.

선택 정렬

선택 정렬은 가장 낮은 값을 계속 선택하고 한쪽 끝으로 바꾸어 컬렉션을 정렬하는 것입니다.

출처

따라서 전체 컬렉션을 스캔하여 가장 낮은 값을 찾습니다. 일단 발견되면, 가장 낮은 색인 (초기 색인 0)으로 레이블이 지정된 상자와 내용을 교환합니다. 가장 낮은 값이 올바른 위치에 있으므로 다음 가장 낮은 인덱스 (인덱스 1)부터이 프로세스를 반복합니다. 반복 할 때마다 전체 콜렉션이 최저값에서 최고 값으로 정렬 될 때까지 스캔 길이 범위가 1 씩 감소합니다.

삽입 정렬

삽입 정렬은 발생한 각 값을 올바른 위치에 삽입하여 컬렉션을 정렬합니다.

출처

따라서 반복마다 전체 모음 (즉, Bubble & Selection Sorts)을 스캔하는 대신 인덱스 0과 1에서 시작하여 값을 비교합니다. 이후 값이 낮을 경우 인덱스 1의 내용이 인덱스 0보다 값이 낮 으면 해당 내용을 교체합니다. 인덱스 2에서 다음 상자로 이동하여 이전에 정렬 된 상자 (인덱스 1과 인덱스 0)를 비교합니다.

더 높은 가치가 발생할 때마다 그 내용을 오른쪽으로 바꿉니다. 올바른 위치를 찾으면 내용 (이전의 색인 2)을 올바른 상자에 삽입하십시오. 마치 마치 나중에 상자의 내용을“풀어 내고”이전 상자로 넘어가는 것과 같습니다.

이전 상자가 보유한 것보다 높은 값을 갖는 경우, 그 내용을 후자의 상자로 옮깁니다. 보유하고있는 것을 삽입 할 올바른 지점을 찾을 때까지이 작업을 계속합니다.

또 다른 간단한 데이터 구조

키 — 값 쌍의 객체

키 — 값 쌍의 객체는 레이블이없는 예금 상자와 같습니다. 각 고유 키는 특정 데이터 조각으로 열립니다. 배열과 달리 고유 키로 액세스 할 수있는 정렬되지 않은 데이터입니다.

출처

따라서 키 (objectName [ 's'])를 사용하여 입금 상자에 액세스하거나 내용을 변경하거나 지정된 내용으로 열리는 키를 만듭니다 (objectName [‘s '] = "Sherlock Holmes"). 모든 예금 상자에 저장된 모든 키 또는 모든 내용에 액세스 할 수 있습니다 (Object.keys (objectName) 또는 Object.values ​​(objectName)).

결론

기본 알고리즘 (선형 및 이진 검색, 버블, 선택 및 삽입 정렬) 및 데이터 구조 (배열 및 키-값 개체)는 데이터 관리와 관련된 시간 및 공간 문제로 이어집니다. 데이터를 검색, 정렬 또는 액세스하는 데 걸리는 시간과 이러한 프로세스에 필요한 메모리 공간을 고려하면 소프트웨어 개발자가 컴퓨터 프로그래밍에서 컴퓨터 과학으로 발전 할 수 있습니다. 효율성을위한 프로그래밍에 대한 생각에서 효율성을위한 프로그래밍에 이르기까지 다양합니다.