CSC 250 Notes Set 9

CSC 250 Notes
Set 9-2

Topics

uses divide-and-conquer approach
- partition the list into 2 sublists
- sort the sublists
- combine the sorted sublists into 1 list
O(n*log n) average case
partitioning is the key operation in the QuickSort algorithm

pivot : element chosen from the list
- lowerSubList : elements with values lower than pivot
- upperSubList : elements with values greater than pivot
choosing the pivot
- Goal: lower & upper lists will be about the same size
- no exact solution
- pick the "middle" element - our strategy
arrange the list elements into 2 groups
- For pivot K,
- ... Smaller than K... K ...Larger than K...
- Note: both sublists are smaller than the original
algorithm ( Partition ) must be able to do this for all situations
- List L[ S .. E ]
- Choose Pivot, value K at location p ; swap Pivot with first element of List, L[S]
  - Swap(p, S)
- Divide the list into 2 sublists relative to the value of the pivot; in the end, the pivot will be the separator between the lists
  - let SI be the last element in the lower sublist, initially 0
  - for each position i in the list, starting at S+1 (since S is the Pivot)
    - Compare L[i] top K; if (L[i] < K)
      - SI++
      - Swap(i,SI) ; swap the current element into the lower-list
  - Swap the Pivot with the element at SI
    - Swap(S, SI)
- Return the location of the Pivot in the list
Now just turn those steps into code!

void QuickSort( int S, int E)
  int ploc
  if (S < E)
    ploc = Partition(S, E)
    QuickSort(S, ploc-1)
    QuickSort(ploc+1, E)

I find that recursive solutions, such as this, are very clear, yet very confusing :)

0	1	2	3	4	5	6	7	8
45	82	25	94	50	60	78	32	92

QuickSort(0, 8)

ploc = Partition(S, E)

0	1	2	3	4	5	6	7	8
50	82	25	94	45	60	78	32	92

0	1	2	3	4	5	6	7	8
50	25	82	94	45	60	78	32	92

0	1	2	3	4	5	6	7	8
50	25	45	94	82	60	78	32	92

0	1	2	3	4	5	6	7	8
50	25	45	32	82	60	78	94	92

0	1	2	3	4	5	6	7	8
32	25	45	50	82	60	78	94	92