Algorithm 4.3.1: Minimum Begin min – A[1]; For j — 2 Тo n Do If (A[j] < min) Then min – A[j]; End; |/ the if End; // the for-j loop Return (min); End.
Algorithm 4.3.1: Minimum Begin min – A[1]; For j — 2 Тo n Do If (A[j] < min) Then min – A[j]; End; |/ the if End; // the for-j loop Return (min); End.
Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
Related questions
Question
100%
If A is the array (1,-2,3,-4,5), what is the return value (min) of
![**Selection Sort and Minimum Finding Algorithm**
Selection sorts choose a particular element in the list (usually the smallest or the largest) and place it in the correct position; **MinSort** selects the minimum entry. First, let's construct an algorithm for finding the minimum entry in a list subject to the restriction that we can only compare two values at a time. We make a "pass" through the list, keeping track of the minimum value found so far in the variable `min`.
### Algorithm 4.3.1: Minimum
```plaintext
Begin
min ← A[1];
For j ← 2 To n Do
If (A[j] < min) Then
min ← A[j];
End; // the if
End; // the for-j loop
Return(min);
End.
```
This pseudo-code contains a new control structure, a **for-loop**, which looks like:
```plaintext
For variable ← expression1 To expression2 Do
(the body of the loop)
End;
```
The execution of this construction is the same as the following:
```plaintext
variable ← expression1;
While (variable <= expression2) Do
(the body of the loop)
variable ← variable + 1;
End;
```
For-loops are a natural way to manipulate arrays; the control variable starts at a particular value and increases by ones until reaching a second particular value.
To begin, the smallest so far is A[1]. Then, looking at A[2], A[3]... in turn, if one of these is smaller than the smallest so far, we change `min` to be that A-value. That is,
**“min is the smallest of A[1], A[2]...A[j]”**
is a loop invariant of the for-j loop. Then, the final value of `min` must be the smallest value in the whole list, obtained at the cost of (n - 1) comparisons. The cost of a sorting algorithm is usually the number of comparisons involving two array entries.
// comparisons involving values of the keys](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2Fa4792360-22b4-40c0-a48a-02ce03c9f6f7%2F7309393f-00d0-4c4b-a93b-561f3d3bc2ff%2F5xtb0ao_processed.png&w=3840&q=75)
Transcribed Image Text:**Selection Sort and Minimum Finding Algorithm**
Selection sorts choose a particular element in the list (usually the smallest or the largest) and place it in the correct position; **MinSort** selects the minimum entry. First, let's construct an algorithm for finding the minimum entry in a list subject to the restriction that we can only compare two values at a time. We make a "pass" through the list, keeping track of the minimum value found so far in the variable `min`.
### Algorithm 4.3.1: Minimum
```plaintext
Begin
min ← A[1];
For j ← 2 To n Do
If (A[j] < min) Then
min ← A[j];
End; // the if
End; // the for-j loop
Return(min);
End.
```
This pseudo-code contains a new control structure, a **for-loop**, which looks like:
```plaintext
For variable ← expression1 To expression2 Do
(the body of the loop)
End;
```
The execution of this construction is the same as the following:
```plaintext
variable ← expression1;
While (variable <= expression2) Do
(the body of the loop)
variable ← variable + 1;
End;
```
For-loops are a natural way to manipulate arrays; the control variable starts at a particular value and increases by ones until reaching a second particular value.
To begin, the smallest so far is A[1]. Then, looking at A[2], A[3]... in turn, if one of these is smaller than the smallest so far, we change `min` to be that A-value. That is,
**“min is the smallest of A[1], A[2]...A[j]”**
is a loop invariant of the for-j loop. Then, the final value of `min` must be the smallest value in the whole list, obtained at the cost of (n - 1) comparisons. The cost of a sorting algorithm is usually the number of comparisons involving two array entries.
// comparisons involving values of the keys
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
This is a popular solution!
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
Knowledge Booster
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.Recommended textbooks for you
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education