Improving bubble sort

Most people believe that using Quick Sort or Merge Sort, would achieve the best sorting performance over a standard array. Even though this might be true in most (or at least some) cases, there are real world situations where a better solution can be applied.

Let's assume there's a big chance we are trying to sort an already sorted array, or almost-sorted array. What is an almost-sorted array? This is an array which is sorted beginning from some element which is not far from the first element.

Now, let's try to recall what bubble sort looks like:
for i = 1 to length(A)
  for j = length(A) downto i+1
   if A[j] < A[j-1] then
    swap A[j] with A[j-1]

This is a very simple implementation, but would cost O(n^2) even when we deal with an already sorted array. How could this be improved? Let's add a flag:
for i = 1 to length(A)
  swapped = false
  for j = length(A) downto i+1
   if A[j] < A[j-1] then
    swap A[j] with A[j-1]
    swapped = true
  if swapped = false then
   break

As you can probably see, once there's a full iteration in which no elements were swapped, the algorithm finishes. For an already sorted array, performance are now O(n). For an almost-sorted array (beginning item c), performance are O(cn). Not bad...