Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Sorting algorithm of Arrays in Java.util package

Tags:

java

algorithm

 /**
 * 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?

like image 534
wliao Avatar asked May 16 '11 08:05

wliao


People also ask

Which algorithm does arrays sort use in Java?

As mentioned in the official JavaDoc, Arrays. sort uses dual-pivot Quicksort on primitives. It offers O(n log(n)) performance and is typically faster than traditional (one-pivot) Quicksort implementations. However, it uses a stable, adaptive, iterative implementation of mergesort algorithm for Array of Objects.

What is arrays sort algorithm?

Arrays. sort(Object[]) is based on the TimSort algorithm, giving us a time complexity of O(n log(n)). In short, TimSort makes use of the Insertion sort and the MergeSort algorithms. However, it is still slower compared to other sorting algorithms like some of the QuickSort implementations.

How does sort () work in Java?

The sort method transfers control to the compare method, and compare method returns values based on the arguments passed: If both the objects are equal, returns 0. If the first object is greater than the second, returns a value > 0. If the second object is greater than the first, returns a value < 0.


2 Answers

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.

like image 102
artbristol Avatar answered Oct 11 '22 18:10

artbristol


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.

like image 42
Pih Avatar answered Oct 11 '22 17:10

Pih