Correction for HW2 Solutions

[Haidong (Haydon) Xue]

Hi all,

Dan Jiang found out that my quicksort solution of HW2 is not very correct, and the problem is the partition procedure. The corrected solution is posted as  http://www.cs.gsu.edu/~hxue1/csc4520/Assignments/Assignment2_solutions_adjusted.pdf . I will talk about it more on Monday. 

It is a good practice for you, so to encourage you to do it more and think deeper, I make a rule here:

if you can prove one of my solutions is incorrect, 2 bonus credits will be added to your final grade.

--
Haidong(Haydon) Xue
Ph.D Candidate
Research Assistant, Teaching Instructor
Department of Computer Science
Georgia State University

http://www.cs.gsu.edu/~hxue1

[Chaoyang Li]

Hi professor Xue,
I think your solution is correct because the result is the same as the so-called standard partition solution.
Actually the pivot element can be chosen randomly which provides us greater freedom than standard solution.
There are many ways to select the pivot.Why should we select the standard partition? what is the benefit from it? Why is it more correct?
Thanks
Best regards
Chaoyang  Li

---

发件人: gsu-csc4520...@googlegroups.com [gsu-csc4520...@googlegroups.com] 代表 Haidong (Haydon) Xue [haido...@gmail.com]
发送时间: 2012年6月17日 16:33
收件人: gsu-csc4520...@googlegroups.com
主题: Correction for HW2 Solutions

[Haidong (Haydon) Xue]

Hi, 

How to choose the pivot generally does not affect the quicksort efficiency, but how to put the pivot into the middle position does. The method in textbook just swap the pivot to the middle position, requiring O(1) time; the method in HW2 solutions (the first version) may need O(n) time.

I will talk more about it on Monday. 

Haydon

--
You received this message because you are subscribed to the Google Groups "GSU CSc4520/6520 Summer 2012" group.
To unsubscribe from this group, send email to gsu-csc4520-summe...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.