Lab

Merge sort O(n log n)

  1. If the list is of length 0 or 1, then it is sorted. Otherwise:
  2. Divide the unsorted list into two sublists of about half the size.
  3. Sort each sublist recursively by re-applying merge sort.
  4. Merge the two sublists back into one sorted list.

  1. Trace the mergesort algorithm as it sorts the following array into ascending order. List the calls to mergesort and to merge in the order in which they occur.20 80 40 25 60 30

Quicksort O(nlogn)

Algorithm

Quicksort sorts by employing a divide and conquer strategy to divide a list into two sub-lists.

The steps are:

  1. Pick an element, called a pivot, from the list.
  2. Reorder the list so that all elements which are less than the pivot come before the pivot and so that all elements greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
  3. Recursively sort the sub-list of lesser elements and the sub-list of greater elements.

The base case of the recursion are lists of size zero or one, which are always sorted.

The boxed element is the pivot element, blue elements are less or equal, and red elements are larger.

  1. Trace the quick sort algorithm as it sorts the following array into ascending order. List the calls to quicksort and to partition in the order in which they occur. 20 80 40 25 60 10 15

Heap

The root must be greater than each of its children.

Let's start with this heap.
A deletion will remove the T
at the root. /
To work out how we're going to maintain the heap property, use the fact that a complete tree is filled from the left. So that the position which must become empty is the one occupied by the M.
Put it in the vacant root position. /
This has violated the condition that the root must be greater than each of its children.
So interchange the M with the larger of its children. /
The left subtree has now lost the heap property.
So again interchange the M with the larger of its children. /

This tree is now a heap again, so we're finished.

We need to make at most h interchanges of a root of a subtree with one of its children to fully restore the heap property. Thus deletion from a heap is O(h) or O(logn).

Addition to a heap

To add an item to a heap, we follow the reverse procedure.
Place it in the next leaf position and move it up.
Again, we require O(h) or O(logn) exchanges. /

Storage of complete trees

The properties of a complete tree lead to a very efficient storage mechanism using n sequential locations in an array.

/ If we number the nodes from 1 at the root and place:
  • the left child of node k at position 2k
  • the right child of node k at position 2k+1
Then the 'fill from the left' nature of the complete tree ensures that the heap can be stored in consecutive locations in an array.
Viewed as an array, we can see that the nth node is always in index position n. /
  1. Consider the heap below. Draw the heap after you insert 12 and remove 12.

10

96

32

5

10 9 6 3 2 5

After inserting 12:

12

910

3256

After removing 12:

10

96

325

  1. Execute the pseudocode statements

For (index =n-1 down to 0 )

Heaprebuild (anArray, index, n)

On the array :

{5 1 2 8 6 10 3 9 4 7}

The array is: 10 9 5 8 7 2 3 1 4 6

2-3 tree

A 2-3 tree in computer science is a type of data structure, a B-tree where every node with children (internal node) has either two children and one data element (2-nodes) or three children and two data elements (3-nodes). Nodes on the outside of the tree (leaf nodes) have no children and two data elements.

a 2-node

a 3-node

  • Every non-leaf node has 2 or 3 children
  • All leaves are at the same level (the bottom level)
  • All data is kept in sorted order
  • Every non-leaf node will contain 1 or 2 fields.
  1. What is the result of inserting 5 40 10 20 15 30 in the order given into an initially empty 2-3 tree?

10 20

51530 40

  1. What is the result of deleting the 10 from the 2-3 tree that you just created?

15 30

5 2040

  1. What is the result of inserting 3 and 4to the 2-3 tree that you just created?

10

420

351530 40

  1. Given the following 2-3 tree draw the tree that results after inserting k,b,c,y, w into the tree.

r

ehu

dfopstv

  1. Given the following 2-3 tree:

o

h mqt

deknprv

draw the tree that results after removing t,e, k and d from the tree.

  1. Draw the 2-3-4 tree that results from inserting o,d,j,h,s,g,a in the order given into a 2-3-4 tree and contains a single node whose value is n.