Difference between revisions of "User:Sorting-searching-TADM2O"

Revision as of 00:18, 20 July 2020

We will apply Quick Sort algorithm for this problem. The algorithm would be changed a bit for this specific problem by adding one step of comparing the distance between the number and the pivot whenever the number is compared for partitioning. This will be explained in the detail below.

First step: Pick a pivot! (recommendation median-of-three)

Second step: We will compare all other numbers with pivot for partitioning. After comparing, we will calculate the distance between the number and the pivot and keep the smallest distance. Then, partitioning the list into 2 parts as the normal quicksort.

Third step: Recursive call for each side after partitioning.

Note: After partitioning, the number in left side, for example, does not need to compare with the one in the right side of the pivot because the distance would definitely be larger than the distance between that number and the pivot. So the problem will be reduced by half (average case).

Anther solution is we can sort the list by a fast algorithm such as merge sort which will take O(nlogn) then find the smallest distance by iterate through the sorted list which will take O(n) (this is question d)