CS50x Week 4

Topics in this week’s lectures and shorts:

  • Merge sort.
  • Pointers.
  • When is pointer used?
  • Array are pointers.
  • String is an array of characters.

Merge sort

Merge sort is a sorting algorithm that uses recursion. Recursion function as explained in 6.00.1x Week 3, is a function that calls a smaller version of itself. The pseudocode and Powerpoint explanation (click on the slide instead of pressing the arrow for power point animation, or use keyboard) for merge sort is as follows:

Efficiency of merge sort

We were introduced to the concept of Big O in the previous week, what is the Big O of merge sort?

T(n) = 0, \mbox{if } n\textless2
T(n) = T(\frac{n}{2}) + T(\frac{n}{2}) + n, \mbox{if } n\textgreater1

where T(n) is the time required to merge sort array with n elements, T(\frac{n}{2}) is time required to sort left half, T(\frac{n}{2}) is time required to sort right half, and n is time required for merging.

For example, to sort an array with 16 elements:

T(16) = 2.T(8) + 16
T(8) = 2.T(4) + 8
T(4) = 2.T(2) + 4
T(2) = 2.T(1) + 2
T(1) = 0
so, T(16) = 64 = 16log{16}

The Big O is nlog{n} .

Another way to look at it is, for each level (refer to slide 2 of Powerpoint, divide the process into columns), it requires n time to merge , and there are log{n} levels, so the time required is nlog{n} .

Hear the sorting process

We are done with different sorting algorithms, enjoy the video below:

Pointers

If there is a need for e.g. when you call a function that accepts variables, a copy of the variables will be passed to the function, so when you change variables in function, and you don’t return it, the variable will not be changed in real. If you want to really change something, and not just its copy, you have to use pointers.

Pointers let you deal with addresses of another variable.

Pointer is a variable of size one int, it stores an address of another variable.

Demo of how to use pointer

When is pointer used? E.g.

Swap fails because the function swap modifies the copy of variables a, and b, and not the real values themselves.

Swap succeeds, because the function swap modifies the real value of a and b by accepting addresses of a and b and changing their dereferenced value.

Arrays are pointers

array[0] is the same as *array, array has the address of 0th element, so dereferencing address will get array[0].
array[1] is the same as *(array + 1), (array + 1) is the address of element next to 0th element, dereference it will get the 1st element.

String is an array of characters, ending with

Pointers point to first address of character. How does the pointer knows when does the string ends? when the n is met. Warning: you need to allocate one extra space for .

Other posts in the series: Harvard CS50x 2014

Leave a Reply