ABOUT MODIFIND

I. Correspondence with Paul E. Black
I sent (2
April 1999) to the forum comp.programming and comp.theory the following subject Three Selection Algorithms:
Hello,
could you read my article FIND, SELECT, MODIFIND, please? See: http://www.geocities.com/SiliconValley/Garage/3323/3alg.html
Abstract:
Hoare's FIND (the H algorithm); Algorithms Z and FR are always better than H; FR has lesser the number of comparison than Z; Z has lesser the number of swaps than FR. When the number of swaps isn't critical then is FR better than Z  and vice versa.
Paul E. Black wrote me on the 6th April 1999:
Dear Dr. Zabrodsky:
I saw your posting on comp.theory and was impressed with your article "Three Algorithms for Finding Kth Smallest of N Elements". I volunteered to be the area editor for Algorithms, Data Structures, and Problems of the new CRC Dictionary of Computer Science, Engineering and Technology. Algorithms, Data Structures, and Problems Terms and Definitions I plan for this site to be an online reference for the entire computer science community. I am recruiting people to add terms and definitions or check current definitions. Would you contribute?
Sincerely,
I replied him 12 April 1999:
Dear Dr Black,
I can offer you: 1) A succint definition of the Selection problem (entries Selection problem, select kth element in your dictionary). Given an array A of N elements and an the positive integer K <= N, determine the Kth smallest element of A and rearrange the array in such a way that
A[1], A[2], ..., A[K1] <= A[K] <= A[K+1], ..., A[N]
2) The N. Wirth's implementation of the Hoare's algorithm
FIND in Pascal (for the array X of integers).
3) V. Zabrodsky's algorithm MODIFIND (in Pascal), the simple
improvement of FIND, which has lesser the number of swaps than
FIND.

You can use an arbitrary part of my article "Three Algorithms for Finding Kth Smallest of N Elements" as well as. Regards Vladimir Zabrodsky And Dr. Black replied me on the 12th April 1999:
Dear Mr. Zabrodsky;
Thank you for your contribution. I have added the definitions and algorithms.
Sincerely,
paul
II. Why MODIFIND? Short History of my Algorithm
I discovered a strange behaviour of the Find algorithm in June 1989. I found the simple modification of the Find algorithm. A first implementation was written in the Rexx language but later I worked only with Pascal's versions. During autumn 1990 I wrote my article Finding Kth
Smallest of N Elements. I sent this paper to the Czech computer magazin Bajt. But my paper didn't even printed in winter 1991. I revised, corrected and extended my article and I sent it again with poetic or music title Variation on the classic theme to another Czech computer magazin Elektronika (with permission from Bajt). It was published in No. 6 (June) 1992 on pages 3334 [5]. But in Bajt, No. 8 1992 on pages 130131 [6], was published the old version my paper, too! In these papers I called the Hoare's algorithm Find as P1 (the abbreviation from first procedure) and my modification as P2 (I resisted temptation named it QUICKFIND). In my notes (three notebooks A4 every with 40 sheets of paper) I described my algorithm sometimes as Fnd. In WEB's and Rexx's version I used the name Z (and H and FR). But for Dr. Black's dictionary I think Z it isn't a lifelike name for selection algorithm  I wrote MODIFIND in my mail ...
III. Notes on Proof of S(N, K)
The number of swaps made by MODIFIND in average case is:
To do the averagecase analysis I used exercises 5.2.22 and following from the D. E. Knuth's book [7]. Is it the same method as for Find? Yes, it is. My explanation follows. See on this example.
In the first step Find pushs aside left all elements lesser or equal 4 (i.e. four elements) and it will find in the second step 3rd smallest element in the subarray 9, 8, 7, 5, 6. MODIFIND stops work with the number 4, when it know that 4 can't be 7th smallest element. It will find 5th smallest element in the subarray 8, 9, 1, 2, 7, 5, 6. But the swaps the numbers 1 and 2 are unnecessary! This numbers don't change your position during execution of the MODIFIND algorithm. We can suppose (for the averagecase analysis, counting swaps) that MODIFIND finds in the second step 3rd smallest element in the subarray 8, 9, 7, 5, 6. The average number of swaps that will have been made in the first step is: ((K  1) (N  K) / 2N) + (N  1) / N We thus obtain the reccurence relation for the average number of swaps in the complete MODIFIND (inspiration from D. E. Knuth): IV. Succint definition of selection problem
C. A. R. Hoare wrote in [1]:
The purpose of the program Find is to find that element of an array A[1:N] whose value is fth in order of magnitude; and to rearrange the array in such a way that this element is placed in A[f]; and furthermore, all elements with subscribts lower than f have lesser values, and all elements with subscripts greater than f have greater values. Thus on completion of the program, the following relationship will hold:
A[1], A[2], ... , A[f  1] <= A[f] <= A[f + 1], ... , A[N]
In [2] R. W. Floyd and R. L. Rivest wrote: The selection problem can be succinctly stated as follows: given a set X of n distinct numbers and an integer i, 1 <= i <= n, determine the ith smallest element of X with as few comparisons as possible. The ith smallest element, denoted by i o X, is that element which is larger than exactly i  1 other elements, so that 1 o X is the smallest, and n o X the largest, element in X.
In [3] R. W. Floyd and R. L. Rivest wrote: SELECT will rearrange the values of array segment X[L : R] so that X[K] (for some given K; L <= K <= R) will contain the (K  L + 1)th smallest value, L <= I <= K will imply X[I] <= X[K], and K <= I <= R will imply X[I] >= X[K]. In [4] we can read: The input to our selection routine will be the positive integer N, the array X[1 .. N], and the positive integer K <= N. The program must permute the array so that X[1 .. K  1] <= X[K] <= X[K + 1 .. N]. At that point, the K^{th}smallest element in the set resides in its proper position, X[K]. My article FIND, SELECT, MODIFIND includes the definition: The selection problem can be stated as follows (C. A. R. Hoare in [1]): given an array A of N distinct elements and an integer K, 1 <= K <= N, determine the Kth smallest element of A and rearrange the array in such a way that this element is placed in A[K] and all elements with subscripts lower than K have lesser values and all elements with subscripts greater than K have greater values. Thus on completion of the program, the following relationship will hold:
My succint definition of selection problem:
I send to Dr. Black following definition:
Given an array A of N elements and an the positive integer K <= N, determine the Kth smallest element of A and rearrange the array in such a way that
In this definition Dr. Black in Algorithms, Data Structures, and Problems
Terms and Definitions (term select and partition problem) mistaked the word rearrange with the word partition: The dictionary says: select and partition(classic problem) Definition: Given an array A of n elements and a positive integer k <= n, find the k^{th} smallest element of A and partition the array such that A[1], ..., A[k1] <= A[k] <= A[k+1], ..., A[n].
Literature
1. C. A. R. HOARE: Proof of a Program: FIND CACM, Vol 14,
No. 1, January 1971, pp. 3945
2. R. W. FLOYD, R. L. RIVEST: Expected Time Bounds for Selection. CACM, March 1975, Vol. 18, No. 3, pp. 165172
3. R. W. FLOYD, R. L. RIVEST: Algorithm 489 The Algorithm SELECT  for Finding the ith Smallest of n Elements [M1] CACM, March 1975, Vol. 18, No. 3, p. 173
4. J. BENTLEY: Selection (in Programming Pearls) CACM, November 1985, Vol. 28, No. 11, pp. 11211127
5. V. ZABRODSKY: Variace na klasicke tema Elektronika, No. 6 1992, p. 3334
6. V. ZABRODSKY: Nalezeni kteho nejmensiho prvku Bajt, No. 8 1992, p. 130131
7. D. E. KNUTH: The Art of Computer Programming. Sorting and Searching AddisonWesley, Reading, Mass., 1973

last modified 24th April 2002
Copyright © 19982002 Vladimir Zabrodsky
Czech Republic