How to arrange a stack of disordered observation records in a correct and trouble-free manner?
First compare which record is earlier, then move the entire record and see with your own eyes how the data is arranged.
General Algorithms and Numerical Computing
After taking a set of photos, the record card was scrambled. Each card has a number and an identity letter. If you want to sort them from small to large, you can't lose two cards with the same number.
Guess first
The sorting value of both observation records is 2. Should one of them be deleted when sorting?
Show answer and explanation
No, both records should be retained. — Identical values do not mean identical records; sorting only changes the order and is not responsible for deduplication.
Then connect experience and science
Let’s spread out the records first
The letters of each card record the identity, and the numbers are the basis for sorting. The same number can appear multiple times, and the record cannot be discarded.
The input is a set of records, not just different numbers.
Only perform one specific action at a time
Movement progress, cards compared or exchanged are highlighted in orange. The program only looks at the values during the comparison phase and moves the complete records during the exchange phase.
Compare → decide whether to exchange
If you change the approach, the result will be the same
The original book gives pairwise exchange, finding the smallest first, and partition quick sorting. Different steps can obtain the same ascending value, but records with the same value may not maintain the original order.
SIMPLE / BETTER / QUICKSORT
As data increases, the number of steps becomes more important
The number of comparisons of the first two methods increases with N²; quick sort is usually about N log N, but it is not guaranteed to be the fastest for every input. The count is the actual measurement in this example, not the number of seconds the machine is running.
The number of comparisons, exchanges and actual time consumption should be distinguished
Expand the calculation
排序后：key₁ ≤ key₂ ≤ … ≤ keyₙ 排序前后：每条Record的身份与内容保持完整
This is an algorithm rules class, and there is no astronomical formula that can be obtained by substitution. The comparison determines the order, and the exchange must move the entire record; the same key value does not mean that the record can be discarded.
give it a try
Use the same set of cards to compare the three methods; drag the progress to 100%, check that the numbers are in ascending order and that the A-H records are still there.
No need to memorize symbols
- N
- Number of records, the screen for this lesson is 8
- Compare
- View the order of two values; quicksort also compares to the baseline value
- exchange
- Swap the two complete records
- base value
- Quick sort is used to divide the values on both sides
- stability
- Whether records with the same sort value maintain the original relative order
Algorithm, accuracy and scope of application
Original book, Chapter 6, printed pages 55–58, Table 6.A. Three algorithms are implemented: SIMPLE SORT compares and exchanges pair by pair according to the front and back positions, BETTER first finds the remaining minimum value and then exchanges, and QUICKSORT uses double pointer partitioning and explicit stack based on the middle element value. This lesson omits the details of the original BASIC optimizing the stack order according to the interval length, and retains the partition results and actual comparison/exchange traces; it does not claim that the worst case of quick sort is N log N. Demonstration card numbers have no real date units, letters only mark identities. Progress percentages map to discrete steps of the algorithm and show the true step number. Comparisons and exchanges are counted separately, except for running seconds; the order of records with the same value is not guaranteed to be stable. The introduction to string ASCII sorting at the end of the chapter is explained in the text, and the interaction only implements numerical sorting. The local AA+ did not find the special module for sorting, and the results were verified using independent native numerical sorting and per-step permutation invariants.
my understanding check
When comparing two records, must the data be exchanged immediately?
uncertain — Comparison and exchange are different actions, and they are exchanged only when the algorithm conditions are met.
If the numbers after sorting are the same, does it mean that the order of records with the same value must also be the same?
uncertain — Whether to retain the sequence relationship of records with the same value involves stability; the three implementations in this lesson do not provide stable sorting guarantees.
Can the number of seconds measured on the original computer be directly used as the time taken by today's web page?
Can't — Hardware, languages, and implementations vary; this lesson compares the number of reproducible operations and the number of seconds without reusing the old machine.
Sorting first ensures that the records are complete and in the correct order, and then compares the operating costs; records with the same values cannot be discarded as duplicate garbage.
Jean Meeus · Astronomical Algorithms, 2nd ed. · No. 6 chapter
General Algorithms and Numerical Computing · All interactive courses