Programming Algorithms: Implementing Heap Sort and IDE Analysis

This assignment delves into the realm of programming algorithms, with a specific focus on the heap sort algorithm. It begins by defining algorithms and contrasting them with code, clarifying the fundamental differences between the two. The assignment then explores the characteristics of code, including data types, constants, variables, methods, control structures, iteration, scope, and parameter passing. It also touches on object-oriented programming concepts like classes, inheritance, and events. Furthermore, the assignment examines Integrated Development Environments (IDEs), detailing their features and functions, such as code editors, compilers, and debuggers. The core of the assignment involves the implementation of the heap sort algorithm in code, providing a practical application of the concepts discussed. Finally, it includes an investigation device exemption (IDE) submission checklist.

Programming algorithms
Page 1 of 34

CONTENTS
Table of Contents
1.0 INTRODUCTION.....................................................................................................................................................
2.0 Table of Contents:.....................................................................................................................................................
3.0 Difference between Algorithm and Code..................................................................................................................
4.0 Characteristics of code.............................................................................................................................................
5.0 Implementation........................................................................................................................................................
6.0 Review and reflection:............................................................................................................................................
7.0 Conclusion.............................................................................................................................................................
Page 2 of 34

Introduction
An algorithm specifies a series of steps that perform a particular computation or task.
Algorithms were originally born as part of mathematics – the word “algorithm” comes from the
Arabic writer Muḥammad ibn Mūsā al-Khwārizmī, – but currently the word is strongly
associated with computer science.
LO1
Define basic algorithms to carry out an operation and outline the process of programming an
application
Algorithm definition:
A sorting algorithm is an algorithm made up of a series of instructions that takes an array as
input, performs specified operations on the array, sometimes called a list, and outputs a sorted
array. Sorting algorithms are often taught early in computer science classes as they provide a
straightforward way to introduce other key computer science topics like Big-O notation, divide-
and-conquer methods, and data structures such as binary trees, and heaps. There are many
factors to consider when choosing a sorting algorithm to use.
Heap Sort is a popular and efficient sorting algorithm in computer programming. Learning how
to write the heap sort algorithm requires knowledge of two types of data structures - arrays
and trees.
The initial set of numbers that we want to sort is stored in an array e.g. [10, 3, 76, 34, 23,
32] and after sorting, we get a sorted array [3,10,23,32,34,76]
Heap sort works by visualizing the elements of the array as a special kind of complete binary
tree called heap.
Procedures to follow for Heapsort
Since the tree satisfies Max-Heap property, then the largest item is stored at the root node.
Remove the root element and put at the end of the array (nth position) Put the last item of the
tree (heap) at the vacant place.
Page 3 of 34

Reduce the size of the heap by 1 and heapify the root element again so that we have highest
element at root.
The process is repeated until all the items of the list is sorted.
// Java program for implementation of Heap Sort
public class HeapSort
{
public void sort(int arr[])
{
int n = arr.length;
// Build max heap
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// Heap sort
for (int i=n-1; i>=0; i--)
{
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
Page 4 of 34

// Heapify root element
heapify(arr, i, 0);
}
}
void heapify(int arr[], int n, int i)
{
// Find largest among root, left child and right child
int largest = i;
int l = 2*i + 1;
int r = 2*i + 2;
if (l < n && arr[l] > arr[largest])
largest = l;
if (r < n && arr[r] > arr[largest])
largest = r;
// Swap and continue heapifying if root is not largest
if (largest != i)
{
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
Page 5 of 34

heapify(arr, n, largest);
}
}
static void printArray(int arr[])
{
int n = arr.length;
for (int i=0; i < n; ++i)
System.out.print(arr[i]+" ");
System.out.println();
}
public static void main(String args[])
{
int arr[] = {1,12,9,5,6,10};
HeapSort hs = new HeapSort();
hs.sort(arr);
System.out.println("Sorted array is");
printArray(arr);
}
}
Page 6 of 34

Difference between Algorithm and Code
An algorithm is a well defined sequence of steps that provides a solution for a given problem,
while a code is one of the methods that can be used to represent an algorithm. While
algorithms can be written in natural language, code is written in a format that is closely related
to high level programming language structures. But code does not use specific programming
language syntax and therefore could be understood by programmers who are familiar with
different programming languages. Additionally, transforming an algorithm presented in code to
programming code could be much easier than converting an algorithm written in natural
language.
Preprocessor is a program that processes its input data to produce output that is used as input
to another program. The output is said to be a preprocessed form of the input data, which is
often used by some subsequent programs like compilers. The amount and kind of processing
done depends on the nature of the preprocessor; some preprocessors are only capable of
performing relatively simple textual substitutions and macro expansions, while others have the
power of full-fledged programming languages.
A compiler is a special program that processes statements written in a particular programming
language and turns them into machine language or "code" that a computer's processor uses.
Typically, a programmer writes language statements in a language such as Pascal or C one line
at a time using an editor. The file that is created contains what are called the source
statements. The programmer then runs the appropriate language compiler, specifying the
name of the file that contains the source statements.
Linker is a program that makes executable files. The linker resolves linkage issues, such as the
use of symbols or identifiers which are defined in one translation unit and are needed from
other translation units. Symbols or identifiers which are needed outside a single translation unit
have external linkage. In short, the linker's job is to resolve references to undefined symbols by
finding out which other object defines a symbol in question, and replacing placeholders with
the symbol's address. Of course, the process is more complicated than this; but the basic ideas
apply.
An interpreter translates high-level instructions into an intermediate form, which it then
executes. In contrast, a compiler translates high-level instructions directly into machine
language. Compiled programs generally run faster than interpreted programs. The advantage of
an interpreter, however, is that it does not need to go through the compilation stage during
which machine instructions are generated. This process can be time-consuming if the program
is long. The interpreter, on the other hand, can immediately execute high-level programs. For
Page 7 of 34

this reason, interpreters are sometimes used during the development of a program, when a
programmer wants to add small sections at a time and test them quickly. In addition,
interpreters are often used in education because they allow students to program interactively.
LO2 Explain the characteristics of procedural, object-orientated and event driven
programming. Conduct an analysis of a suitable Integrated Development Environment (IDE)
Characteristics of code:
A data type defines what kind of value a column can hold: integer data, character data,
monetary data, date and time data, binary strings, and so on. Such as Boolean, Numbers, String
values, Arrays, Objects, NULL, MISSING, Collation, Date, Binary.
A constant is an identifier (name) for a simple value. As the name suggests, that value cannot
change during the execution of the script (except for magic constants, which aren't actually
constants). A constant is case-sensitive by default. By convention, constant identifiers are
always uppercase.
A variable is any factor, trait, or condition that can exist in differing amounts or types. An
experiment usually has three kinds of variables: independent, dependent, and controlled. The
independent variable is the one that is changed by the scientist.
Method is a procedure, technique, or way of doing something, especially in accordance with a
definite plan. a manner or mode of procedure, especially an orderly, logical, or systematic way
of instruction, inquiry, investigation, experiment, presentation, etc.
Page 8 of 34

A control structure is a block of programming that analyzes variables and chooses a direction in
which to go based on given parameters. The term flow control details the direction the program
takes (which way program control "flows").
Iteration is the act of repeating a process, either to generate an unbounded sequence of
outcomes, or with the aim of approaching a desired goal, target or result. Each repetition of the
process is also called an "iteration", and the results of one iteration are used as the starting
point for the next iteration.
Scope is an object that refers to the application model. It is an execution context for
expressions. Scopes are arranged in hierarchical structure which mimic the DOM structure of
the application. Scopes can watch expressions and propagate events.
Parameter passing The mechanism used to pass parameters to a procedure (subroutine) or
function. The most common methods are to pass the value of the actual parameter (call by
value), or to pass the address of the memory location where the actual parameter is stored (call
by reference).
In object-oriented programming, a class is an extensible program-code-template for creating
objects, providing initial values for state (member variables) and implementations of behavior
(member functions or methods).
In object-oriented programming, inheritance is the concept that when a class of objects is
defined, any subclass that is defined can inherit the definitions of one or more general classes.
This means for the programmer that an object in a subclass need not carry its own definition of
data and methods that are generic to the class (or classes) of which it is a part. This not only
speeds up program development; it also ensures an inherent validity to the defined subclass
object (what works and is consistent about the class will also work for the subclass).
Page 9 of 34

Events enable a class or object to notify other classes or objects when something of interest
occurs. The class that sends (or raises) the event is called the publisher and the classes that
receive (or handle) the event are called subscribers. 1
In a typical C# Windows Forms or Web application, you subscribe to events raised by controls
such as buttons and list boxes. You can use the Visual C# integrated development environment
(IDE) to browse the events that a control publishes and select the ones that you want to handle.
The IDE automatically adds an empty event handler method and the code to subscribe to the
event.
An Integrated Development Environment (IDE) is an application that facilitates application
development. In general, an IDE is a graphical user interface (GUI)-based workbench designed
to aid a developer in building software applications with an integrated environment combined
with all the required tools at hand.
Most common features, such as debugging, version control and data structure browsing, help a
developer quickly execute actions without switching to other applications. Thus, it helps
maximize productivity by providing similar user interfaces (UI) for related components and
reduces the time taken to learn the language. An IDE supports single or multiple languages.
An integrated development environment (IDE) is an application that facilitates application
development. IDEs are designed to encompass all programming tasks in one application.
Therefore, IDEs offer a central interface featuring all the tools a developer needs, including the
following:
Code editor: This feature is a text editor designed for writing and editing source code. Source
code editors are distinguished from text editors because they enhance or simplify the writing
and editing of code.
Compiler: This tool transforms source code written in a human readable/writable language into
a form executable by a computer.
Debugger: This tool is used during testing to help debug application programs.
Page 10 of 34

Build automation tools: These tools automate common developer tasks.
In addition, some IDEs might also include the following:
Class browser: This tool is used to examine and reference the properties of an object-oriented
class hierarchy.
Object browser: This feature is used to examine the objects instantiated in a running
application program.
Class hierarchy diagram: This tool allows the programmer to visualize the structure of object-
oriented programming code.
Typical integrated development tools:
o editor (with auto-indent, auto-completion, colorization, …) ;
o version control ;
o compiler/builder ;
o documentation extractor ;
o debugger ;
o testing tools ;
o Refactoring tools.
Page 11 of 34

LO3 Implement basic algorithms in code using an IDE
Implementation:
Investigational Device Exemption (IDE) Submission Checklist
Please check ()
1. Cover Letter
Statement that submission is an original IDE application
Sponsor Information (Name, Address)
Sponsor Contact (Name, Telephone Number, Fax)
Device Name and Intended Use
Manufacturer Information (Name, Address)
Manufacturer Contact (Name, Telephone Number, Fax)
If an investigation involves an exception from informed consent for emergency research, state in
the Cover Letter that the investigation is subject to 21 CFR 50.24 requirements.
Other Information in Cover Letter (as appropriate):
Pre-IDE/Pre-IDE meetings: Describe your contacts with the FDA review division. If a Pre-IDE
document was submitted, state the Pre-IDE number and name of FDA contact, if known, who
reviewed the Pre-IDE. If a Pre-IDE meeting occurred, give name of FDA contact person and copy of
meeting minutes.
Waiver Requests: Identify any requests for waivers and include a justification for the waiver.
Referenced Files: Identify any files by reference (for example, approved PMA, 510(k), IDE, Device
Master File).
Note: If you are not the holder of these referenced files, include a letter from the holder of the
files, which grants FDA permission to reference the files in its review of your current application.
2. Table of Contents
Provide a detailed Table of Contents page
Page 12 of 34