COMPSCI 61B Lecture Notes - Lecture 34: Royal Institute Of Technology, Insertion Sort, Deterministic Algorithm
1 Jun 2017
School
Department
Course
Professor
Document Summary
Goal is to be intense, but not too terribly long. Will survey you on the nal survey on how it went. Last year"s students thought it was slightly too hard, but the version this time should be good. Rastering is the toughest part (3 extra credit points if completed by sunday) Di culty was as expected, median was 66% (we expected 63%) Exams at berkeley will often push your limits. Final exam can shadow your midterm 2 score. Create l and g pointers at left and right ends. L pointer is a friend to small items, and hates large or equal items. G pointer is a friend to large items, and hates small or equal items. Walk pointers towards each other, stopping on a hated item. When both pointers have stopped, swap and move pointers by one. Overall runtime still depends crucially on pivot selection strategy!
