Algorithms – Does Quicksort Provide Fewer Swapping Steps?

algorithmssorting

So far, most of the fastest and common sorting method is quicksort. Although it has its pro and cons. However, i'm thinking that although this sorting method is fast but does it provide shortest swapping step? Because quicksort divide a set of element into 2 and then sorting, will it double up the swapping step?

Best Answer

will it double up the swapping step?

In most cases: The contrary. I'll assume that by swapping you refer to the total number of comparisons. Swapping doesn't really matter in my opinion as it should be a constant time operation and as it is the result of a comparison. The number of comparisons is important.

By dividing the set into two halves you can always think of it as a binary tree. The amount of comparisons to be done is thus logarithmic and dependent on the height of this tree. However, for quicksort, this is not true for all input vectors. When the input is already sorted and the wrong pivot is chosen, then quicksort will run in O(n^2) which is terribly slow. You can think of it as a pretty high tree because quicksort could not properly divide the input vector. Worst case: Not swaps at all and costly at runtime.

Generally you can say, the number of swaps is related to the number of comparisons. The fewer comparisons, the fewer swaps. The number of swaps always depends on the specific input vector!

Related Solutions

Algorithms Naming History Sorting – Why Quicksort is Called Quicksort

In 1962 research on sorting algorithms wasn't as far advanced as today and the computer scientist Tony Hoare found a new algorithm which was quicker than the other so he published a paper called Quicksort and as the paper was quoted the title stayed.

Quoting the abstract:

A description is given of a new method of sorting in the random-access store of a computer. The method compares very favourably with other known methods in speed, in economy of storage, and in ease of programming. Certain refinements of the method, which may be useful in the optimization of inner loops, are described in the second part of the paper.

Algorithms – How to Sort an Array of Numbers with Decimals

Your problem is that your "numbers" don't have decimal places. You have a string which consists of two integers which are separated by .. Parse them as two integers and write a custom comparer. The sorting algorithm can remain the same, you just need to pass in the comparer.

In C# such a comparer could look similar to this:

void Test()
{
    var data=new string[]{ "1.34", "1.15", "1.1", "1.2", "1.26", "1.10", "1.20", "1.17" };
    Array.Sort(data, VersionComparer);
    data.Dump();
}

static int VersionComparer(string s1, string s2)
{
    List<int> parts1 = s1.Split('.').Select(int.Parse).ToList();
    List<int> parts2 = s2.Split('.').Select(int.Parse).ToList();

    while(parts1.Count < parts2.Count)
        parts1.Add(0);
    while(parts2.Count < parts1.Count)
        parts2.Add(0);

    for(int i = 0; i < parts1.Count; i++)
    {
         if(parts1[i] < parts2[i])
             return -1;
         if(parts1[i] > parts2[i])
             return +1;
    }
    return 0;
}

Best Answer

Related Solutions

Algorithms Naming History Sorting – Why Quicksort is Called Quicksort

Algorithms – How to Sort an Array of Numbers with Decimals

Related Topic