웹 프론트엔드 JS 튜토리얼 자바스크립트를 사용한 알고리즘을 통한 항해 - 삽입정렬

자바스크립트를 사용한 알고리즘을 통한 항해 - 삽입정렬

Oct 13, 2024 am 06:23 AM

삽입 정렬이란 무엇입니까?

삽입 정렬은 컴퓨터 과학의 또 다른 기본 정렬 알고리즘입니다. 한 번에 한 항목씩 최종 정렬된 배열을 작성합니다. 이는 카드 패를 정렬하는 것과 매우 유사합니다. 카드를 하나씩 집어 이미 정렬한 카드 중에서 올바른 위치에 각 카드를 삽입합니다.

삽입 정렬의 작동 방식

삽입 정렬은 배열을 반복하면서 각 반복마다 정렬된 부분을 늘립니다. 각 요소에 대해 이미 정렬된 요소와 비교하여 현재 요소를 삽입할 올바른 위치를 찾을 때까지 위로 이동합니다.

다음은 단계별 분석입니다.

  1. 두 번째 요소(색인 1)를 "현재" 요소로 시작합니다.
  2. 현재 요소와 이전 요소를 비교하세요.
  3. 현재 요소가 더 작다면 이전 요소와 비교하세요. 더 큰 요소를 위로 이동하여 교체된 요소를 위한 공간을 만드세요.
  4. 전체 배열이 정렬될 때까지 2~3단계를 반복하세요.

삽입정렬의 시각화:

A Voyage through Algorithms using Javascript - Insertion Sort

https://visualgo.net/en/sorting에서 녹화한 gif

JavaScript에서 삽입 정렬 구현

각 부분을 설명하는 자세한 설명과 함께 JavaScript의 삽입 정렬 구현을 살펴보겠습니다.

function insertionSort(arr) {
  // Start from the second element (index 1)
  // We assume the first element is already sorted
  for (let i = 1; i < arr.length; i++) {
    // Store the current element we're trying to insert into the sorted portion
    let currentElement = arr[i];
    // Define the starting index of lookup (this is the last index of sorted portion of array)
    let j = j - 1;
    // Move elements of arr[0..i-1] that are greater than currentElement
    // to one position ahead of their current position
    while (j >= 0 && arr[j] > currentElement) {
      // Shift element to the right
      arr[j + 1] = arr[j];
      j--;
    }
    // We've found the correct position for currentElement (at j + 1), insert it:
    arr[j + 1] = currentElement;
  }

  // The array is now sorted in-place:
  return arr;
}
로그인 후 복사

핵심 포인트:

  1. 양방향 프로세스: 삽입 정렬은 앞으로 이동하는 외부 루프와 뒤로 이동하는 내부 루프를 통해 작동하며 알고리즘의 핵심을 구성하는 앞뒤 이동을 생성합니다.
  2. 정방향 스캔(외부 루프):
   for (let i = 1; i < arr.length; i++)
로그인 후 복사

정렬되지 않은 요소(currentElement = arr[i])를 한 번에 하나씩 선택하면서 배열을 앞으로 이동합니다.

  1. 뒤로 삽입(내부 루프):
   while (j >= 0 && arr[j] > currentElement)
로그인 후 복사

정렬된 부분을 되돌아보고 더 큰 요소를 오른쪽으로 이동하여(arr[j 1] = arr[j]) 현재 요소를 위한 공간을 만듭니다.

  1. 요소 삽입:
   arr[j + 1] = currentElement;
로그인 후 복사

현재 요소를 올바른 위치에 삽입하여 정렬된 부분을 늘립니다.

  1. 내부 및 안정적인 정렬: 동일한 요소의 상대적 순서를 유지하면서 원본 배열을 직접 수정합니다.

삽입 정렬은 한 장의 카드를 정렬하는 방식을 모방하여 한 번에 한 항목씩 최종 정렬 배열을 만듭니다. 정렬되지 않은 부분에서 카드(요소)를 반복적으로 선택하고 정렬된 카드 중 올바른 위치에 삽입하며 필요에 따라 더 큰 카드를 이동합니다. 이 직관적인 프로세스를 통해 소규모 또는 거의 정렬된 데이터 세트에 대한 삽입 정렬을 효율적으로 수행할 수 있습니다.

삽입정렬은 안정적인가?

예, 삽입 정렬은 안정적인 정렬 알고리즘입니다. 정렬 알고리즘의 안정성은 정렬 후에도 동일한 요소의 상대적 순서가 유지된다는 것을 의미합니다. 삽입 정렬은 작동 방식으로 인해 이를 자연스럽게 달성합니다.

  1. 순서 유지: 정렬된 부분에 요소를 삽입할 때 삽입 정렬은 현재 요소보다 엄격하게 큰 요소만 이동합니다. 즉, 동일한 값을 가진 요소가 여러 개 있는 경우 상대적 순서가 유지됩니다.
  2. 불필요한 교체 없음: 동일한 요소를 교체할 수 있는 다른 정렬 알고리즘과 달리 삽입 정렬은 필요한 경우에만 요소를 이동합니다. 이 특성은 동일한 요소가 원래 상대 위치에 유지되도록 보장합니다.
  3. 왼쪽에서 오른쪽으로 처리: 왼쪽에서 오른쪽으로 배열을 처리하고 각 요소를 이미 정렬된 요소 중 올바른 위치에 삽입함으로써 삽입 정렬은 자연스럽게 동일한 요소의 원래 순서를 유지합니다.

삽입 정렬의 안정성은 동일한 요소의 원래 순서를 유지하는 것이 중요한 복잡한 데이터 구조를 정렬할 때 특히 유용할 수 있습니다. 예를 들어, 학생 목록을 먼저 학년별로 정렬한 다음 이름별로 정렬하는 경우 안정적인 정렬을 사용하면 같은 학년의 학생이 이름별로 알파벳 순서로 유지됩니다.

이러한 안정성은 기본 삽입 정렬 알고리즘의 고유한 속성이며 달성하기 위해 추가적인 수정이나 오버헤드가 필요하지 않으므로 자연스럽게 안정적인 정렬 방법이 됩니다.

시간 및 공간 복잡도 분석

Insertion Sort의 성능 특성은 다음과 같습니다.

  • 시간 복잡성:

    • 최상의 사례: O(n) - 배열이 이미 정렬된 경우
    • 평균 사례: O(n^2)
    • 최악의 경우: O(n^2) - 배열이 역정렬된 경우
  • 공간 복잡도: O(1) - 삽입 정렬은 내부 정렬 알고리즘입니다

선택 정렬과 달리 삽입 정렬은 거의 정렬된 배열에서 잘 수행될 수 있으며 이러한 경우 선형 시간 복잡도에 가깝습니다.

삽입 정렬의 장점과 단점

장점:

  • 구현과 이해가 간단함
  • 중소규모 데이터세트에 효율적입니다
  • 적응형 - 거의 정렬된 배열에서 좋은 성능을 발휘합니다
  • 안정적 - 동일한 요소의 상대적 순서를 유지합니다
  • 내부 정렬(O(1) 공백)
  • 온라인 정렬 시나리오에 적합

단점:

  • 대규모 데이터세트에는 비효율적(평균 및 최악의 경우 O(n^2))
  • 입력 크기가 증가하면 성능이 빠르게 저하됩니다

삽입 정렬을 사용해야 하는 경우

  • 중소 규모 데이터세트(일반적으로 최대 수백 개의 요소)
  • 거의 정렬된 데이터
  • 요소를 수신하여 점진적으로 정렬하는 온라인 정렬 시나리오
  • 더 복잡한 알고리즘의 서브루틴(예: 작은 파티션을 위한 Quicksort)

실제 응용 프로그램 및 사용 사례

  1. 표준 라이브러리 구현: 작은 배열이나 하이브리드 정렬 알고리즘의 일부로 자주 사용됩니다
  2. 데이터베이스 작업: 소규모 레코드 세트 정렬
  3. 임베디드 시스템: 단순성과 낮은 메모리 오버헤드로 인해 리소스가 제한된 시스템에 적합
  4. 실시간 데이터 처리: 데이터가 수신될 때 정렬된 순서를 유지

결론

삽입 정렬은 대규모 데이터 세트에 대한 제한에도 불구하고 특정 시나리오에서 귀중한 이점을 제공합니다. 손으로 카드를 정렬하는 방식과 유사한 직관적인 특성으로 인해 정렬 알고리즘을 이해하는 데 탁월한 교육 도구가 됩니다.

주요 내용:

  • 거의 정렬된 데이터에 대한 O(n)의 최적 사례 시간 복잡도
  • 안정적, 내부 및 적응형 정렬 알고리즘
  • 소규모 데이터 세트 및 온라인 정렬에 효율적입니다
  • 종종 하이브리드 정렬 전략에 통합됩니다

대규모 정렬 작업에는 적합하지 않지만 삽입 정렬의 원리는 보다 정교한 방법으로 적용되는 경우가 많습니다. 특정 시나리오에서의 단순성과 효율성 덕분에 프로그래머의 알고리즘 툴킷에 귀중한 추가 기능을 제공합니다.

정렬 알고리즘의 선택은 궁극적으로 특정 사용 사례, 데이터 특성 및 시스템 제약 조건에 따라 달라집니다. 삽입 정렬을 이해하면 알고리즘 설계 장단점에 대한 통찰력을 제공하고 고급 정렬 기술을 탐색하기 위한 기반을 마련합니다.

위 내용은 자바스크립트를 사용한 알고리즘을 통한 항해 - 삽입정렬의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.

핫 AI 도구

Undresser.AI Undress

Undresser.AI Undress

사실적인 누드 사진을 만들기 위한 AI 기반 앱

AI Clothes Remover

AI Clothes Remover

사진에서 옷을 제거하는 온라인 AI 도구입니다.

Undress AI Tool

Undress AI Tool

무료로 이미지를 벗다

Clothoff.io

Clothoff.io

AI 옷 제거제

Video Face Swap

Video Face Swap

완전히 무료인 AI 얼굴 교환 도구를 사용하여 모든 비디오의 얼굴을 쉽게 바꾸세요!

인기 기사

<gum> : Bubble Gum Simulator Infinity- 로얄 키를 얻고 사용하는 방법
3 몇 주 전 By 尊渡假赌尊渡假赌尊渡假赌
Nordhold : Fusion System, 설명
3 몇 주 전 By 尊渡假赌尊渡假赌尊渡假赌
Mandragora : 마녀 트리의 속삭임 - Grappling Hook 잠금 해제 방법
3 몇 주 전 By 尊渡假赌尊渡假赌尊渡假赌

뜨거운 도구

메모장++7.3.1

메모장++7.3.1

사용하기 쉬운 무료 코드 편집기

SublimeText3 중국어 버전

SublimeText3 중국어 버전

중국어 버전, 사용하기 매우 쉽습니다.

스튜디오 13.0.1 보내기

스튜디오 13.0.1 보내기

강력한 PHP 통합 개발 환경

드림위버 CS6

드림위버 CS6

시각적 웹 개발 도구

SublimeText3 Mac 버전

SublimeText3 Mac 버전

신 수준의 코드 편집 소프트웨어(SublimeText3)

JavaScript 엔진 : 구현 비교 JavaScript 엔진 : 구현 비교 Apr 13, 2025 am 12:05 AM

각각의 엔진의 구현 원리 및 최적화 전략이 다르기 때문에 JavaScript 엔진은 JavaScript 코드를 구문 분석하고 실행할 때 다른 영향을 미칩니다. 1. 어휘 분석 : 소스 코드를 어휘 단위로 변환합니다. 2. 문법 분석 : 추상 구문 트리를 생성합니다. 3. 최적화 및 컴파일 : JIT 컴파일러를 통해 기계 코드를 생성합니다. 4. 실행 : 기계 코드를 실행하십시오. V8 엔진은 즉각적인 컴파일 및 숨겨진 클래스를 통해 최적화하여 Spidermonkey는 유형 추론 시스템을 사용하여 동일한 코드에서 성능이 다른 성능을 제공합니다.

Python vs. JavaScript : 학습 곡선 및 사용 편의성 Python vs. JavaScript : 학습 곡선 및 사용 편의성 Apr 16, 2025 am 12:12 AM

Python은 부드러운 학습 곡선과 간결한 구문으로 초보자에게 더 적합합니다. JavaScript는 가파른 학습 곡선과 유연한 구문으로 프론트 엔드 개발에 적합합니다. 1. Python Syntax는 직관적이며 데이터 과학 및 백엔드 개발에 적합합니다. 2. JavaScript는 유연하며 프론트 엔드 및 서버 측 프로그래밍에서 널리 사용됩니다.

C/C에서 JavaScript까지 : 모든 것이 어떻게 작동하는지 C/C에서 JavaScript까지 : 모든 것이 어떻게 작동하는지 Apr 14, 2025 am 12:05 AM

C/C에서 JavaScript로 전환하려면 동적 타이핑, 쓰레기 수집 및 비동기 프로그래밍으로 적응해야합니다. 1) C/C는 수동 메모리 관리가 필요한 정적으로 입력 한 언어이며 JavaScript는 동적으로 입력하고 쓰레기 수집이 자동으로 처리됩니다. 2) C/C를 기계 코드로 컴파일 해야하는 반면 JavaScript는 해석 된 언어입니다. 3) JavaScript는 폐쇄, 프로토 타입 체인 및 약속과 같은 개념을 소개하여 유연성과 비동기 프로그래밍 기능을 향상시킵니다.

JavaScript 및 웹 : 핵심 기능 및 사용 사례 JavaScript 및 웹 : 핵심 기능 및 사용 사례 Apr 18, 2025 am 12:19 AM

웹 개발에서 JavaScript의 주요 용도에는 클라이언트 상호 작용, 양식 검증 및 비동기 통신이 포함됩니다. 1) DOM 운영을 통한 동적 컨텐츠 업데이트 및 사용자 상호 작용; 2) 사용자가 사용자 경험을 향상시키기 위해 데이터를 제출하기 전에 클라이언트 확인이 수행됩니다. 3) 서버와의 진실한 통신은 Ajax 기술을 통해 달성됩니다.

자바 스크립트 행동 : 실제 예제 및 프로젝트 자바 스크립트 행동 : 실제 예제 및 프로젝트 Apr 19, 2025 am 12:13 AM

실제 세계에서 JavaScript의 응용 프로그램에는 프론트 엔드 및 백엔드 개발이 포함됩니다. 1) DOM 운영 및 이벤트 처리와 관련된 TODO 목록 응용 프로그램을 구축하여 프론트 엔드 애플리케이션을 표시합니다. 2) Node.js를 통해 RESTFULAPI를 구축하고 Express를 통해 백엔드 응용 프로그램을 시연하십시오.

JavaScript 엔진 이해 : 구현 세부 사항 JavaScript 엔진 이해 : 구현 세부 사항 Apr 17, 2025 am 12:05 AM

보다 효율적인 코드를 작성하고 성능 병목 현상 및 최적화 전략을 이해하는 데 도움이되기 때문에 JavaScript 엔진이 내부적으로 작동하는 방식을 이해하는 것은 개발자에게 중요합니다. 1) 엔진의 워크 플로에는 구문 분석, 컴파일 및 실행; 2) 실행 프로세스 중에 엔진은 인라인 캐시 및 숨겨진 클래스와 같은 동적 최적화를 수행합니다. 3) 모범 사례에는 글로벌 변수를 피하고 루프 최적화, Const 및 Lets 사용 및 과도한 폐쇄 사용을 피하는 것이 포함됩니다.

Python vs. JavaScript : 커뮤니티, 라이브러리 및 리소스 Python vs. JavaScript : 커뮤니티, 라이브러리 및 리소스 Apr 15, 2025 am 12:16 AM

Python과 JavaScript는 커뮤니티, 라이브러리 및 리소스 측면에서 고유 한 장점과 단점이 있습니다. 1) Python 커뮤니티는 친절하고 초보자에게 적합하지만 프론트 엔드 개발 리소스는 JavaScript만큼 풍부하지 않습니다. 2) Python은 데이터 과학 및 기계 학습 라이브러리에서 강력하며 JavaScript는 프론트 엔드 개발 라이브러리 및 프레임 워크에서 더 좋습니다. 3) 둘 다 풍부한 학습 리소스를 가지고 있지만 Python은 공식 문서로 시작하는 데 적합하지만 JavaScript는 MDNWebDocs에서 더 좋습니다. 선택은 프로젝트 요구와 개인적인 이익을 기반으로해야합니다.

Python vs. JavaScript : 개발 환경 및 도구 Python vs. JavaScript : 개발 환경 및 도구 Apr 26, 2025 am 12:09 AM

개발 환경에서 Python과 JavaScript의 선택이 모두 중요합니다. 1) Python의 개발 환경에는 Pycharm, Jupyternotebook 및 Anaconda가 포함되어 있으며 데이터 과학 및 빠른 프로토 타이핑에 적합합니다. 2) JavaScript의 개발 환경에는 Node.js, VScode 및 Webpack이 포함되어 있으며 프론트 엔드 및 백엔드 개발에 적합합니다. 프로젝트 요구에 따라 올바른 도구를 선택하면 개발 효율성과 프로젝트 성공률이 향상 될 수 있습니다.

See all articles