This preview shows pages 1–2. Sign up to view the full content.
This preview has intentionally blurred sections. Sign up to view the full version.View Full Document
Unformatted text preview: 3/27/06 - 3/31/06 Class Notes QUICKSORT Popular sorting algorithm that uses "Divide and Conquer" method It can be implemented "in place" so no external memory is needed Algorithm of QuickSort(s) o Input: unsorted array(s) o Output: sorted array(s) Step-by-Step Process o 1) Divide If there is only one element in s, simply return. Otherwise: Choose element x in s, which we will refer to as the pivot Divide s into three parts: L, E, G; L refers to the elements that are less than x, G refers to the elements that are greater than x, and E refers to the elements that are equal to x S / | \ L E G o 2) Recur QuickSort(L); QuickSort(G); o 3) Conquer Put elements back into S from L, E, and G, respectively In Place QuickSort o We use the same array s for storage of L, E, and G at each step o We use the subranges to represent the set o The last element in the subrange is used as the pivot o In order to separate s into L, E, and G, we will have "left" and "right" indexes that point to the front and back of s o 85 24 63 45 17 31 96 50 o L--> <--R x o (find element > 50) (find element < 50> o When found, simply swap them o Continue until L & R meet, then swap x with R and this will contain L, E, and G o 85 24 63 45 17 31 96 50 o L--> <--R...
View Full Document