Warm-up: Interview Question

Taken from Quora Question.

C Interview: Write a C program to count the number of bits set in an unsigned integer. (000 -> 0, 110 -> 2, 1101001 ->4)

Class 10: Insertion Sort

It is possible, maybe even likely, that you've seen sorting algorithms before. Hopefully you read about them in the book. I can guarantee that you'll see them again. They are the quintessential introduction to complexity theory. Thinking them out and choosing between them captures so many good dimensions of tackling problems: scaling issues, best-case/worst-case/average-case, pros and cons of approaches, and the impact of data structures on your algorithm.

So, unapologetically, here is insertion sort in several different forms:

      
       for (i = 1; i < n; ++i){
           j = i;
           while ((j > 0) && (s[j] < s[j-1]) ){
             swap(s[j], s[j-1]);
             --j;
           }
       }
      
    

Some profs dislike using any particular language for these courses. The reason is that the idea is language independent, and seeing it in many forms gets you thinking about it abstractly. But you rarely put abstract thinking on your resume, it's subversive like that.

New C++ feature: Swap

So in all of the versions of "insertion sort" that we saw things are switching places. C++ has a very cool method for that called swap.

Description Task 1: Describe how swap works in your own words.

Be C++ Task 2: Write your own templated swap function.

Array-Based Insert Sort

Here is a version I hacked up in C++:

Hand's On Complexity 3: Alter this to have the array have length 50 and be populated by random integers from 1 to 100. How many swaps does it take on average? Change it to length 100 and answer (you might want to kill some couts).

So the worst-case running time is certainly \( \mathcal{O}(n^2) \), (count the worst-case size of the loops and number of swaps in that case).

Average Case 4: Based on your observations, do you think that the average case performance is \(\mathcal{O}(n^2)\)?

Best Case 5: What is the best type of input? What is the cost of this algorithm in that case?

Creative Research Task 6: Can you improve this algorithm using the speed of binary search? Where might you try? What happens?

Insertion Sort on a Linked List

Thought Experiment 6: How would insertion sort perform on a singly-linked list?

Thought Experiment 7: Which performance is altered if we switch to a doubly-linked list (Best-Case, Worst-Case, Average-Case)?

Here is a version of Insertion sort on a doubly-linked list:

Adjust Task 8: Have this code count the number of swaps. Then populate it with 50 random integers and figure out the average number of swaps. Now with 100 random integers. Do you think the number of swaps is different than in the array case?

Refactor Task 9: Now, how can you cut back on the number of swaps using the intrinsic structure of linked lists? Does this improve worst-case performance? Why or why not?

Timing Task 10: Take the adjustments you've made and make them adjustable, so that we can time the code using time ./executable_here at various sizes. Check that the growth is quadratic. Create a sorted case and time that, confirm your estimates for growth.