Common method comparison - c++ & java
Sort
C++
For c++, here is official document
sort()
This method sorts elements in the range [first, last).
Result is in ascending order by deflaut.
Introsort.
// sort algorithm example
#include <iostream> // std::cout
#include <algorithm> // std::sort
#include <vector> // std::vector
bool myfunction (int i,int j) { return (i>j); }
int main () {
int myints[] = {32,71,12,45,26,80,53,33};
std::vector<int> myvector (myints, myints+8); // 32 71 12 45 26 80 53 33
// using default comparison (operator <):
std::sort (myvector.begin(), myvector.begin()+4); //(12 32 45 71)26 80 53 33
// using function as comp
std::sort (myvector.begin(), myvector.end(), myfunction); //80 71 53 45 33 32 26 12
// print out content:
std::cout << "myvector contains:";
for (std::vector<int>::iterator it=myvector.begin(); it!=myvector.end(); ++it)
std::cout << ' ' << *it;
std::cout << '\n';
return 0;
}
On average, linearithmic in the distance between first and last: Performs approximately N*log2N
stable_sort()
sort()
is unstable. However, stable_sort()
preserves the relative order of the elements with equivalent value.
If enough extra memory is available, linearithmic in the distance between first and last: Performs up to N*log2(N) element comparisons (where N is this distance), and up to that many element moves.
Otherwise, polyloglinear in that distance: Performs up to N*log22(N) element comparisons, and up to that many element swaps.
partial_sort()
partial_sort()
sort first several elements while the remaining elements are left without any specific order.
int main(int argc, char const *argv[])
{
vector<int> myvector = {32,71,12,45,26,80,53,33};
partial_sort(myvector.begin(), myvector.begin() + 4, myvector.end());
//(12 26 32 33 71) 80 53 45
for(int i : myvector){
cout << i << " ";
}
cout << endl;
}
Java
sort(), primitive type and object type. parallelSort().collection.sort()
Array.sort()
Package: java.util.Arrays;
Sorts the specified array into ascending numerical order.
For primitive type, The sorting algorithm is a Dual-Pivot Quicksort(Orignal source) by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm offers O(n log(n)) performance on many data sets that cause other quicksorts to degrade to quadratic performance, and is typically faster than traditional (one-pivot) Quicksort implementations. This quicksort is unstable.
For object type, the sorting algorithm is Timsort which is combined character of merge sort and selection sort(wiki). This is a stable sort algorithm.
Primitive type
public static void sort(int[] a);
import java.util.Arrays;
public class test{
public static void main(String[] args) {
int[] test1 = {6,5,4,3,2,1};
int[] test2 = {6,5,4,3,2,1};
Arrays.sort(test1);
Arrays.sort(test2, 0, 3);
for (int i : test1) {
System.out.print(i + " ");
}
System.out.println(); //1 2 3 4 5 6
for (int i : test2) {
System.out.print(i + " ");
}
System.out.println(); //(4 5 6) 3 2 1
}
}
Object type
public static void sort(Object[] a)
public static void sort(Object[] a, int fromIndex, int toIndex)
public static <T> void sort(T[] a, Comparator<? super T> c)
public static <T> void sort(T[] a, int fromIndex, int toIndex, Comparator<? super T> c)
Arrays.parallelSort()
This is a stable sort algorithm.
Only if the size of array is larger than MIN_ARRAY_SORT_GRAN, algorithm can use multi-thread. (MIN_ARRAY_SORT_GRAN is 1«13, that is 8192, in source code.)
*The sorting algorithm is a parallel sort-merge that breaks the array into sub-arrays that are themselves sorted and then merged.(JavaDoc)
Container
import java.util.Collections;
import java.util.Comparator;
import java.util.ArrayList;
public class test{
public static void main(String[] args) {
ArrayList<Integer> test1 = new ArrayList<Integer>(Arrays.asList(9,3,2,1,8,7,6,5,4));
Comparator<Integer> reverseComparator = Collections.reverseOrder();
Collections.sort(test1,reverseComparator);
for (int i : test1) {
System.out.print(i + " ");
}
System.out.println(); //9 8 7 6 5 4 3 2 1
}
}