# Sorting algorithms

## Selection Sort

template <typename T>
void sel_sort (vector<T>& v) {
const int n = v.size();
for (int i = 0; i < n - 1; ++i) {
const int p = pos_min(v, i, n-1);
swap(v[i], v[p]);
}   }

template <typename T>
int pos_min (vector<T>& v, int l, int r) {
int p = l;
for (int j = l + 1; j <= r; ++j) {
if (v[j] < v[p]) {
p = j;
}   }
return p;
}


## Insertion Sort (v1)

template <typename T>
void ins_sort_1 (vector<T>& v) {
const int n = v.size();
for (int i = 1; i < n; ++i) {
for (int j = i; j > 0 and v[j - 1] > v[j]; --j) {
swap(v[j - 1], v[j]);
}   }   }


## Insertion Sort (v2)

Avoids swap-chaining: instead of doing swaps, tht elements are shifted to the right (this improves from three assignments per iteration to one).

template <typename T>
void ins_sort_2 (vector<T>& v) {
const int n = v.size();
for (int i = 1; i < n; ++i) {
const T x = v[i];
int j;
for (j = i; j > 0 and v[j - 1] > x; --j) {
v[j] = v[j - 1];
}
v[j] = x;
}   }


## Insertion Sort (v3)

In order to avoid the final test at each iteration, the smallest element is first placed at the first position of the table.

template <typename T>
void ins_sort_3 (vector<T>& v) {
const int n = v.size();
swap(v[0], v[pos_min(v, 0, n-1)]);
for (int i = 2; i < n; ++i) {
const T x = v[i];
int j;
for (j = i; v[j - 1] > x; --j) {
v[j] = v[j - 1];
}
v[j] = x;
}   }


## Bubblesort

template <typename T>
void bubble_sort (vector<T>& v) {
const int n = v.size();
for (int i = 0; i < n - 1; ++i) {
for (int j = n - 1; j > i; --j) {
if (v[j - 1] > v[j]) {
swap(v[j - 1], v[j]);
}   }   }   }


## Heapsort with ADT

template <typename T>
void heap_sort_0 (vector<T>& v) {
const int n = v.size();
priority_queue<T> pq;
for (int i = 0; i < n; ++i) {
pq.push(v[i]);
}
for (int i = n - 1; i >= 0; --i) {
v[i] = pq.top();
pq.pop();
}   }


## Heapsort

template <typename T>
void heap_sort (vector<T>& v) {
const int n = v.size();
make_heap(v);
for (int i = n - 1; i >= 1; --i) {
swap(v[0], v[i]);
sink(v, i, 0);
}   }

template <typename T>
void make_heap (vector<T>& v) {
const int n = v.size();
for (int i = n/2 - 1; i >= 0; i--) {
sink(v, n, i);
}   }

template <typename T>
void sink (vector<T>& v, int n, int i) {
const T x = v[i];
int c = 2*i + 1;
while (c < n) {
if (c+1 < n and v[c] < v[c + 1]) c++;
if (x >= v[c]) break;
v[i] = v[c];
i = c;
c = 2*i + 1;
}
v[i] = x;
}


## Mergesort (v1)

template <typename T>
void merge_sort_1 (vector<T>& v) {
merge_sort_1(v, 0, v.size() - 1);
}

template <typename T>
void merge_sort_1 (vector<T>& v, int l, int r) {
if (l < r) {
const int m = (l + r) / 2;
merge_sort_1(v, l, m);
merge_sort_1(v, m + 1, r);
merge(v, l, m, r);
}   }

template <typename T>
void merge (vector<T>& v, int l, int m, int r) {
vector<T> b(r - l + 1);
int i = l;
int j = m + 1;
int k = 0;
while (i <= m and j <= r) {
if (v[i] <= v[j]) b[k++] = v[i++];
else b[k++] = v[j++];
}
while (i <= m) b[k++] = v[i++];
while (j <= r) b[k++] = v[j++];
for (k = 0; k <= r - l; ++k) v[l + k] = b[k];
}


## Mergesort (v2)

Cuts the recursion when the subvector is “small enough” at which point it uses insertion sort.

template <typename T>
void merge_sort_2 (vector<T>& v) {
merge_sort_2(v, 0, v.size() - 1);
}

template <typename T>
void merge_sort_2 (vector<T>& v, int l, int r) {
const int CRITICAL_SIZE = 50;
if (r - l < CRITICAL_SIZE) {
ins_sort(v, l, r);
} else {
const int m = (l + r) / 2;
merge_sort_2(v, l, m);
merge_sort_2(v, m + 1, r);
merge(v, l, m, r);
}   }


## Mergesort with bottom-up merging

template <typename T>
void merge_sort_bu (vector<T>& v) {
const int n = v.size();
for (int m = 1; m < n; m *= 2) {
for (int i = 0; i < n - m; i += 2*m) {
merge(v, i, i + m - 1, min(i + 2 * m - 1, n - 1));
}   }   }


## Quicksort with Hoare’s partition (v1)

template <typename T>
void quick_sort_1 (vector<T>& v) {
quick_sort_1(v, 0, v.size() - 1);
}

template <typename T>
void quick_sort_1 (vector<T>& v, int l, int r) {
if (l < r) {
const int q = partition(v, l, r);
quick_sort_1(v, l, q);
quick_sort_1(v, q + 1, r);
}   }

template <typename T>
int partition (vector<T>& v, int l, int r) {
const T x = v[l];
int i = l - 1;
int j = r + 1;
for (;;) {
while (x < v[--j]);
while (v[++i] < x);
if (i >= j) return j;
swap(v[i], v[j]);
}   }


## Quicksort (v2)

Pivot is selected at random.

template <typename T>
void quick_sort_2 (vector<T>& v) {
quick_sort_2(v, 0, v.size() - 1);
}

template <typename T>
void quick_sort_2 (vector<T>& v, int l, int r) {
if (l < r) {
const int p = randint(l, r);
swap(v[l], v[p]);
const int q = partition(v, l, r);
quick_sort_2(v, l, q);
quick_sort_2(v, q + 1, r);
}   }


## Quicksort (v3)

Stops sorting when the subvector is “small enough”. At the end, a last pass is made with insertion sort.

template <typename T>
void quick_sort_3 (vector<T>& v) {
quick_psort_3(v, 0, v.size() - 1);
ins_sort(v, 0, v.size() - 1);
}

template <typename T>
void quick_psort_3 (vector<T>& v, int l, int r) {
const int CRITICAL_SIZE = 100;
if (r - l >= CRITICAL_SIZE) {
const int q = partition(v, l, r);
quick_psort_3(v, l, q);
quick_psort_3(v, q + 1, r);
}   }


Lliçons.jutge.org
Jordi Petit
Universitat Politècnica de Catalunya, 2023

Prohibit copiar. Tots els drets reservats.