1

Q#1

I am searching for a method to sort an array in ascending order. I found this and it works, but I don't understand how it works.

Q#2

As for the Big O notation, which method is better (n will be small in my case), the method below or Arrays.sort()? 

for (int i = 0; i < array; i++) {
   for (int j = 0; j < array; j++) {
      if (arr[i] < arr[j]) {
         order = arr[j];
         arr[j] = arr[i];
         arr[i] = order;
      }
    }
}

Note: array is equal to arr.length.

QuickSilver
  • 3,915
  • 2
  • 13
  • 29
Omar Eses
  • 23
  • 1
  • 8
  • Are you sure you didn't mean: "...to sort an array in **descending** order..."? – Janez Kuhar May 23 '20 at 09:49
  • Welcome to the StackOverflow community! Could you tag the post with the language you are using? This makes it easier to find and answer the question. – cadebe May 23 '20 at 09:53
  • @JanezKuhar yes i have tried both this way is for the ascending from little to big can you tell me how does it work. because i am trying to it kind a hard – Omar Eses May 23 '20 at 10:27
  • @GhostCat thanks for the hint, i am now reading about both of sorting bubble and insertion. now is it better to have Arrays,sort() or in the way up there. cause even though this method is o(n^2) it is quicker in measuring nano seconds, that is why i was wondering. – Omar Eses May 23 '20 at 10:45

1 Answers1

0

#1

The method you are using is closest to what is called a Selection Sort. A nice illustration can be found here and a more entertaining one here.

A proper implementation of a selection sort would start the inner loop at j = i + 1 and swap at most one element per each iteration of the outer loop (the minimum or maximum of elements in the unsorted part of the array with the i-th element). As it stands, the array still gets sorted correctly, but you are doing a lot of redundant comparisons and swaps.

Also note that your if logic sorts the array in descending order (and not in ascending, as you claim that it does).

#2

The time complexity of a Selection Sort is O(n^2), whereas Arrays.sort() uses Dual Pivot Quicksort with an O(nlogn) time complexity. There is also an optimisation built into the JDK's sorting algorithm that uses Insertion Sort on smaller arrays so there really is no reason for you to worry about performance.

Edit: Why is the sorting time faster using this method as opposed to using Arrays.sort()?

While the API docs state:

Implementation Note:

The sorting algorithm is a Dual-Pivot Quicksort...

the actual implementation is much more involved and contains all kinds of optimisations.

Of course, there can be a particular case where your sorting method is faster, but I would stick to using the JDK's sorting algorithm. It has been thoroughly tested and refined to assure correctness and optimal performance.

Another thing to consider, as @GhostCat has pointed out, is that your benchmarking might be flawed. Check How do I write a correct micro-benchmark in Java? for more on that topic.

Janez Kuhar
  • 3,705
  • 4
  • 22
  • 45
  • i was wondering because in the method up there it was giving me less time than Arrays,sort(). anyway thanks for answering second question, I would have voted you up but not much credits. – Omar Eses May 23 '20 at 10:31
  • 1
    @JanezKuhar yes now it is much better, thank u. the weird thing that arrays.sort took longer time in array.sort than in nanoTime array.sort took 282300 in nano and in this method 60200 so i was wondering if this has a relation with big O – Omar Eses May 23 '20 at 13:01