- Science
- Computer Science
- Algorithms
-
Flashcards
-
Learn
-
Test
-
Match
-
Flashcards
-
Learn
-
Test
-
Match
Terms in this set (19)
Students also viewedSets found in the same foldercomputer science
Verified answer
computer science
Relate to a recursive sorting algorithm called QuickSort, which is described as follows: A one-element list is already sorted; no further work is required. Otherwise, take the first element in the list, call it the pivot element, then walk through the original list to create two new sublists, $L_{1}$ and $L_{2}.$ $L_{1}$ consists of all elements that are less than the pivot element and $L_{2}$ consists of all elements that are greater than the pivot element. Put the pivot element between $L_{1}$ and $L_{2}.$ Sort each of L1 and L2 using QuickSort (this is the recursive part). Eventually all lists will consist of 1 element sublists separated by previous pivot elements, and at this point the entire original list is in sorted order. This is a little confusing, so here is an example, where pivot elements are shown in brackets: Original list: 6, 2, 1, 7, 9, 4, 8; After 1st pass: 2, 1, 4, [6], 7, 9, 8; After 2nd pass: 1, [2], 4, [6], [7], 9, 8; After 3rd pass: 1, [2], 4, [6], [7], 8, [9] Sorted. How many comparisons between list elements are required for pass 1 of QuickSort on an n-element list?
Verified answer
computer science
Verified answer
computer science
Verified answer
Recommended textbook solutions
An algorithm is a procedure for solving a problem in terms of the actions to be executed and the order in which those actions are to be executed. An algorithm is merely the sequence of steps taken to solve a problem. The steps are normally "sequence," "selection, " "iteration," and a case-type statement.
In C, "sequence statements" are imperatives. The "selection" is the "if then else" statement, and the iteration is satisfied by a number of statements, such as the "while," " do," and the "for," while the case-type statement is satisfied by the "switch" statement.
Pseudocode is an artificial and informal language that helps programmers develop algorithms. Pseudocode is a "text-based" detail (algorithmic) design tool.
The rules of Pseudocode are reasonably straightforward. All statements showing "dependency" are to be indented. These include while, do, for, if, switch. Examples below will illustrate this notion.
GUIDE TO PSEUDOCODE LEVEL OF DETAIL: Given record/file descriptions, pseudocode should be created in sufficient detail so as to directly support the programming effort. It is the purpose of pseudocode to elaborate on the algorithmic detail and not just cite an abstraction.
Examples:
1..
If student's grade is greater than or equal to 60
- Print "passed"
- Print "failed"
endif
2.
Set total to zero
Set grade counter to one
While grade counter is less than or equal to ten
- Input the next grade
- Add the grade into the total
endwhile
Set the class average to the total divided by ten
Print the class average.
3.
Initialize total to zero
Initialize counter to zero
Input the first grade
while the user has not as yet entered the sentinel
- add this grade into the running total
- add one to the grade counter
- input the
next grade (possibly the sentinel)
endwhile
if the counter is not equal to zero
- set the average to the total divided by the counter
- print the average
else
- print 'no grades were entered'
endif
4.
initialize passes to zero
initialize failures to zero
initialize student to one
while student counter is less than or equal to ten
- input the next exam result
- if the student passed
- add
one to passes
else
- add one to failures
- add one to student counter
endif
endwhile
print the number of passes
print the number of failures
if eight or more students passed
- print "raise tuition"
endif
Some Keywords That Should be Used And Additional Points
For looping and selection, The keywords that are to be used include Do While...EndDo; Do Until...Enddo; While .... Endwhile is acceptable. Also, Loop .... endloop is also VERY good and is language independent. Case...EndCase; If...Endif; Call ... with (parameters); Call; Return ....; Return; When;
Always use scope terminators for loops and iteration.
As verbs, use the words Generate, Compute, Process, etc. Words such as set, reset, increment, compute, calculate, add, sum, multiply, ... print, display, input, output, edit, test , etc. with careful indentation tend to foster desirable pseudocode. Also, using words such as Set and Initialize, when assigning values to variables is also desirable.
More on Formatting and Conventions in Pseudocoding
Do not include data declarations in your pseudocode.
Function Calls, Function Documentation, and Pseudocode
- Call FunctionName (arguments: field1, field2, etc.)
- Return (field1)
- FunctionName (parameters: field1, field2, etc. )
- Call FunctionName
(arguments: pointer to fieldn, pointer to field1, etc.)
- FunctionName (parameters: pointer to field1, pointer to field2, ...)
- Return (pointer to fieldn)
Source Code
SPELLING ERRORS ARE NOT ACCEPTABLE