# Sort

Last Updated: 2024-01-20
``````interface Sorter {
public  <T extends Comparable<? super T>> void sort(T[] a);
}
``````

## Quick Sort

``````class QuickSorter implements Sorter {
public <T extends Comparable<? super T>> void sort(T[] a) {
sort(a, 0, a.length - 1);
}

public <T extends Comparable<? super T>> void sort(T[] a, int low, int high) {
T pivot = a[(low+high)/2];
int i = low, j = high;
while (i <= j) {
while (a[i].compareTo(pivot) < 0) i++;
while (a[j].compareTo(pivot) > 0) j--;
T tmp = a[j];
a[j--] = a[i];
a[i++] = tmp;
}
if (low < j)
sort(a, low, j);
if (i < high)
sort(a, i, high);
}
}
``````

in python

``````def qsort(L):
if L == []:
return []
pivot = L[0]
return (qsort([x for x in L[1:] if x < pivot]) +
[pivot] +
qsort([x for x in L[1:] if x >= pivot]))
``````

## Heap Sort

``````class HeapSorter implements Sorter {
public <T extends Comparable<? super T>> void sort(T[] a) {
sort(a, 0, a.length - 1);
}

public <T extends Comparable<? super T>> void sort(T[] a, int low, int high) {
int size = a.length;

// Build Heap
for (int k = size / 2; k >= 0; k--) {
sink(a, k, size);
}

//Sort
while (size > 1) {
swap(a, 0, --size);
sink(a, 0, size);
}
}

private <T extends Comparable<? super T>> void sink(T[] a, int k, int size) {
int l = 2 * k;
int r = 2 * k + 1;
int largest;
if (l < size && a[l].compareTo(a[k]) > 0)
largest = l;
else
largest = k;
if (r < size && a[r].compareTo(a[largest]) > 0)
largest = r;
if (largest != k) {
swap(a, k, largest);
sink(a, largest, size);
}
}

private <T extends Comparable<? super T>> void swap(T[] a, int i, int j) {
T tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
}
``````

insertion sort is the algorithm of choice either when the data is nearly sorted (because it is adaptive) or when the problem size is small (because it has low overhead).

### C++

``````vector<int> vals = {-1, -2, -3, 1, 2, 3, 0};
int p = 2;

sort(vals.begin(),
vals.end(),
[p](int a, int b) {
return pow(a, p) < pow(b, p);
});
``````

### Java 8+

``````list.stream().sorted()
``````

Or

``````list.sort((Foo o1, Foo o2) -> o1.getBar() - o2.getBar());
``````

Reverse

``````list.stream().sorted(Comparator.reverseOrder())
``````

Use `Collections.sort()`

``````Collections.sort(vals, (a, b) ->
Integer.compare(Math.pow(a, p), Math.pow(b, p)));
``````

### JavaScript

Sort array

``````arr.sort((a,b) => { return parseFloat(a.data) - parseFloat(b.data) } );

arr.sort((a,b) => { return a.str.localeCompare(b.str) } );

arr.sort((a,b) => { return a.str.toUpperCase().localeCompare(b.str.toUpperCase() } );
``````

Sort object

``````const sortedObj = Object.keys(obj)
.sort()
.reverse()
.reduce((newObj, k) => {
newObj[k] = obj[k];
return newObj;
}, {});
``````

### Python

By default, `sort`, `sorted`, `heapq` can sort tuples: the first element first and on the second element second. Can specify `key` to override default. `cmp` is deprecated in Python 3

``````sorted_data = sorted(data, key=lambda x: x['key'])
``````

or sorts in place

``````data.sort(key=lambda x: x['key'])
``````

Sort on multiple keys, suppose x is a tuple `(int, int, boolean)`

``````data.sort(key=lambda x: (x[0], not x[2]))
``````

Sort dict

``````import operator
sorted_x = sorted(x.iteritems(), key=operator.itemgetter(1), reverse=True)
``````

https://docs.python.org/3/howto/sorting.html

### Rust

``````let mut vals = [-1, -2, -3, 1, 2, 3, 0];
let p = 2;

vals.sort_by(|a :&isize, b :&isize|
a.pow(p).cmp(&b.pow(p)));
``````