Algorithms For Dummies

  Arranging and Searching Data 

     141

    while True:

        while lIndex <= rIndex and data[lIndex] <= pivot:

            lIndex 

+= 1

        while rIndex >= lIndex and data[rIndex] >= pivot:

            rIndex -= 1

        if rIndex <= lIndex:

            break

        data[lIndex], data[rIndex] = \

            data[rIndex], data[lIndex]

        print(data)

  

    data[left], data[rIndex] = data[rIndex], data[left]

    print(data)

    return rIndex

UNDERSTANDING QUICKSORT WORST-

CASE PERFORMANCE

Quicksort seldom incurs the worst-case sort time. However, even modified versions 

of the Quicksort can have a worst-case sort time of O(n

2

) when one of these events 

occurs:

• 

The dataset is already sorted in the desired order.

• 

The dataset is sorted in reverse order.

• 

All the elements in the dataset are the same.

All these problems occur because of the pivot point that a less intelligent sort function 

uses. Fortunately, using the right programming technique can mitigate these problems 

by defining something other than the leftmost or rightmost index as the pivot point. The 

techniques that modern Quicksort versions rely on include: