3.2.6 Sorting Techniques

• 2.6 SORTING TECHNIQUES

• WHY IS EFFICIENT SORTING SO IMPORTANT?
• Sorting is very important so we can carry out efficient Binary Searches on large databases.
• Interactive systems rely on data being retrieved from these systems quickly.
• For example :  Amazon

• BUBBLE SORT
• Start at the beginning of the list.
• Compare each pair of items.
• If they are not in order swap them.
• Work through the list n-1 times.
• Let’s look at an example.....

•  BUBBLE SORT EXAMPLE

  

• INSERTION SORT
• Advantage
• Faster than a Bubble Sort 

• Disadvantage
• More complex to code.

• In an Insertion Sort each element in turn is inserted into its correct place in the sorted list.
• The next element to be inserted into the correct place is shown in red.  The sorted part of the list is green

3.2.6 Searching Techniques

3.2.6 SEARCHING TECHNIQUES

• WHY IS EFFICIENT SEARCHING SO IMPORTANT?
• Most of the data stored by organisations is stored in Computerised Databases.  Some databases have millions of records.
• Interactive systems rely on data being retrieved from these systems quickly.
• For example : Cash Machines

• LINEAR SEARCH
• A Linear Search...
• Start at the beginning of the list.
• Compare each item in the list with the search item.
• Stop when the item is found or when the end of the list is reached.

• LINEAR SEARCH EXAMPLE
• Imagine we need to find the phone number for a student called Keith Fit in an unsorted  list of 15 students...
• We may have to access up to 15 records to find the record we need. This time it took 10 reads.

1.       Rhys                                 7788

2.       Domingo                        6545

3.       Hayden                           3987

4.       Iris                                     9009

5.       Kayla                                7886

6.       Abdul                               2345

7.       Kay                                   5843

8.       John                                 7996

9.       Sally                                  0191

10.   Keith                                6109

11.   Carla                                 7685

12.   Donna                             4243

13.   Miles                                7658

14.   Raul                                  3424

15.   Saul                                  0055

• Advantages
• This technique is very simple to code.
• A Linear Search works with an unsorted list.
• Disadvantage
• Linear Searches are slow, especially with large lists.

• BINARY SEARCH
• A Binary Search of a Sorted List...
• Find the Middle Item of the Current Search List.
• Check if the Current Item is the Search Item.
• If not then make the Current Search List either the Higher Half or the Lower Half of the list.
• Go to Step 1
• Advantage
• Much Faster than a Linear Search, especially as the List increases in size.
• 
  Calculate the Maximum Reads for a file of 1000 records..

• Disadvantages.....
• The List needs to be Sorted.
• A Binary Search is more
• Complex to Code.

and searching

• Google creates millions of indexes of web-pages.  These are lists of pages sorted by their subjects.
• Without these indexes Google would not be able to use a binary search and would not be able to return your search results so quickly. Without these indexes your search would take days!!!
• This is how it works...
• http://www.youtube.com/watch?v=BNHR6IQJGZs&feature=related

• Summary
• Efficient Searching is very important because…
• We don’t want to wait for data retrieval in ICT systems
• Large number of records to search

• Linear Search Characteristics…
• Look at each item in order
• Slow in comparison to a Binary Search
• List needs not to be sorted- simple

• Binary Search Characteristics…
• Fast in comparison to Linear Search
• Complex to code
• List has to be sorted

3.2.5 Binary Trees and Binary Tree Traversals

3.2.5 Binary Trees and Binary Tree Traversals

Binary Trees

A Binary Tree is a graph with a

Root Node whose Left Pointer points to the Left Sub-Tree and whose Right Pointer points to the Right Sub-Tree where each Sub-Tree is a Binary Tree.

    This is a   Recursive   Definition

Why Binary Trees?

Much like with Linked Lists, Binary Trees can store data in an ordered format without the need for time consuming moving of data.

They also speed up the process of searching a database.

Breadth-First and Depth-First Traversals

There are different ways of searching or extracting data from Binary Trees.  These split into two main types...

•       Breath-First Traversals

•       Depth-First Traversals

Breadth-First Traversal

Start with the Root Node and visit each of its Child Nodes

Take each of those Nodes and visit each of its child nodes

And so on...

Depth-First Traversal

There are three types of Depth-First Traversal

•       In-Order Traversal

Left-Tree, Root, Right Tree

•       Pre-Order Traversal

Root, Left-Tree, Right Tree

•       Post-Order Traversal

Left-Tree, Right-Tree, Root

3.2.4 Stacks and Queues

2.4 Stacks and Queues

Data structures

àDynamic data structures

Stacks

E.g. Used to store return addresses for procedures or functions (recursion)

LIFO- Last in First Out

If the stack is full then an overflow error occurs

Queues

Eg printer queues

They are circular

LILO- Last In Last Out

3.2.3 Lists and Pointers

2.3 Lists & Pointers

Abstract Data Types

•       Programming Languages use Data Types such as : Integer, Real, String, Date etc…

•       Abstract Data Type – a data type whose properties are specified independent of any programming language.

•       For example -                   

•       List –     a collection of elements with an                inherent order.

List Operations

These operations are required for a list:

•       Initialise List

•       Insert Element

•       Find Element

•       Delete Element

•       Length of List

•       Output the List

Types of List

Linear List

•       Items are stored in linear order in the list.

•       Linear lists are simple, but slow and inefficient.

Linked List

•       Items are stored in the next available space and pointers used to link the elements.

•       Linked Lists are complex to code but fast and efficient to use.

Inserting an Element into a Linked List

Pointer

A variable that contains an address.  The Pointer points to the memory location with that address.

Null Pointer

A pointer that points to nothing.  Usually Ø or -1

Programming Linked Lists

•       Linked Lists can be programmed using 2 dimensional arrays. 

•       New values can be inserted without shifting any other values.

•       Value can still be output in order.

3.2.2 Recursive techniques

2.2 Recursive techniques

Iterative loop

A sequence if statements which are repeated without jumping out of loop e.g. FOR loop

Recursive loop

A function which calls itself to produce a looping effect.

e.g 4 Factorial = 4 x 3 x 2 x 1

Base case stops series of function calls stopping the infinite loop.

An infinite loop results in a stack overflow error

General case- recursion part

The role of the stack

the stack stores the return addresses of functions or procedures which are calls recursively.

The stack is LIFO- (Last In First Out) so as the function reaches their end return addresses are returned to the correct function

3.2.1 Programming Language Paradigms

Programming Language Paradigms

What is a Programming Language?

A formal language for describing computation

A “user interface” to a computer

Syntax + semantics

Compiler, or interpreter, or translator

A tool to support a programming paradigm

A programming language is a notational system for describing computation in a machine-readable and human-readable form. — Louden

Generations of Programming Languages

1GL:       Machine Code Languages

2GL:       Assembly Language

3GL:       Imperative/Procedural Languages  (machine-independent) (FORTRAN, Pascal, C ...)

4GL+:    Event Driven and OOP Languages  (Visual Basic. Net)

Each generation is at a higher level of abstraction

Programming Languages Paradigms

We divide 3GL and 4GL Languages into different styles or methodologies of language known as : Paradigms

A Brief Chronology of 3GL and 4GL Programming Languages

Example Imperative/Procedural Language : Fortran

History

John Backus (1953) sought to write programs in conventional mathematical notation, and generate code comparable to good assembly programs.

No language design effort (made it up as they went along)

Most effort spent on code generation and optimization

FORTRAN I released April 1957; working by April 1958

The current standard is FORTRAN 2003
(FORTRAN 2008 is work in progress)

Innovations

Symbolic notation for subroutines and functions

Assignments to variables of complex expressions

DO loops

Comments

Input/output formats

Machine-independence

Successes

Easy to learn; high level

Promoted by IBM; addressed large user base

(scientific computing)

                “Hello World” in FORTRAN

PROGRAM HELLO

                DO 10, I=1,10

                PRINT *,'Hello World'

10           CONTINUE

                STOP

                END

Example Imperative/Procedural  Language : ALGOL 60

History

Committee of PL experts formed in 1955 to design universal, machine-independent, algorithmic language

First version (ALGOL 58) never implemented; criticisms led to ALGOL 60

Innovations

BNF (Backus-Naur Form) introduced to define syntax (led to syntax-directed compilers)

First block-structured language; variables with local scope

Structured control statements

Recursive procedures

Variable size arrays

Successes

Highly influenced design of other PLs but never displaced FORTRAN

“Hello World” in BEALGOL

BEGIN

FILE F (KIND=REMOTE);

EBCDIC ARRAY E [0:11];

REPLACE E BY "HELLO WORLD!";

WHILE TRUE DO

                                BEGIN

                                WRITE (F, *, E);

                                END;

END.

Example Imperative/Procedural  Language : COBOL

History

Designed by committee of US computer manufacturers

Targeted business applications

Intended to be readable by managers (!)

Innovations

Separate descriptions of environment, data, and processes

Successes

Adopted as de facto standard by US DOD

Stable standard for 25 years

Still the most widely used PL for business applications (!)

“Hello World” in COBOL

000100 IDENTIFICATION DIVISION.

000200 PROGRAM-ID.     HELLOWORLD.

000300 DATE-WRITTEN.   02/05/96        21:04.

000400* AUTHOR BRIAN COLLINS

000500 ENVIRONMENT DIVISION.

000600 CONFIGURATION SECTION.

000700 SOURCE-COMPUTER. RM-COBOL.

000800 OBJECT-COMPUTER. RM-COBOL.

001000 DATA DIVISION.

001100 FILE SECTION.

100000 PROCEDURE DIVISION.

100200 MAIN-LOGIC SECTION.

100300 BEGIN.

100400                  DISPLAY " " LINE 1 POSITION 1 ERASE EOS.

100500                  DISPLAY "HELLO, WORLD." LINE 15 POSITION 10.

100600                  STOP RUN.

100700 MAIN-LOGIC-EXIT.

100800                  EXIT.

“Hello World” in Functional Languages

SML  print("hello world!\n");

Haskell  hello() = print "Hello World"

Example Logic Language : Prolog

History

Originated at U. Marseilles (early 1970s), and compilers developed at Marseilles and Edinburgh (mid to late 1970s)

Innovations

Theorem proving paradigm

Programs as sets of clauses: facts, rules and questions

Computation by “unification”

Successes

Prototypical logic programming language

Used in Japanese Fifth Generation Initiative

“Hello World” in Prolog

hello :- printstring("HELLO WORLD!!!!").

printstring([]).

printstring([H|T]) :- put(H), printstring(T).

Object-Oriented Languages – a problem is broken down into Objects which contain data and processes.

OOP - Diagrams

Inheritance Diagram   

Objects/Attributes/Methods

Object Oriented Programming Terms

Object                          A real world item which we store data about

Class                              Groups of objects with the same attributes and methods

Base Class                   Top class in the Inheritance Diagram

Sub Class                     Stores attributes and methods of parent class, and adds some of its own

Inheritance                  Is where sub classes take the attributes and methods of a parent class

Polymorphism          One class morphs into multiple subclasses

Containment             A class contains attributes and methods in one unit

Bundle                         Bundle together attributes and methods

Instance                       An object is an instance of a class

Encapsulation           Bundles methods and data