자바 스크립트의 초급 정렬 알고리즘:버블,선택 및 삽입 정렬

데이터 세트를 모두 배열하면 관리 및 검색에 더 많은 시간과 리소스가 추가됩니다. 데이터가 정렬되었는지 여부에 관계없이 사용할 수있는 검색 방법에 직접 영향을 미치며 이진 검색과 같이 백만 개의 작업을 수행하는 검색 또는 10 을 수행하는 검색 간의 차이를 의미 할 수 있습니다.

간단히 말해서,우리는 숫자 배열을 최소값에서 최대값으로 정렬하는 데만 집중할 것이지만,이러한 알고리즘은 다른 정렬 목표를 위해 쉽게 수정할 수 있습니다. 특정 구현은 많이 다를 수 있지만 결국에는 개념적으로 이러한 패턴과 유사 할 수 있기 때문에 이러한 개념 및 패턴은 더 일반적인 개념 및 패턴이며 데이터 정렬에 대한”방법”이 적음을 명심하십시오.

여기에 50 개의 난수의 연습 배열이 있습니다.

const unsortedArr = ;

전제 조건

빅 오 표기법의 렌즈를 통해 모든 것을 살펴볼 것이므로 시간이 지남에 따라 복잡성이 어떻게 증가하는지 이해하는 것이 매우 도움이 될 것입니다.

버블 정렬

이것은 정렬 방법의”안녕하세요 세계”입니다.

배열의 각 항목에 대해 우리는 다음 항목이 배열에서 자신의 인덱스를 교환하는 경우,더 큰 경우 확인하려고합니다. 정렬 된 숫자를 다시 계산하지 않으려면 배열 뒤쪽에서 시작하여 다른for loop이 이전 숫자를 가져옵니다. 이 방법으로 모든 가장 큰 값이 쌓이거나 끝에”거품이 생깁니다”.

버블 정렬 애니메이션

그래픽/애니메이션 덕분에 VisuAlgo.net

우리 버전은 애니메이션에서 반대로 작동하지만 충분히 가깝습니다.

const bubble = arr => { const swap = (list, a, b) => , list] = , list]; for (let i = arr.length; i > 0; i--) { for (let j = 0; j < i - 1; j++) { if (arr > arr) swap(arr, j, j + 1); }; }; return arr;};console.log(bubble(unsortedArr));

선택 정렬

선택 정렬은 버블 정렬의 반대처럼 작동하지만 버블 정렬은 가장 큰 값을 모두 끝까지 밀어 넣습니다.

배열을 반복할 때마다 가장 작은 값을 선택합니다. 루프가 완료되면 그 최소 걸릴 다시 루프를 시작하기 전에 배열의 전면에 넣어 것입니다. 이 방법은 전체 배열이 정렬 될 때까지 각 반복의 가장 낮은 값이 앞면에 쌓입니다.

선택 정렬 애니메이션

비주얼 덕분에 그래픽/애니메이션.순

const selection = arr => { const swap = (list, a, b) => , list] = , list]; arr.forEach((item, i) => { let min = i; for (let j = i + 1; j < arr.length; j++) { if (arr < arr) min = j; }; swap(arr, i, min); }); return arr;};console.log(selection(unsortedArr));

삽입 정렬

개인적으로 가장 좋아하는 삽입 정렬은 손으로 무언가를 정렬하는 방법과 더 유사합니다.

우리는 배열을 정렬 된 것과 정렬되지 않은 두 부분으로 간주하며,새로운 값을 찾을 때마다 정렬 된 절반에서 그 자리를 찾기 위해 다시 반복합니다. 각 추가와 함께 우리의 정렬 된 그룹은 전체 배열이 될 때까지 커집니다.

삽입 정렬 애니메이션

비주얼 덕분에 그래픽/애니메이션.순

const insertion = arr => { arr.forEach((item, i) => { let num = arr; let j; for (j = i - 1; j >= 0 && arr > num; j--) { arr = arr; }; arr = num; }); return arr;};console.log(insertion(unsortedArr));

비교

알고리즘을 비교하기 위해 빅 오 표기법을 사용하는 한 가지 문제점은 알고리즘에서 동일 할 수있는 최악의 시나리오를 기반으로한다는 것입니다. 버블,선택 및 삽입 정렬은 모두 영형(엔^2),평균 또는 최상의 시나리오 또는 데이터 구조에 따라 어떻게 다른지에 대해 많이 알려주지 않습니다.

삽입 정렬이 매번 승리합니다. 또한 시작하기 전에 전체 배열을 가질 필요가 없다는 이점이 있으므로 데이터가 들어올 때 실시간으로 정렬 할 수 있습니다.

데이터가 이미 구성되는 방식을 고려하기 전에 어떤 알고리즘이”최고”인지 결정해서는 안되기 때문에 이 점을 명심하십시오.

결론

이 세 가지는 많은 양의 데이터를 효율적으로 분류하는 최상의 솔루션과는 거리가 멀지 만,압도적 인 바다가 될 수있는 것에 발가락을 담그는 가장 직관적 인 것 중 일부입니다. 🌊