Sorting

Sorting

What sorted means, selection sort by hand and what it costs, sort on a vector, an array, a part and in decreasing order, sorting strings and characters, sorting pairs to remember original positions, and what a sorted vector makes easy.

Назария

Дарси 3 аз 12

Хониш: 11 дақиқа

Саволҳо: 5

A list of marks, a list of prices, the children of a class by height: a great many problems start with "put these in order", and a great many others become easy the moment the data is in order. This lesson is about sorting — first doing it by hand once, to see what it costs, and then letting C++ do it.

What "sorted" means

A vector is sorted in increasing order when every element is at least as large as the one before it: a[i - 1] <= a[i] for every i. Equal values are allowed next to each other, so 1 3 3 7 is sorted. Sorting rearranges the values and nothing else: the same numbers, the same number of copies of each, in a new order.

Read n marks. Print them from the lowest to the highest, and then the top three.

Sorting by hand: selection sort

Here is how a person would do it with a row of cards. Find the smallest card and swap it to the front. Then find the smallest of the rest and swap it into second place. Keep going; each turn fixes one more position for good. This is selection sort, because every turn selects the smallest of what is left:

Selection sort: the smallest of the rest moves to the front

C++

1#include <bits/stdc++.h>

2using namespace std;

4int main() {

5 ios_base::sync_with_stdio(false);

6 cin.tie(NULL);

8 vector<int> a = {7, 3, 9, 1};

9 int n = 4;

10 for (int i = 0; i < n - 1; i++) {

11 int best = i;

12 for (int j = i + 1; j < n; j++) {

13 if (a[j] < a[best]) {

14 best = j;

15 }

16 }

17 swap(a[i], a[best]);

18 }

19 for (int x : a) {

20 cout << x << " ";

21 }

22 cout << "\n";

23 return 0;

24}

Four numbers

сатр 8

Selection sort: find the smallest, put it first; then the smallest of the rest, put it second; and so on.

a4 катак

n—i—best—j—x—

1 / 40

Question	After sorting
the smallest and the largest	`a[0]` and `a[n - 1]`
the k-th smallest (k from 1)	`a[k - 1]`
the median of n values	the middle element, `a[(n - 1) / 2]`; for even n there are two middles, and this is the lower one, the lower median
are there two equal values?	compare each `a[i]` with `a[i - 1]`
the closest two values	the smallest `a[i] - a[i - 1]`: close values are now neighbours

What "sorted" means

Sorting by hand: selection sort

Practice: Sorting

sort: let the library do it

Strings and characters

Sorting pairs: remember where things came from

What sorting unlocks

Check your understanding