웹 프론트엔드 JS 튜토리얼 전문가처럼 정렬 알고리즘 마스터하기

전문가처럼 정렬 알고리즘 마스터하기

Oct 19, 2024 am 08:22 AM

지금까지 다양한 정렬 알고리즘에 대해 이야기해왔으니 오늘은 선택 정렬 알고리즘에 대해 배워보겠습니다. 메모리가 제한된 환경에서 가능한 최소 스왑 양을 허용하는 정렬 알고리즘입니다.

목차

  1. 소개
  2. 선택정렬 알고리즘이란?
  3. 선택 정렬은 어떻게 작동하나요?
    • 시간복잡도
    • 공간 복잡도
  4. JavaScript로 구현
  5. LeetCode 문제 해결
  6. 결론

소개

선택 정렬은 목록의 정렬되지 않은 부분에서 가장 작은(또는 가장 큰) 요소를 반복적으로 선택하고 이를 정렬된 부분의 시작(또는 끝)으로 이동하는 간단하면서도 효과적인 정렬 알고리즘입니다. 전체 목록이 정렬될 때까지 이 프로세스가 반복됩니다. 이 기사에서는 선택 정렬 알고리즘, JavaScript 구현 및 실제 문제 해결에 적용되는 방법에 대해 자세히 살펴보겠습니다.

Mastering Sort Algorithm like a PRO

선택 정렬 알고리즘이란 무엇입니까?

선택 정렬 알고리즘은 내부 비교 정렬 알고리즘입니다. 입력 목록을 두 부분으로 나눕니다.

  1. 좌측 정렬된 부분
  2. 정렬되지 않은 오른쪽 끝 부분

알고리즘은 정렬되지 않은 부분에서 가장 작은 요소를 반복적으로 선택하고 가장 왼쪽의 정렬되지 않은 요소와 교환하여 정렬된 부분과 정렬되지 않은 부분 사이의 경계를 한 요소 오른쪽으로 이동합니다.

선택 정렬은 어떻게 작동하나요?

배열 [64, 25, 12, 22, 11]을 사용하는 예를 살펴보겠습니다.

  1. 초기 배열: [64, 25, 12, 22, 11]
  • 정렬된 부분: []
  • 정렬되지 않은 부분: [64, 25, 12, 22, 11]
  1. 첫 번째 패스:
  • 정렬되지 않은 부분의 최소값 찾기: 11
  • 11을 정렬되지 않은 첫 번째 요소(64)와 교환
  • 결과: [11, 25, 12, 22, 64]
  • 정렬된 부분: [11]
  • 정렬되지 않은 부분: [25, 12, 22, 64]
  1. 두 번째 패스:
  • 정렬되지 않은 부분의 최소값 찾기: 12
  • 12를 정렬되지 않은 첫 번째 요소(25)와 교환
  • 결과: [11, 12, 25, 22, 64]
  • 정렬된 부분: [11, 12]
  • 정렬되지 않은 부분: [25, 22, 64]
  1. 세 번째 패스:
  • 정렬되지 않은 부분의 최소값 찾기: 22
  • 22를 정렬되지 않은 첫 번째 요소(25)와 교환
  • 결과: [11, 12, 22, 25, 64]
  • 정렬된 부분: [11, 12, 22]
  • 정렬되지 않은 부분: [25, 64]
  1. 네 번째 패스:
  • 정렬되지 않은 부분의 최소값 찾기: 25
  • 25는 이미 올바른 위치에 있습니다
  • 결과: [11, 12, 22, 25, 64]
  • 정렬된 부분: [11, 12, 22, 25]
  • 정렬되지 않은 부분: [64]
  1. 최종 통과:
    • 단 하나의 요소만 남았으며 자동으로 올바른 위치에 배치됩니다
    • 최종 결과: [11, 12, 22, 25, 64]

이제 배열이 완전히 정렬되었습니다.

시간 복잡도

선택 정렬은 모든 경우(최상, 평균, 최악)에서 O(n^2)의 시간 복잡도를 갖습니다. 여기서 n은 배열의 요소 수입니다. 그 이유는 다음과 같습니다.

  • 외부 루프는 n-1번 실행됩니다
  • 외부 루프가 반복될 때마다 내부 루프는 n-i-1번 실행됩니다(여기서 i는 외부 루프의 현재 반복입니다)

이 결과는 대략 (n^2)/2 비교와 n 교환으로 이루어지며 이는 O(n^2)로 단순화됩니다.

이러한 2차 시간 복잡성으로 인해 선택 정렬은 대규모 데이터 세트에 효율적이지 않습니다. 그러나 단순성과 가능한 최소한의 스왑 수를 만든다는 사실은 특정 상황, 특히 보조 메모리가 제한된 경우 유용할 수 있습니다.

공간 복잡도

선택 정렬은 배열을 제자리에서 정렬하기 때문에 O(1)의 공간 복잡도를 갖습니다. 입력 크기에 관계없이 일정한 양의 추가 메모리 공간만 필요합니다. 이는 메모리 효율성을 높여 메모리가 제한된 환경에서 유리할 수 있습니다.

JavaScript로 구현

선택 정렬 알고리즘의 JavaScript 구현은 다음과 같습니다.

function selectionSort(arr) {
  const n = arr.length;

  for (let i = 0; i < n - 1; i++) {
    let minIndex = i;

    // Find the minimum element in the unsorted portion
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }

    // Swap the found minimum element with the first unsorted element
    if (minIndex !== i) {
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
  }

  return arr;
}

// Example usage
const unsortedArray = [64, 25, 12, 22, 11];
console.log("Unsorted array:", unsortedArray);
console.log("Sorted array:", selectionSort(unsortedArray));
로그인 후 복사
로그인 후 복사

코드를 분석해 보겠습니다.

  1. 배열을 입력으로 사용하는 SelectionSort 함수를 정의합니다.
  2. 정렬된 부분과 정렬되지 않은 부분 사이의 경계를 나타내는 외부 루프(i)를 사용하여 배열을 반복합니다.
  3. 각 반복마다 정렬되지 않은 첫 번째 요소가 최소값이라고 가정하고 해당 인덱스를 저장합니다.
  4. 그런 다음 내부 루프(j)를 사용하여 정렬되지 않은 부분에서 실제 최소 요소를 찾습니다.
  5. 더 작은 요소를 찾으면 minIndex를 업데이트합니다.
  6. 최소값을 찾은 후 필요한 경우 정렬되지 않은 첫 번째 요소로 바꿉니다.
  7. 전체 배열이 정렬될 때까지 이 과정을 반복합니다.

LeetCode 문제 해결

선택 정렬 알고리즘을 이용하여 리트코드 알고리즘 문제 하나를 풀어보겠습니다. 할까요?

문제: 배열 정렬 [중간]

문제: 정수 배열이 주어지면 배열을 오름차순으로 정렬하고 반환합니다. O(nlog(n)) 시간 복잡도에서 내장 함수를 사용하지 않고 가능한 가장 작은 공간 복잡도로 문제를 해결해야 합니다.

접근법:: 이 문제를 해결하기 위해 Selection Sort 알고리즘을 직접 적용할 수 있습니다. 여기에는 배열을 반복하고, 정렬되지 않은 부분에서 가장 작은 요소를 찾아 이를 정렬되지 않은 첫 번째 요소와 바꾸는 작업이 포함됩니다. 전체 배열이 정렬될 때까지 이 과정을 반복합니다.

해결책:

function selectionSort(arr) {
  const n = arr.length;

  for (let i = 0; i < n - 1; i++) {
    let minIndex = i;

    // Find the minimum element in the unsorted portion
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }

    // Swap the found minimum element with the first unsorted element
    if (minIndex !== i) {
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
  }

  return arr;
}

// Example usage
const unsortedArray = [64, 25, 12, 22, 11];
console.log("Unsorted array:", unsortedArray);
console.log("Sorted array:", selectionSort(unsortedArray));
로그인 후 복사
로그인 후 복사

이 솔루션은 앞서 구현한 Selection Sort 알고리즘을 직접 적용합니다. 문제를 올바르게 해결하지만 선택 정렬의 O(n^2) 시간 복잡성으로 인해 이 솔루션이 LeetCode의 대규모 입력에 대한 시간 제한을 초과할 수 있다는 점에 주목할 가치가 있습니다. 아래 이미지는 해결책이 정확하지만 효율적이지 않음을 보여줍니다.

Mastering Sort Algorithm like a PRO

결론

결론적으로 선택 정렬은 정렬 기술의 세계에 대한 훌륭한 소개 역할을 하는 간단하고 직관적인 정렬 알고리즘입니다. 단순성으로 인해 이해하고 구현하기가 쉬워 초보자에게 귀중한 학습 도구가 됩니다. 그러나 2차 시간 복잡도 O(n^2)로 인해 대규모 데이터 세트에는 효율적이지 않습니다. 대규모 데이터 세트 또는 성능이 중요한 애플리케이션의 경우 QuickSort, MergeSort 또는 내장 정렬 기능과 같은 보다 효율적인 알고리즘이 선호됩니다.



최신 소식과 연결 상태를 유지하세요

이 시리즈의 모든 부분을 놓치지 않도록 하고 저와 더 깊이 있게 소통하기 위해
소프트웨어 개발(웹, 서버, 모바일 또는 스크래핑/자동화), 데이터에 대한 토론
구조와 알고리즘, 기타 흥미로운 기술 주제에 대해 알아보려면 저를 팔로우하세요.

Mastering Sort Algorithm like a PRO

위대한 해결책 ?

소프트웨어 엔지니어 | 기술 작가 | 백엔드, 웹 및 모바일 개발자 ? | 효율적이고 확장 가능한 소프트웨어 솔루션 제작에 열정을 갖고 있습니다. #연결하자 ?
  • 깃허브
  • 링크드인
  • 엑스(트위터)

앞으로 계속 지켜봐 주시기 바랍니다. 즐거운 코딩 되세요 ?‍??

위 내용은 전문가처럼 정렬 알고리즘 마스터하기의 상세 내용입니다. 자세한 내용은 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- 로얄 키를 얻고 사용하는 방법
4 몇 주 전 By 尊渡假赌尊渡假赌尊渡假赌
Nordhold : Fusion System, 설명
4 몇 주 전 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)

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이 포함되어 있으며 프론트 엔드 및 백엔드 개발에 적합합니다. 프로젝트 요구에 따라 올바른 도구를 선택하면 개발 효율성과 프로젝트 성공률이 향상 될 수 있습니다.

JavaScript 통역사 및 컴파일러에서 C/C의 역할 JavaScript 통역사 및 컴파일러에서 C/C의 역할 Apr 20, 2025 am 12:01 AM

C와 C는 주로 통역사와 JIT 컴파일러를 구현하는 데 사용되는 JavaScript 엔진에서 중요한 역할을합니다. 1) C는 JavaScript 소스 코드를 구문 분석하고 추상 구문 트리를 생성하는 데 사용됩니다. 2) C는 바이트 코드 생성 및 실행을 담당합니다. 3) C는 JIT 컴파일러를 구현하고 런타임에 핫스팟 코드를 최적화하고 컴파일하며 JavaScript의 실행 효율을 크게 향상시킵니다.

See all articles