How does bubble sort compare to selection sort?

Which sorting tech开发者_Go百科nique is faster: bubble or selection sort, and why? Are both equally efficient?

Wikipedia says (emphasis added):

Among simple average-case Θ(n²) algorithms, selection sort almost always outperforms bubble sort and gnome sort, but is generally outperformed by insertion sort. Insertion sort is very similar in that after the kth iteration, the first k elements in the array are in sorted order. Insertion sort's advantage is that it only scans as many elements as it needs in order to place the k + 1st element, while selection sort must scan all remaining elements to find the k + 1st element.

Simple calculation shows that insertion sort will therefore usually perform about half as many comparisons as selection sort, although it can perform just as many or far fewer depending on the order the array was in prior to sorting. It can be seen as an advantage for some real-time applications that selection sort will perform identically regardless of the order of the array, while insertion sort's running time can vary considerably. However, this is more often an advantage for insertion sort in that it runs much more efficiently if the array is already sorted or "close to sorted."

While selection sort is preferable to insertion sort in terms of number of writes (Θ(n) swaps versus Ο(n²) swaps), it almost always far exceeds (and never beats) the number of writes that cycle sort makes, as cycle sort is theoretically optimal in the number of writes. This can be important if writes are significantly more expensive than reads, such as with EEPROM or Flash memory, where every write lessens the lifespan of the memory.

Finally, selection sort is greatly outperformed on larger arrays by Θ(n log n) divide-and-conquer algorithms such as mergesort. However, insertion sort or selection sort are both typically faster for small arrays (i.e. fewer than 10-20 elements). A useful optimization in practice for the recursive algorithms is to switch to insertion sort or selection sort for "small enough" sublists.

And, Wikipedia on bubble sort (emphasis added):

Bubble sort has worst-case and average complexity both О(n²), where n is the number of items being sorted. There exist many sorting algorithms with substantially better worst-case or average complexity of O(n log n). Even other О(n²) sorting algorithms, such as insertion sort, tend to have better performance than bubble sort. Therefore, bubble sort is not a practical sorting algorithm when n is large.

The only significant advantage that bubble sort has over most other implementations, even quicksort, but not insertion sort, is that the ability to detect that the list is sorted is efficiently built into the algorithm. Performance of bubble sort over an already-sorted list (best-case) is O(n). By contrast, most other algorithms, even those with better average-case complexity, perform their entire sorting process on the set and thus are more complex. However, not only does insertion sort have this mechanism too, but it also performs better on a list that is substantially sorted (having a small number of inversions).

Selection sort performs a smaller number of swaps compared to bubble sort; therefore, even though both sorting methods are of O(N²), selection sort performs faster and more efficiently!

while comparing these two algorithms we have to consider the two operations that are taking place in these algorithm i)comparison ii)swapping on the basis of comparison operation both are equally efficient but if you consider swapping operation you will find that selection sort is more efficient consider a array of size 100 in descending and we have to sort them in ascending order in this problem BUBBLE SORT will take 100*100=(10000)apprx swapping operations while in case of SELCTION SORT it will take only 100 swapping operations beacuse in selection sort at each iteration only one swapping take place

Bubble sort algorithm is considered to be the most simple and inefficient algorithm, but selection sort algorithm is efficient as compared to bubble sort. Bubble sort also consumes additional space for storing temporary variable and needs more swaps.

I can't seem to find a satisfying solution to this question here or elsewhere, though Senthil's link is headed in the right direction.

The question initially had me puzzled since bubble sort can be optimized by early termination of the outer loop after a sub-array (or linked list, etc) pass that fails to perform a value swap. Select sort can't be helped that way, so why would it outperform? Both are weak in general use - O(n^2) - so why isn't the one that can at least be marginally improved better?

The answer, based purely on examination of my own and other implementations, is that bubble sort does a value swap (read, write, write) on EVERY SINGLE COMPARISON HIT. Select sort just notes the new boundary value (min for an ascending sort, max for descending) and then swaps it out at the end of the pass.

void swapInt(int *ptr1, int *ptr2) {
   int temp;

   temp = *ptr1;
   *ptr1 = *ptr2;
   *ptr2 = temp;
}

/* compare and swap over a shrinking sub-array */
void bubbleSortArray(int a[], const int aSize) {
   int unsorted, i, iMax = (aSize - 1);

   do {
      unsorted = 0;
      for (i = 0; i < iMax; i++) {
         if ( a[i] > a[i + 1] ) {
            unsorted = 1;
            /* swap every time comparison is true */
            swapInt(&a[i], &a[i + 1]);
         }
      }
      --iMax;
   } while (unsorted);
}

/* compare to find min value, write it before shrinking the sub-array */
void selectSortArray(int a[], const int aSize) {
   int i, j, mindex;

   for (i = 0; i < (aSize - 1); i++) {
      mindex = i;
      for (j = (i + 1); j < aSize; j++) {
         if ( a[j] < a[mindex] ) mindex = j;
      }
      /* swap after inner loop terminates */
      swapInt(&a[i], &a[mindex]);
   }
}

Even though both of them have comparable and bad, worst and average case complexities, there are certain points which show that selection sort is better than bubble sort.

The Selection sort spends most of its time trying to find the minimum element in the "unsorted" part of the array. It clearly shows the similarity between Selection sort and Bubble sort. Bubble sort "selects" the maximum remaining elements at each stage, but wastes some effort imparting some order to "unsorted" part of the array.

Bubble sort uses more swap times, while selection sort avoids this.

When using selecting sort it swaps n times at most. but when using bubble sort, it swaps almost n*(n-1). And obviously reading time is less than writing time even in memory. The compare time and other running time can be ignored. So swap times is the critical bottleneck of the problem.

In bubble sort we have more number of comparisons and swapping.

in an array of 10 elements we have 9 comparisons in first pass,8 in second 7,6 and so on. And in each 8 or 9 comparisons we are just able to swap just on element.

Where as in selection sort we first find minimum element of all and place it at 0 index of elements.

Complexity of both the algorithms is O(n2), but in worst case bubble sort has complexity O(n2) and selection has complexity of O(n2) and in best case bubble sort has complexity O(n) and selection sort has O(n2)