Algorithms For Dummies

 Understanding the Need to Sort and Search

Right side:  [2, 4, 7]

Merged  [2, 4, 5, 7, 9]

Left side:  [8]

Right side:  [1]

Merged  [1, 8]

Left side:  [6]

Right side:  [3]

Merged  [3, 6]

Left side:  [10]

Right side:  [3, 6]

Merged  [3, 6, 10]

Left side:  [1, 8]

Right side:  [3, 6, 10]

Merged  [1, 3, 6, 8, 10]

Left side:  [2, 4, 5, 7, 9]

Right side:  [1, 3, 6, 8, 10]

Merged  [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Solving sorting issues the best  

way using Quicksort

The Quicksort is one of the fastest methods of sorting data. In reading about 

Mergesort  and  Quicksort  online,  you  find  that  some  people  prefer  to  use  one 

over the other in a given situation. For example, most people feel that a Quick-

sort works best for sorting arrays, and Mergesort works best for sorting linked 

lists (see the discussion at 

http://www.geeksforgeeks.org/why-quick-sort- 

preferred-for-arrays-and-merge-sort-for-linked-lists/

). Tony Hoare 

wrote the first version of Quicksort in 1959, but since that time, developers have 

written many other versions of Quicksort. The average sort time of a Quicksort 

is O(n log n), but the worst-case sort time is O(n

2

).

The first part of the task is to partition the data. The code chooses a pivot point 

that determines the left and right side of the sort. Here is the partitioning code for 

this example:

data = [9, 5, 7, 4, 2, 8, 1, 10, 6, 3]

  

def partition(data, left, right):

    pivot = data[left]

    lIndex = left 

+ 1

    rIndex = right

  

---

CHAPTER 7