Section5: Pointers, Heaps, and Sorting

Section materials curated by our Head TA Nick Bowman, drawing upon materials from previous quarters.

This week’s section exercise delve deep into the details of pointers and memory management in C++. This is an opportunity to get down and dirty in the nitty gritty of things, and to get closer towards gaining ultimate power over your computer! The topics covered in section this week will show up on the next assignment,

Remember that every week we will also be releasing a Qt Creator project containing starter code and testing infrastructure for that week's section problems. When a problem name is followed by the name of a .cpp file, that means you can practice writing the code for that problem in the named file of the Qt Creator project. Here is the zip of the section starter code:

📦 Starter code

1) A Series of Unfortunate References

Topics: Pointers and references

What is the output of the following code snippet?

void VFD(int *duncan, int isadora, int& quigley) {
	isadora += *duncan;
	quigley *= isadora;
	(*duncan) = 1;
	isadora = *duncan;
}

int main() {
	int sunny = -6;
	int klaus = 21;
	int violet = 2;
	VFD(&sunny, violet, klaus);
 	cout << sunny << " " << klaus << " " << violet << " " << endl; 
 	return 0;
}

2) Pointed Points about Pointers

Topics: Arrays and pointers

Pointers to arrays are different in many ways from ADTs in how they interact with pass by-value and the = operator. To better understand how they work, trace through the following program. What is its output?

void print(int* first, int* second) {
	for (int i = 0; i < 5; i++) {
		cout << i << ": " << first[i] << ", " << second[i] << endl;
	}
}
void transmogrify(int* first, int* second) {
	for (int i = 0; i < 5; i++) {
		first[i] = 137;
	}
}
void mutate(int* first, int* second) {
	first = second;
	second[0] = first[0];
}
void change(int* first, int* second) {
	first = new int[5];
	second = new int[5];
	for (int i = 0; i < 5; i++) {
		first[i] = second[i] = 271;
	}
}
int main() {
	int* one = new int[5];
	int* two = new int[5];

	for (int i = 0; i < 5; i++) {
		one[i] = i;
		two[i] = 10 * i;
	}

	transmogrify(one, two);
	print(one, two);
	
	mutate(one, two);
	print(one, two);
	
	change(one, two);
	print(one, two);
	
	delete[] one;
	delete[] two;
	return 0;
}

0: 137, 0
1: 137, 10
2: 137, 20
3: 137, 30
4: 137, 40
0: 137, 0
1: 137, 10
2: 137, 20
3: 137, 30
4: 137, 40
0: 137, 0
1: 137, 10
2: 137, 20
3: 137, 30
4: 137, 40 

3) The Hogwarts School of Pointers and Memory

Topics: Pointer tracing and memory diagrams

Trace through the following function and draw the program’s memory at the designated spot. Indicate which variables are on the stack and which are on the heap, and indicate orphaned memory. Indicate with a question mark (?) memory that we don’t know the values of.

struct Quidditch {
	int quaffle;
	int *snitch;
	int bludger[2];
};

struct Hogwarts {
	int wizard;
	Quidditch harry;
	Quidditch *potter;
};

Quidditch * hufflepuff(Hogwarts * cedric) {
	Quidditch *seeker = &(cedric->harry);
	seeker->snitch = new int;
	*(seeker->snitch) = 2;
	cedric = new Hogwarts;
	cedric->harry.quaffle = 6;
	cedric->potter = seeker;
	cedric->potter->quaffle = 8;
	cedric->potter->snitch =
	&(cedric->potter->bludger[1]);
	seeker->bludger[0] = 4;
	return seeker;
}

void gryffindor() {
	Hogwarts *triwizard = new Hogwarts[3];
	triwizard[1].wizard = 3;
	triwizard[1].potter = NULL;
	triwizard[0] = triwizard[1];
	triwizard[2].potter =
	hufflepuff(triwizard);
	triwizard[2].potter->quaffle = 4;
	// DRAW THE MEMORY AS IT LOOKS HERE
}

4) The Notorious RBQ, Revisited (RingBufferQueue.h/.cpp)

Topics: Classes, dynamic memory allocation, pointers

Remember our good friend the RingBufferQueue from last section? Check out the problem definition from last week if you want a quick refresher. Last time we visited the RBQ it had fixed capacity – that is, it couldn't grow in size after it was initially created. How limiting! With our newfound pointer and dynamic allocation skills, we can remove this limitation on the RBQ and make it fully functional!

Add functionality to the class RingBufferQueue from the previous section problem so that the queue resizes to an array twice as large when it runs out of space. In other words, if asked to enqueue when the queue is full, it will enlarge the array to give it enough capacity.

For example, say our queue can hold 5 elements and we enqueue the five values 10, 20, 30, 40, and 50. Our queue would look like this:

index    0    1    2    3    4
      +----+----+----+----+----+
value | 10 | 20 | 30 | 40 | 50 |
      +----+----+----+----+----+
         ^                   ^
         |                   |
       head                tail

If the client tries to enqueue a sixth element of 60, your improved queue class should grow to an array twice as large:

index    0    1    2    3    4    5    6    7    8    9
      +----+----+----+----+----+----+----+----+----+----+
value | 10 | 20 | 30 | 40 | 50 | 60 |    |    |    |    |
      +----+----+----+----+----+----+----+----+----+----+
         ^                        ^
         |                        |
       head                     tail

The preceding is the simpler case to handle. But what about if the queue has wrapped around via a series of enqueues and dequeues? For example, if the queue stores the following five elements:

index    0    1    2    3    4
      +----+----+----+----+----+
value | 40 | 50 | 10 | 20 | 30 |
      +----+----+----+----+----+
              ^    ^
              |    |
            tail head

If the client tries to add a sixth element of 60, you cannot simply copy the array as it is shown. If you do so, the head and wrapping will be broken. Instead, copy into the new array so that index 0 always becomes the new head of the queue. The picture will look the same as the previous one with the value 60 at index 5.

Write up the implementation of the new and improved RingBufferQueue. It should have the same members as in the previous problem, but with the new resizing behavior added. You may add new member functions to your class, but you should make them private.

#pragma once

#include <iostream>
using namespace std;
class RingBufferQueue {
public:
    RingBufferQueue();
    ~RingBufferQueue();
    bool isEmpty() const;
    bool isFull() const;
    int size() const;
    void enqueue(int elem);
    int dequeue();
    int peek() const;
private:
    int* _elements;
    int _capacity;
    int _size;
    int _head;
    friend ostream& operator <<(ostream& out, const RingBufferQueue& queue);
    void enlarge();
};

#include "RingBufferQueue.h"

static int kDefaultCapacity = 5;
RingBufferQueue::RingBufferQueue() {
    _capacity = kDefaultCapacity;
    _elements = new int[_capacity];
    _head = 0;
    _size = 0;
}
RingBufferQueue::~RingBufferQueue() {
    delete[] _elements;
}
void RingBufferQueue::enqueue(int elem) {
    if (isFull()) {
        enlarge();
    }
    int tail = (_head + _size) % _capacity;
    _elements[tail] = elem;
    _size++;
}
int RingBufferQueue::dequeue() {
    int front = peek();
    _head = (_head + 1) % _capacity;
    _size--;
    return front;
}
int RingBufferQueue::peek() const {
    if (isEmpty()) {
        throw "Can't peek at an empty queue!";
    }
    return _elements[_head];
}
bool RingBufferQueue::isEmpty() const {
    return _size == 0;
}
bool RingBufferQueue::isFull() const {
    return _size == _capacity;
}
int RingBufferQueue::size() const {
    return _size;
}
void RingBufferQueue::enlarge() {
    int *larger = new int[_capacity * 2];
    for (int i = 0; i < _size; i++) {
        larger[i] = _elements[(_head + i) % _capacity];
    }
    delete[] _elements;
    _elements = larger;
    _capacity *= 2;
    _head = 0;
}
ostream& operator <<(ostream& out, const RingBufferQueue& queue) {
    out << "{";
    if (!queue.isEmpty()) {
        // We can access the inner ‘_elements’ member variables because
        // this operator is declared as a friend of the RingBufferQueue class
        out << queue._elements[queue._head];
        for (int i = 1; i < queue.size(); i++) {
            int index = (queue._head + i) % queue._capacity;
            out << ", " << queue._elements[index];
        }
    }
    out << "}";
    return out;
}

5) Min Heap

Topics: Heaps

We have implemented the Priority Queue ADT using a binary min-heap. Draw a diagram of the heap’s tree structure that results from inserting the following priority values in the order given: 25, 37, 28, 12, 30, 3

6) Max Heap

Topics: Heaps

You have a PriorityQueue class which treats higher (larger integer value) priority elements as frontmost. The internal implementation of the class is a binary max-heap stored in an unfilled array. The initial allocation of the array is for capacity 5 and the array capacity is doubled when asked to enqueue to a queue which is full. You are going to trace the operation of enqueuing and dequeuing elements from the priority queue. You can sketch as a tree if you prefer when working it out, but your final answer should be based on an unfilled array that skips use of index 0.

(a) Show the contents of the internal array after these elements are enqueued to an empty priority queue in this order. Each element has a string value and a priority in parenthesis.

Red(8), Blue(33), Green(29), Purple(42), Orange(20), Yellow(22), Indigo(10), Teal(21)

(b) Dequeue is called twice on the priority queue. Which two values are removed?

(c) Show the contents of the internal array after the above two elements have been dequeued

    

        
elements:
        
?
        
P(42)
        
B(33)
        
G(29)
        
T(21)
        
O(20)
        
Y(22)
        
I(10)
        
R(8)
        
?
    
    

        
index:
        
 0 
        
 1 
        
 2 
        
 3 
        
 4 
        
 5 
        
 6 
        
 7 
        
 8 
        
 9 
    

    

        
elements:
        
?
        
G(29)
        
T(21)
        
Y(22)
        
R(8)
        
O(20)
        
I(10)
        
?
        
?
        
?
    
    

        
index:
        
 0 
        
 1 
        
 2 
        
 3 
        
 4 
        
 5 
        
 6 
        
 7 
        
 8 
        
 9 
    

7) Insertion Sort [Covered on Friday]

Topics: Sorting

Suppose you are sorting the following vector using insertion sort: {29, 17, 3, 94, 46, 8, -4, 12}

Walk through the insertion sort algorithm and show the state of the vector after each of the first three passes of the outermost loop (that is, the loop where you find the minimum element).

8) Merge Sort [Covered on Friday]

Topics: Sorting

Suppose you are sorting the following vector using merge sort: {29, 17, 3, 94, 46, 8, -4, 12}

Walk through the merge sort algorithm and show the sub-vectors that are created by the algorithm and show the merging of the sub-vectors into larger sorted vectors. As a hint, this vector should have three split steps, and three merge steps.

9) It Was The Best of Cases, It Was The Worst of Cases [Covered on Friday]

Topics: Sorting, Big-O, Best and Worst Case Analysis

Recall that we said in lecture that quicksort performs in O(n log n) in the best case but O(n^2) in the worst case.

Let's explore why that might be. Here's an example of a vector that quicksort will sort in O(n log n) (assuming you pick the first element in the vector as the pivot): {4, 1, 3, 5, 6, 7, 2}

And here's an example of a vector with the same values that quicksort will sort in O(n^2) (again, assuming you pick the first element in the vector as the pivot): {1, 2, 3, 4, 5, 6, 7}

Using these vectors, figure out what causes the differences in quicksort's performance, and then construct your own vectors for each case using different values. Hint: look at the patterns in the pivots that are chosen by the algorithm.