Single-dimensional array and simple looping activities of significance
The Dutch National Flag problem is linear in running time. Essentially sort an array with only 3 distinct values each of which may appear 0 or more times. (not length 3). You are allowed only one pass over the array, so the solution is a single while loop with some prior initialization. 

It was probably originally posed by Dijkstra. It is mentioned in David Grits's The Science of Programming where it can be solved very nicely by posing pre and post conditions using David's ideas of finding invariants from pre and post conditions. 

You can also make it a simple object oriented problem if you like by using objects as the array elements, for example. 

A more interesting formulation of the problem refers to the Dutch National Flag which is a Tricolor: Red over White over Blue. You have an array that has some jumbled up red and white and blue cells, zero or more of each. You want to move all of the red cells to the left end, all of the blue cells to the right end, with the white cells in the middle. The restriction is that you may make only a single pass over the array. The correct solution is very creative and demonstrates the power of loop invariants. 

I have mentioned this problem in answers to other questions here. A search for "dutch" on the questions page will reveal them. 

Solving it without hints can provide a gigantic a-ha moment for almost everyone. 

If students can do the classic version, they can also think about a modification that will handle 4 values instead. From that you can talk about the inherent complexity of sorting values from any finite set.