CODEWITHSUNDEEP
javaalgorithm
wliao
wliao

Reputation: 1416

Sorting algorithm of Arrays in Java.util package

 /**
 * Sorts the specified sub-array of bytes into ascending order.
 */
private static void sort1(byte x[], int off, int len) {
// Insertion sort on smallest arrays
if (len < 7) {
    for (int i=off; i<len+off; i++)
    for (int j=i; j>off && x[j-1]>x[j]; j--)
        swap(x, j, j-1);
    return;
}

From Arrays.java line 804-814

As quoted above, it's claiming of using Insertion Sort. However, I'm taking it as Bubble Sort? Which one it's actually is, and why?

Upvotes: 11

Views: 981

Answers (4)

Pih
Pih

Reputation: 2278

This whole sorting algorithm is an optimized quick sort that use median of 3 indexed elements to get pivot element, and the code that you showed, is an optimization when the input array (or from the the recursion) is small.

Although, the quoted part is an insertion sort, no doubt.

But it is wrong just look this part of algorithm, so, using this link:

  • Lines 573-577 make an insertion sort, for small input arrays.
  • Lines 581-593 choice the pivot element, using median of 3.
  • Lines 596-611 does the sorting using the pivot element.
  • Lines 614-616 puts the partition element elements back to the middle (quick sort stuff).
  • Lines 619-622 recursion of the two halves of the input array.

A good explanation about quick sort could be find at http://en.wikipedia.org/wiki/Quicksort.

Upvotes: 3

Vincent Cantin
Vincent Cantin

Reputation: 17292

Bubble sort only swaps elements located at consecutive indices.

Update: the comment in the source code might wrong :-)

Upvotes: 0

artbristol
artbristol

Reputation: 32437

The quoted code is an insertion sort. A bubble sort repeatedly passes through the entire array, whereas an insertion sort sorts the first element, then the first two elements, then the first three elements, etc. You can tell because the code has two indexed loops, whereas the outer loop on a bubble sort just checks whether the whole array is in order or not.

Upvotes: 4

Wu Yongzheng
Wu Yongzheng

Reputation: 1717

For an already sorted array, bubble sort's outer loop only go once, but insertion's outer loop run n times (although only 1 comparison for each outer loop).

I think it's obvious that it's insertion sort.

Upvotes: 0

Related Questions