1 Randomized Quick Sorting Backwards Analysis

• Main Author: Yan Liu
• Other Authors: The Pennsylvania State University CiteSeerX Archives
• Format: Text
• Language: English
• Subjects: The Pointers
• Online Access: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.129.2183; http://www.csee.wvu.edu/~ksmani/courses/fa01/random/lecnotes/lecture12.pdf

Consider the following scheme to solve the sorting problem: given n numbers to be sorted, after the ith of n (1 ≤ i ≤ n), we will make sure that we have i of input numbers in a sorted list. Clearly these i sorted numbers will partition the ranks of the remaining n − i unsorted numbers into i + 1 intervals. The (i + 1)th step consists of choosing one of the n − i unsorted numbers uniformly at random, and inserting it into the sorted list. After n such insertion steps, we are left with a list of all the input numbers, in sorted order. This algorithm can be viewed as a variant of quicksort algorithm [2]. To perform the insertion step, throughout the algorithm we maintain a pointer for each number yet to be inserted into the sorted list.After the ith step, the pointer for each uninserted number specifies which of the i + 1 intervals in the sorted list it would be inserted into, if it were the next to be inserted. The pointers are bidirectional, so that given an interval we can determine the numbers whose pointers point to it. Suppose we insert a number x whose pointers point to interval I, thus the work required to update the pointers is proportional to the number of pointers point to I. Consider the work done in the ith step when the objects in the input are considered in a random order. While we could directly analyze this random variable, we introduce a useful tool: backwards analysis. By using backwards analysis, we imagine that the algorithm is running backwards starting from the sorted list we have at