I have 2 Questions about some kind of sorts
the first one is:
When implementing quicksort, if the array contains lots of duplicates, it may be better to perform a three-way partition (into elements less than, equal to , and greater than the pivot) to make smaller recursive calls. Assume three-way comparisons.
We need to : give an algorithm that performs a three-way in-place partition of an N-element subarray using only N-1 three-way comparisons, if there are d items equal to the pivot, you may use d additional comparable swaps, above and beyond the two-way partitioning algorithm. (Hint: As i and j move toward each other, maintain five groups of elements as shown below):
Equal small (i) unknown (j) large equal
-------------------------------------------------------------------------------------
the second Question :
We are given an array that contains N numbers. We want to determine if there are two numbers whose sum equals a given number K. For instance, if the input is 8,4,1,6, and K is 10, then the answer is yes (4 and 6). A number may be used twice.
Now we want to give an O(N log N) algorithm to solve this problem. (Hint: sort the items first. after that is done, you can solve the problem in linear time.
Here what I got for this question:
we sort the items; then run i and j from opposite ends of the array toward each other, incrementing i
if a+ a[j ]<K, and decrementing j if a+ a[j ]>K.
The sort is O(N log N)
the scan is O(N).
but i want to change it to code.
could you please help me with these 2 questions