알고리즘 학습

5장. 모자 없이 분류하기

이 작품은 AI를 사용하여 번역되었습니다. 여러분의 피드백과 의견을 환영합니다: [e-mail]

이 장에서는 학습 내용을 살펴봅니다:

• 비교 기반 정렬 알고리즘에는 두 가지 기본 연산이 필요합니다:

  • less(i,j) A[i] < A[j].

  • swap(i,j) 의 내용을 A[i] 와A[j] 로 바꿉니다.

• 정렬할 때 비교기 함수를 제공하는 방법(예: 정수 또는 문자열 값을 내림차순으로 정렬할 수 있음). 비교기 함수는 기본 순서가 없는 복잡한 데이터 구조도 정렬할 수 있습니다(예: 2차원(x, y) 점의 컬렉션을 정렬하는 방법이 명확하지 않은 경우).

• 삽입 정렬 및 선택 정렬과 같은 비효율적인 O(^N2) 정렬 알고리즘을 코드 구조에서 식별하는 방법을 알아보세요.

• 함수가 스스로를 호출할 수 있는재귀. 이 기본적인 컴퓨터 과학 개념은 문제 해결을 위한 분할 및 정복 전략의 기초를 형성합니다.

• 병합 정렬과 퀵소트가 분할과 정복을 사용하여 N 값의 배열을 O(N logN)으로 정렬하는 방법. 힙 정렬이 O(N log N)을 보장하는 방법.

• 팀 정렬이 삽입 정렬과 병합 정렬의 기능을 결합하여 Python의 기본 정렬 알고리즘을 보장된 O(N log N)으로 구현하는 방법.

이 장에서는 배열의 N 값을 오름차순이 되도록 재배열하는 알고리즘을 소개합니다. 값 모음을 정렬된 순서로 구성하는 것은 많은 프로그램의 효율성을 향상시키기 위한 필수적인 첫 단계입니다. 정렬은 직원의 이름과 전화번호가 포함된 회사의 직원 명부를 인쇄하거나 공항 전광판에 항공편 출발 시간을 표시하는 등 많은 실제 애플리케이션에도 필요합니다.

정렬되지 않은 배열을 사용하면 최악의 경우 값을 검색하는 데 O(N)이 걸립니다. 배열이 정렬된 경우 이진 배열 검색은 최악의 경우 O(log N) 성능으로 대상 값을 찾을 수 있습니다.

스와핑을 통한 정렬

그림 5-1의 상단에 있는 배열( A)의 값을 정렬해 보세요. 연필을 사용하여 그림 5-1의 값을 종이에 복사해 보세요(또는 펜을 꺼내서 이 페이지에 그냥 써 보세요!). 배열에서 두 값의 위치를 반복적으로 바꾸어 오름차순으로 정렬해 보세요. 가장 적은 수의 스왑이 필요한 것은 무엇일까요? 또한 두 값을 서로 비교하는 횟수를 세어보세요. 저는 5번의 스왑으로 이 값들을 정렬했습니다. 더 적은 수를 사용할 수 있나요?¹

그림 5-1. 샘플 배열, A, 정렬

스왑 횟수를 세는 것도 중요하지만, 두 값 사이의 비교 횟수도 세어야 합니다. 먼저 1장에서 설명한 것처럼 7번만 비교하면 A 에서 2가 가장 작은 값이라는 것을 알 수 있습니다. 가장 작은 값은 A[3] 에서 발견되므로 A[0] 으로 바꿉니다. 이렇게 하면 가장 작은 값이 배열의 앞쪽으로 이동합니다.