The sorting algorithm is the content of the data structure discipline, in which the internal sorting existing algorithms have many kinds, what is the characteristics of each? This brings graph design realizes the commonly used internal sorting algorithm and compares. Sort by bubbling, direct insertion, simply sequencing, rapid sorting, stack sorting, test comparison for the number of comparisons of keywords, and number of movements.
Problem analysis and overall design
ADT ORDERABLIST {data object: d = {ai | ai∈integerseet, i = 1, 2, ..., n, n ≥ 0} Data relationship: r1 = {
The keywords of the elements to be row table are integers. Test comparisons with different data in positive order, reverse order, and different dilution, test comparison of the number of comparisons of keywords (keyword exchange accounts 3 times) . Requires display information, the user inputs the number of the table length (100-1000) and the number of different test data (8-18) by the keyboard (8-18). Each test is completed, requiring the column performance to be compared. Require the results analysis.
Detailed Design 1, Bubble Sort Algorithm: Core Thought is to scan data list and find two adjacent items that appear. When these two projects are found, the location of the project is swapped and then continues to scan. Repeat the above operation until all items are placed in order
Bubblesort (Struct REC R [], INT N) {INT I, J; Struct REC W; unsigned long int compare = 0, MOVE = 0; for (i = 1; i <= n-1; i ) for (J = N; j> = i 1; j -) {if (r [j] .key 2. Direct insertion sorting algorithm: After I-1, L [1..i-1] has a sequence. The second handling only the L [I] inserts the appropriate position of L [1..i-1] such that L [1..i] is a sequence of sequence. To achieve this, we can use the method of comparing. First compare L [I] and L [I-1], if L [I-1] ≤ L [i], then L [1..i] has been ranked, the clutch is over; otherwise L [I] and L [I-1] position, continue to compare L [I-1] and L [I-2] until a certain position j (1 ≤ J ≤ i-1) makes L [J ] ≤ L [J 1] INSERTSORT (Struct Rec R [], INT N) {INT I, J; UNSIGNED long int compare = 0, MOVE = 0; for (i = 2; i <= n; i ) {compare ; r [0] = r [I]; Move ; J = I-1; while (r [0] .key {r [j]; j -; move ; compare;} r [j 1] = R [0]; Move ; "Printf (" / ninsertsort compare =% LD, Move);} 3, simply sequencing the sorting algorithm: First find the smallest data in the data list, Then use this data to switch the position in the first data; next to the second small data, then exchange it with the second data exchange position, and so on. SelectSort (Struct REC R [], INT N) {Unsigned long int compare = 0, MOVE = 0; INT I, J, K; Struct REC W; For (i = 1; i <= n-1; i ) { K = i; for (j = i 1; j <= n; j ) {if (r [j] .key> r [k] .key) {k = j; compare ;} w = r [i]; r [i] = r [k]; r [k] = W; Move = MOVE 3; }} printf ("/ nselectsort compare =% ld, move =% ld / n", compare, move);} 4. Quick Sort Algorithm: First check the number of data in the data list, if less than two, then exit the program. If there are more than two data, select a split point to divide the data into two parts, less than the split point of the data is placed in one group, and the rest is placed in another group, and then sorted two sets of data. Usually the data of the split point is randomly selected. This is similar to whether your data has been arranged, the size of the two word lists you divide is almost almost. And as long as the size of the two sub-lists is almost q (struct rec r [], int S, int T) {INT i = S, J = T; IF (S 5. Pile Sort (1) Basic idea: Heap Sort is a tree selection sort, in the ordering process, the R [1..n] is regarded as a complete binary tree, using a completed binary tree The intrinsic relationship between points and children's nodes is selected to select the smallest element. (2). The definition of the heap: Sequences K1, K2, K3, ..., Kn of n elements are called a heap, when and only when the sequence is satisfied: Ki ≤ K2i Ki ≤ K2i 1 (1 ≤ i ≤ [N / 2]) SIFT (Struct REC R [], INT L, INT M) {INT I, J; Struct REC W; I = L; J = 2 * I; W = R [I]; While J <= m) {IF (j Heapsort (Struct Rec R [], INT N) {unsigned long int compare = -1, move = -1; struct REC W; INT i; int A; for (i = n / 2; i> = 1; i- -) A = SIFT (R, I, N); COMPARE ; MOVE ; For (i = n; i> = 2; I -) {w = r [i]; r [i] = r [1]; r [1] = W; A = SIFT (R, 1, I- 1); Compare = a; Move = a;}} Summary: 1. Learn to use a random function randomize () to set the initial value to add #include 2 in the header file. Basically before doing this procedure, 3. Summary of the sorting algorithm: (1) If N is smaller (such as N ≤ 50), direct insertion or direct selection can be used. When the record size is small, the direct insertion sort is better; otherwise, because the number of records directly selects the mobile recorder is less than the direct plug, the selection is selected to be selected. (2) If the file initial state is basically orderly (refer to the positive order), the quick sorting of direct interceptors, bubble or random should be selected; (3) If N is large, the time complexity should be used as O (NLGN) Sorting method: rapid sorting, stack sorting or sorting. Rapid sorting is currently considered to be the best method based on the internal sort of comparison. When the keyword to be sorted is randomly distributed, the average time of rapid sorting is shortest; the auxiliary space required for the stacking routine is less sorted, and not There will be worst cases that may appear rapidly. These two sorts are unstable.
