Sorting with Life

We often come across situations where we start blaming someone for something without being bothered why he failed to please us. And why not because it is quite obvious to point that very finger.
At that moment that person seems obnoxious to us. Later if some one is lucky enough then that point is taken back and pondered. And things gets sorted as an array. I sense a similarity here with Bubble sort. Bigger and good things are sent in the last and there is a focus on small elements. In bubble sort, an array of elements are divided into two segments: unsorted and sorted. The sorted part starts building at the end. We keep arguing every time from the start and drop the bigger(read better) parts at the end.

 

begin BubbleSort(list)
   for all elements of list
      if list[i] > list[i+1]
         swap(list[i], list[i+1])
      end if
   end for
   return list
end BubbleSort

Thus the time complexity of that issue increases heavily. Good thing is, it will be sorted but you will have to pay the price with the time.

Let's take a step back and think if we can apply our favorite quick sort algorithm.

Quicksort(A,p,r) {
    if (p < r) {
       q <- Partition(A,p,r)
       Quicksort(A,p,q)
       Quicksort(A,q+1,r)
    }
}



Partition(A,p,r)
    x <- A[p]
    i <- p-1
    j <- r+1
    while (True) {
        repeat
            j <- j-1
        until (A[j] <= x)
        repeat
            i <- i+1
        until (A[i] >= x)
        if (i A[j]
        else 
            return(j)
    }
}

Now thing is why can't we take this step before rather than making things worse and delayed. Yes its true that sometimes arguments results into better understanding. But there exists a word "Sometimes".

Can a cautionary step taken at that time can avoid these mishaps?
In that short span of time when effervescence of anger fumes at peak is it possible to fit in others shoes and THINK. Well our dear Pivot element can serve the purpose here. Quick sort algorithm smartly selects the pivot element more lesser time it takes to sort. 
Can we intelligently select that pivot and divide the issue?
Well there lies an ambiguity and that's why we have best case, average case and the worst case. 

Let's conclude here with the person who fits in right there perfectly wins the moment and lives it. As the pivot was selected smartly. And this is why quick sort performs better than bubble sort because it initiates good processes from the starting. It doesn't wait long to start.

References

1. Quick sort