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 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.
So 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. Let's make a "pass"
through the list keeping track of the minimum value we’ve found so far in the
variable min.
Algorithm 4.3.1: Minimum
Begin
min – A[1];
For j
If (A[j] < min) Then
min + A[j];
+ 2 To n Do
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:
//
For variable –
expression1 To expression2 Do
//
//
//
(the body of the loop)
End;
//
// The execution of this construction is the same as the following:
//
variable
//
expression1;
While (variable <= expression2) Do
(the body of the loop)
variable + 1;
//
//
//
variable +
// End;
//
// For-loops are a natural way to manipulate arrays; the control variable starts at a
// particular value and goes up by ones until it reaches 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, and it was obtained at the cost of (n
1) comparisons. The
cost of a sorting algorithm is usually taken to be 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 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.
So 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. Let's make a "pass"
through the list keeping track of the minimum value we’ve found so far in the
variable min.
Algorithm 4.3.1: Minimum
Begin
min – A[1];
For j
If (A[j] < min) Then
min + A[j];
+ 2 To n Do
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:
//
For variable –
expression1 To expression2 Do
//
//
//
(the body of the loop)
End;
//
// The execution of this construction is the same as the following:
//
variable
//
expression1;
While (variable <= expression2) Do
(the body of the loop)
variable + 1;
//
//
//
variable +
// End;
//
// For-loops are a natural way to manipulate arrays; the control variable starts at a
// particular value and goes up by ones until it reaches 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, and it was obtained at the cost of (n
1) comparisons. The
cost of a sorting algorithm is usually taken to be 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