3-2-6 Sorting

Why is efficient sorting so important?

• So we can carry out binary searches on large databases
• Interactive systems rely on data being retrieved from these systems quickly.

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.

Insertion Sort:

In an Insertion Sort, we divide the list into a sorted part and an unsorted part (to begin with, only the first item in the list is sorted). The next element is the new Current element, and it is compared with the first one and sorted. This goes on with each elemebt until the list is sorted completely.

The next element to be inserted into the correct place is shown in red.  The sorted part of the list is green.

Advantage:

• Faster than a Bubble sort.

Disadvantage:

• Harder to code.

Quicksort: 

• A sorting method developed by Tony Hoare in the 1960's.
• The idea is to divide and conquer: split the list into 2 parts, one containing values less than a pivot value, the others containing values greater than it.
• The pivot value can be arbitrarily chosen.

A Quicksort is a lot quicker than and Insetion sort and a bubble sort.

3-2-6 Searching

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 the end of the list is reached. 

Advantages:

• Simple to code.
• Works with an unsorted list.

Disadvantages:

• Slow, especially with large lists.

Binary Search:

• 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.
• Repeat from Step 1

Advantages:

• Much Faster than a Linear Search, especially as the list increases in size.
  e.g.

Disadvantages:

• The list needed to be sorted for the binary search to take place.
• It's more complex to code.

3-2-5 Trees

Tree: a connected undirected graph with no cycles.

Rooted Tree: a tree in which one vertex has been designated as the root and every edge is directed away from the root.

3-2-5 Graphs

Graph: a diagram consisting of circles, called vertices, joined by lines, called edges or arcs; each edge joins exactly two vertices.

Neighbours: two vertices are neighbours if they we connected by an edge.

Degree: of a vertex (singular of vertices) , the number of neighbours for that vertex.

E.g. Vertex A and vertex B are neighbours. Vertex A has degree 3 because it has three new ours: B, C, and D.


Labelled (weighted) Graph: a graph in which the edges are labelled or given a value called a weight.

Automation: turning an abstraction into a form that can be processed by computer.

Directed Graph (or digraph): diagram consisting of vertices joined by edges.
(e.g. A round-robin tournament [where every team plays every other team exactly
once])

Simple Graph: an undirected graph without multiple edges and in which each edge connects two different vertices.

Data Representation of a Graph:

An adjacency matrix and an adjacency list are two ways to represent a graph without multiple edges so that the graph can be processed by a computer.

Connectivity
Many applications of graphs involve getting from one vertex to another. For example, it may be required to find the shortest route between one place and another or a route out of a maze. Many problems like these can be modelled with paths formed by travelling along the edges of the graphs. A graph is connected if there is a path between each pair of vertices and is disconnected otherwise.

Path:
Informally, a path is a sequence of edges that begins at a vertex of a graph and travels form vertex to vertex along edges of a graph.

Explorer's Problem: the solution finds a route that traverses each road exactly once before returning to the starting point.
Traveller's Problem: the solution finds a route that visits each city once before retuning to the starting point.

3-2-4 Stacks and queues

Stacks and queues are abstract data types (ADT's). Both are dynamic data structures rather than static data structures. Both can be seen as special cases of lists. They differ n the way elements are added and removed.

Stacks

A stack is also known as a last-in first-out abstract data type. Imagine a pile of plates in a restaurant on a spring-loaded rack: plates are added to and taken away from the top.

Two operations can be carried out in a stack:

• add a new item to the top of the stack (known as pushing).
  
• remove an item from the top of the stack (known as popping).

In computing context, stacks are used to store the return address, parameters and register contents when a procedure or function call is made. When the procedure or function completes execution, the return address and other data are retrieved from the stack.

Stacks are used for compilers, when translating high-level language expressions in assignment statements.

Implementation

When implementing a dynamic structure using the linear list method, the structure becomes static.

Queues

A queue also known as the first-in last-out abstract data type.
In everyday life, we encounter queues in lots of different situations.

Two operations may be carried out in a queue:

• add a new item to the rear of the queue
  
• remove an item from the front of the queue

(Computing examples of queues include print jobs waiting to be printed, characters enter at the keyboard and held in a buffer, jobs waiting to be executed under a batch operating systems, and simulations)

A queue can be implemented in various ways. The simplest method is using an array. However, this makes the queue into a static data structure.

For dynamic implementations, memory locations are assigned form the heap and pointer type variables link the nodes.

Priority queue: each element of a priority queue has an associated priority.

3-2-3 Lists and Pointers

Abstract data types

Programming languages distinguish between different data types such as integer, real and string. High-level languages also provide the programmer with data structures such as records and arrays. Object-orientated programming languages allow the declaration of classes, data structures combined with the methods that act on them.

Real-life problems often refer to other structure. Or containers, to store data items and objects, also called elements. Lists are example of the structures. We write shopping lists and to do lists and we can setup playlists on media players. People use an endless number of lists.

Elements can be added and deleted from a list. Therefore a list can grow and shrink. This is known as a dynamic structure. A list is a collection of elements with an inherent order.

The operations that need to be performed on a list are:

• initialise list (I.e. start a new list)
  
• insert an element
  
• find an element
  
• delete an element
  
• get length of list
  
• output entire list

Linear Lists

A linear list stores its elements in adjacent locations. Elements in an array are stored physically in adjacent locations in main memory. When an array is declared, the computer reserves the space for elements. This means the array is a static structure.

Advantages:

• Easy to program.
  
• if elements are stored in key order, a binary search is possible.

Disadvantages:

• Memory locations may be wasted due to arrays being static.
  
• Insertion of an element within an ordered list requires moving elements.
  
• Deletion of an element with a list requires moving elements.

Linked Lists

Imagine list elements sorted wherever there is a space and linked to form a sequence. Each element of the list, known as a node, can be represented as a record of data fields, with an extra field used as a pointer that links a node to the next mode in the list. A special outer, the start pointer, points to the first node of the list. The last node in the limits has a null pointer in the pointer field.

The concept of makes insertion and deletion of elements much less time consuming. Just the pointer fields are changed. To insert a new node at the beginning of the list, the contents of the start variable is copied into the new node's pointer field, then the start variable is set to lint to the new node.

Linked lists can also be stored in an array. But instead of moving nodes to insert and delete elements, the nodes are connected to the pointers and the pointer values are the index of the array location of the node.

Use of Free Memory, the heap, and pointers

Pointer type: a variable of pointer type stores an address or a data value.
Heap: the memory locations available to application programs for dynamic allocations.
Dynamic allocation: memory space is only allocated when required at run time.
Memory leakage: successive calls to allocate memory space are made, but memory locations that are no longer required are not released. Eventually no memory is left in the heap.

3-2-2 Recursion

What is recursion?

Recursion describes the ability of a routine to call itself. This means a recursive routine is defined in terms of itself.

Recursion is very powerful and often results in a very elegant solution to a problem. However, iterative solutions usually make more efficient use of computer time and memory space.

Recursive routine: a routine defined in terms of itself.

General cause: the solution in terms on itself for a value n.

Base case: a value that has a solution which does not involve any reference to the general case solution.


The mechanism of recursive routines:

Recursion works only if the routine is called with the current value or values passed as parameters. It would not works with global variables.
    Each time a routine is called, a special area of main memory, called the stack, is used. There the return address is stored as well as the contents of registers. Any local variables and the routine's parameters are also allocated space on stacks. The locations in the stack area used to store the values referring to one invocation of a routine is known as a stack frame. When a routine ends, control normally passes to the sotred return address and its stack frame is removed from the stack.

If many recursive calls are made, the stack space could run out. This is known as stack overflow. For example, if the above function Factorial1 were called with a parameter of 0, recursive calls would not terminate normally as the base case of 1 would never be reached. Eventually stack overflow would occur. Because of the stack overheads, recursive algorithms may not be as sufficient as iterative solutions.


STACK FRAME: the locations in the stack area used to store the values referring to one innovation of a routine.