무질서한 관찰 기록 더미를 올바르고 문제 없이 정리하는 방법은 무엇입니까?
먼저 어떤 기록이 먼저인지 비교한 뒤, 전체 기록을 옮겨가며 자료가 어떻게 정리되어 있는지 직접 눈으로 확인해보세요.
일련의 사진을 찍은 후 기록 카드가 뒤섞였습니다. 각 카드에는 번호와 신분증이 있습니다. 작은 것부터 큰 것 순으로 정렬하려면 같은 번호의 카드 두 장을 잃어버릴 수 없습니다.
먼저 추측해 보세요
두 관찰 기록의 정렬 값은 2입니다. 정렬할 때 둘 중 하나를 삭제해야 할까요?
정답과 설명 보기
아니요, 두 기록을 모두 보관해야 합니다. — 동일한 값은 동일한 기록을 의미하지 않습니다. 정렬은 순서만 변경하며 중복 제거에 대한 책임은 없습니다.
그렇다면 경험과 과학을 연결하세요
먼저 기록을 펼쳐보자
각 카드의 문자는 신원을 기록하고, 숫자는 정렬의 기준이 됩니다. 동일한 번호가 여러 번 나타날 수 있으며 기록을 삭제할 수 없습니다.
입력은 단지 다른 숫자가 아닌 일련의 레코드입니다.
한 번에 하나의 특정 작업만 수행
이동 진행 상황, 비교 또는 교환된 카드는 주황색으로 강조 표시됩니다. 프로그램은 비교 단계에서만 값을 보고 교환 단계에서는 전체 기록을 이동합니다.
비교 → 교환 여부 결정
방법을 바꿔도 결과는 같을 것이다
원본 책에서는 쌍별 교환(가장 작은 것을 먼저 찾는 것)과 분할 빠른 정렬을 제공합니다. 다른 단계에서는 동일한 오름차순 값을 얻을 수 있지만 동일한 값을 가진 레코드는 원래 순서를 유지하지 못할 수 있습니다.
SIMPLE / BETTER / QUICKSORT
데이터가 증가할수록 단계 수가 더 중요해집니다.
처음 두 방법의 비교 횟수는 N²에 따라 증가합니다. 퀵 정렬은 일반적으로 N log N 정도이지만 모든 입력에 대해 가장 빠르다는 보장은 없습니다. 이 예에서 카운트는 실제 측정값이지 기계가 실행되는 시간(초)이 아닙니다.
비교횟수, 교환횟수, 실제 소모시간을 구분해야 함
계산 과정 펼치기
排序后：key₁ ≤ key₂ ≤ … ≤ keyₙ 排序前后：每条기록的身份与内容保持完整
알고리즘 규칙 클래스이며, 대입해서 구할 수 있는 천문학 공식은 없습니다. 비교는 순서를 결정하고 교환은 전체 기록을 이동해야 합니다. 동일한 키 값이 있다고 해서 레코드를 삭제할 수 있다는 의미는 아닙니다.
한번 시도해 보세요
세 가지 방법을 비교하려면 동일한 카드 세트를 사용하십시오. 진행률을 100%로 끌어 숫자가 오름차순인지, A-H 레코드가 여전히 있는지 확인하세요.
한번보세요 →
기호를 외울 필요가 없습니다
- N
- 레코드 수, 이 강의의 화면은 8입니다.
- 비교하다
- 두 값의 순서를 봅니다. Quicksort는 기준 값과도 비교됩니다.
- 교환
- 두 개의 완전한 레코드를 교환합니다.
- 기준가
- 퀵 정렬은 양쪽 값을 나누는 데 사용됩니다.
- 안정
- 동일한 정렬 값을 가진 레코드가 원래 상대 순서를 유지하는지 여부
알고리즘, 정확성 및 적용 범위
원본 책, 6장, 인쇄된 페이지 55-58, 표 6.A. 세 가지 알고리즘이 구현됩니다. SIMPLE SORT는 앞과 뒤 위치에 따라 쌍별로 비교하고 교환하며, BETTER는 나머지 최소값을 먼저 찾아 교환하고, QUICKSORT는 이중 포인터 파티셔닝과 중간 요소 값을 기준으로 명시적 스택을 사용합니다. 이 레슨에서는 간격 길이에 따라 스택 순서를 최적화하는 원래 BASIC의 세부 사항을 생략하고 파티션 결과와 실제 비교/교환 추적을 유지합니다. 퀵 정렬의 최악의 경우가 N log N이라고 주장하지 않습니다. 데모 카드 번호에는 실제 날짜 단위가 없으며 문자만 신원을 표시합니다. 진행률은 알고리즘의 개별 단계에 매핑되며 실제 단계 번호를 표시합니다. 비교 및 교환은 실행 시간(초)을 제외하고 별도로 계산됩니다. 동일한 값을 갖는 레코드의 순서는 안정적이지 않을 수 있습니다. 이 장의 끝 부분에 있는 문자열 ASCII 정렬에 대한 소개가 텍스트에 설명되어 있으며 상호 작용은 숫자 정렬만 구현합니다. 로컬 AA+는 정렬을 위한 특수 모듈을 찾지 못했고 결과는 독립적인 기본 수치 정렬 및 단계별 순열 불변을 사용하여 검증되었습니다.
내 이해 확인
두 개의 기록을 비교할 때 데이터를 즉시 교환해야 합니까?
불확실한 — 비교와 교환은 서로 다른 행위이며, 알고리즘 조건을 만족하는 경우에만 교환됩니다.
정렬 후의 숫자가 동일하다면, 동일한 값을 갖는 레코드의 순서도 동일해야 한다는 뜻인가요?
불확실한 — 동일한 값을 갖는 레코드의 순서 관계를 유지하는지 여부는 안정성과 관련이 있습니다. 이 강의의 세 가지 구현은 안정적인 정렬을 보장하지 않습니다.
원래 컴퓨터에서 측정한 초를 오늘의 웹페이지에서 바로 사용할 수 있나요?
캔트 — 하드웨어, 언어 및 구현은 다양합니다. 이 단원에서는 재현 가능한 작업 수와 기존 시스템을 재사용하지 않고 소요되는 시간(초)을 비교합니다.
먼저 정렬을 통해 기록이 완전하고 올바른 순서인지 확인한 다음 운영 비용을 비교합니다. 동일한 값을 가진 기록은 중복 쓰레기로 버릴 수 없습니다.
Jean Meeus · Astronomical Algorithms, 2nd ed. · 아니요. 6 장