2.3

Question 1

2.3.1
1. What is an insertion sort?
2. What is the plain English explanation for the insertion sort algorithm?
3. What is the pseudocode algorithm for the insertion sort?

Answer 1

1. Inversion sort sorts the array by shifting elements one by one. After each iteration, the size of the sorted data at the beginning of the list grows by one. The algorithm shifts values along, it does not swap values.
2. Repeat the following for each item in the list, excluding the first:
   Remember the current item as the key
   Move every item before the key that is bigger than it forward
   Place the key item before these larger items
   What is the pseudocode algorithm for the insertion sort?
   for I = 1 to A.length - 1:
   key = A[i]
   j = i - 1
   while j >= 0 and A[j] > key:
   A[j + 1] = A[j]
   j - -
   endWhile
   A[j + 1] = key
   next i

Question 2

2.3.1
1. What are the advantages of insertion sort?
2. What are the disadvantages of insertion sort?
3. What are the best and worst case scenarios for insertion sort?

Answer 2

1. An advantage is it is easy to implement, and it is good for small data sets that are almost sorted. Another advantage is the insertion sort generally performs quicker than bubble sort and is therefore preferable.
2. A disadvantage does not scale well so it is not good for large data sets.
3. The best case scenario is the data is already sorted.
   The worst case scenario for ascending sort is when the values are in descending order.

Question 3

2.3.1
1. What is a stack?
2. How does a stack work?

Answer 3

1. A stack is a data structure that is essential for the operation of a computer. Items are pushed onto the top of the stack when they are added to it and popped off the top when they are deleted from it. It is also possible to peak at eh top item without deleting it.
2. A stack is known as a last-in first-out of LIFO structure — the last item to be pushed onto the stack must also be the first item to be popped off. A stack has a stack pointer that always points to the node at the top. Any attempt to put an item onto a full stack is called a stack overflow. Similarly, any attempt to pop an item off an empty stack is called a stack underflow.

Question 4

2.3.1
1. What are the applications of a stack?
2. What is a queue?

Answer 4

1. Stacks are used by processors to track the flow of programs. When a procedure or function (subroutine) is called, it changes the value of the program of the subroutine. When the subroutine ends, the processor must return the program counter to its previous value — we can archive this using a stack, which allows subroutine calls to be nested.
2. A queue is a linear data structure. Items are enqueued at the back of the queue and dequeued from the front of the queue. It is also possible to peek at the front item without deleting it. Imagine a supermarket checkout — the customer at the front of the queue is served first, and new customers join at the back. By nature, a queue system also allows people to jump the queue — called a priority queue. In special circumstances, new items can join at the front of the queue.

Question 5

2.3.1
1. How is a queue implemented?
2. What are the applications of a queue?
3. What is a data structure?

Answer 5

1. Queues can be implemented using an array or object-orientated technique.
2. Queues are used for: process scheduling; transferring data between processors and printer spooling; Performing breadth-first searches on graph data structures.
3. A data structure is a particular way of organising related data.

Question 6

2.3.1
1. What is a dynamic data structure?
2. What operations can be performed on a queue?

Answer 6

1. A dynamic data structure uses an area of memory called the heap. Size can change during processing, so as the size can change it is possible for the structure to ‘overflow’ if it exceeds the maximum allowed memory.
2. Enqueue: adding an item to the back of the queue.
   Dequeue: removing an item from the front of the queue.
   Peek: returning the value from the front of the queue without removing it.