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. Insertion 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
3. 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. What are the applications of a stack?

Answer 3

1. A stack is a first-in last-out data structure where items are pushed onto the top of the stack when they are added, and popped off the top when they are deleted.
2. 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.

Question 4

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

Answer 4

1.A queue is a first-in, first-out data structure, where there are two pointers for the front and back. Items are enqueued at the back of the queue and dequeued from the front of the queue.
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 5

2.3.1
1. What is a dynamic data structure?
2. What are the possible advantages of a queue?

Answer 5

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. A queue is first in first out, so the data is retrieved in the order they are stored. Data can be added to the end, and a dynamic structure can expand the size to take in more data.

Question 6

1. What are the operations performed on a stack?
2. What are the operations performed on a queue?

Answer 6

1. Check size: size(), check if empty: isEmpty(); return front element: peek(); add to the queue: push(element); remove front element and return removed element: pop();
2. Check size: size(), check if empty: isEmpty(); return front element: peek(); add to the queue: enqueue(element); remove front element and return removed element: dequeue();

Question 7

1. How do you push and pop elements from a stack?
2. How do you enqueue and dequeue from a queue?

Answer 7

1. To push: Increment the top pointer, and stack[top] = newElement.
   To pop: if top = 0, return empty error, else decrease the top pointer by one and return the removed item.
2. To enqueue, first check if the queue is full, if it is not, then add a new element to the tail position and increase the tail pointer.
   To dequeue, if head == tail + 1, then return empty array error, else increment the head by 1.