CODEWITHSUNDEEP
javaalgorithmsortingjava-streamtime-complexity
user18085807
user18085807

Reputation:

Does Java stream().sorted or list.sort() not increases time complexity?

While making some sortings, some people suggest using stream().sorted or list.sort() methods in Java to reduce time complexity. However, I think these methods also use some sorting algorithms that has a similar time complexity.

List result = list.stream().sorted((o1, o2)->o1.getItem().getValue().
                                   compareTo(o2.getItem().getValue())).
                                   collect(Collectors.toList());

So, does it mean that these algorithms use the most efficient sorting algorithms for sorting less time than I sort in 2 nested for loop?

Upvotes: 1

Views: 1115

Answers (3)

Alexander Ivanchenko
Alexander Ivanchenko

Reputation: 29028

The very first impotent thing that you have to understand about any kind of algorithm is that just talking about algorithms will not significantly change your knowledge in this area.

You have to study and practice them, implementing algorithms step by step.

If want to improve your understanding of sorting algorithms you need to start with the very basic like bubble sort and insertion sort (descriptions and pseudocode could've found in Wikipedia is quite enough to grasp the idea and start coding). When you'll have a firm understanding of the basics that you ready to go with merge sort and quicksort.

Here is a small insight on what is happening inside the so-called dual-pivot quicksort provided by JDK.

In fact, it's a very advanced compound algorithm which apart from the conventional quicksort entails merge sort, heap sort, and parallel computing in case of a massive data set.

Only when you know all proc and cons of the essential algorithms (like why there are different portition schemes out there, why quicksort is preferred over merge sort meanwhile in the worse case time complexity of the merge sort seems better, etc) it make sense to speculate about the optimizations that are going the dual-pivot quicksort.

For now short answer with regards to the performance of the build-in quicksort:

guarantees n*log(n) on any data

Now about Streams and sorting.

Sorting is always happening inside the array in place. If the source of data is backed by the array an ArrayList or CopyOnWriteArrayList, then its underlying array will get sorted.

Otherwise, for instance, if you are dialing with a LinkedList, a new array will be allocated in memory and all the data from the list will be copied to this array and then get sorted.

And when you are dialing with a stream it'll not affect the source of data. The whole data from the source requires to be loaded into memory to be sorted. And then you most likely will store it in a brand collection.

Conclusion:

  • if you need to change a source of data - use the sort() method with the list directly;
  • if your task doesn't require sorting all the initial data (or you simply want to preserve the initial state of the source) - then Stream API will give a hand with filtering and sorting.

Upvotes: 0

AliShokri
AliShokri

Reputation: 21

The time complexity of these methods is O(nlog(n)). And it's the best time complexity for sorting an array.

Upvotes: 1

mute_police
mute_police

Reputation: 73

Sorting algorithms that use nested loops are usually O(n²) complexity, due to every iteration of the inner loop occurring for every iteration of the outer loop. Some of these algorithms would be

  • Insertion Sort;
  • Bubble Sort;
  • etc;

However, other do not use nested loops as you mentioned, for example, the most used sorting algorithm for general use would be QuickSort, which stands as a Divide and Conquer Algorithm, it starts by selecting a pivot value and rearranging the array based on said pivot value, with all smaller values coming before it, and all larger values coming after it (Not necessarily ordered yet).

QuickSort stands as O(nlog(n)) Average case complexity. Do bear in mind that some of the more advanced sorting algorithms also have a worst case scenario complexity of O(n^2).

In fact, some sorting implementations actually shuffle the array before sorting it just to avoid the worst case scenario.

I leave here some information about Quicksort below.

Quicksort explanation and how it works

Upvotes: 0

Related Questions