SORTING
Let m0, m1, …, mn-1 are n integers in array m (int m[1001]) to be sorted. You can use
STL function sort:
sort(m, m + n);
Here
• m = &m[0] is a pointer to the first element;
• m + n = &m[n] is a pointer to the elment that is next to the last element;
0 1 2 3 4 5
6 2 8 9 12 1
n = 6 elements
m m+n
If you have a vector (vector<int> v), use the next format:
sort(v.begin(), v.end());
0 1 2 3 4 5
6 2 8 9 12 1
v.begin() v.end()
E-OLYMP 2321. Sort Sort array of integers in nondecreasing order.
► Read the data into integer array. Sort the data using STL function sort. Print the
data.
Store the array of integers in vector v.
vector<int> v;
Read the numbers into the array.
scanf("%d",&n);
v.resize(n);
for(i = 0; i < n; i++)
scanf("%d",&v[i]);
Sort it with sort function.
sort(v.begin(),v.end());
Print the elements in nondecreasing order.
for(i = 0; i < n; i++)
printf("%d ",v[i]);
printf("\n");
In this problem you can use swap sort with complexity O(n2). Since n ≤ 1000, this
algorithm will pass the time limit. Iterate over all pairs (i, j), 0 ≤ i < j < n, and if m[i] >
m[j], swap them.
1 8 4 6 2 9 swap(m[i],m[j]) 1 2 4 6 8 9
i j i j
#include <stdio.h>
#define MAX 1010
int m[MAX];
int i, n;
void sort(void)
{
int i, j, temp;
for (i = 0; i < n; i++)
for (j = i + 1; j < n; j++)
if (m[i] > m[j])
{
temp = m[i]; m[i] = m[j]; m[j] = temp;
}
}
int main(void)
{
scanf("%d", &n);
for (i = 0; i < n; i++)
scanf("%d", &m[i]);
sort();
for (i = 0; i < n; i++)
printf("%d ", m[i]);
printf("\n");
return 0;
}
To sort the data in increasing or decreasing order you can use comparators:
• sort(m, m + n, less<int>()) – sort in increasing order;
• sort(m, m + n, greater<int>()) – sort in decreasing order;
To sort the vector v, use
• sort(v.begin(), v.end(), less<int>()) – sort in increasing order;
• sort(v.begin(), v.end(), greater<int>()) – sort in decreasing order;
To sort the data in increasing order, you can omit the comparator. Default order is
increasing.
E-OLYMP 4738. Sorting Sort array of integers in non-increasing order.
► Read the data into integer array. Sort the data using STL function sort and
greater<int>() comparator. Print the data.
You can write your own comparator. Comparator is a function of the form
int f(type a, type b)
{
. . .
}
that returns true (1), if elements a and b should not be swapped and false (0)
otherwise. Consider array m and two elements: a = m[i], b = m[j], where i < j. If m[i]
and m[j] must be swapped to preserve the sorting order, then comparator must return
false.
i j
a b
f(a, b)
true false
i j i j
a b b a
For sorted array the value of the function f(a, b) must be true for any elements a
and b such that position of a is less than the position of b. The next comparator sorts
array of integers in decreasing order:
int f(int a, int b)
{
return a > b;
}
12 9 7 7 7 5 2
a > b
Comparator a < b is equivalent to less<int>().
Comparator a > b is equivalent to greater<int>().
int f(int a, int b)
{
return a < b; less<int>()
}
int f(int a, int b)
{
return a > b; greater<int>()
}
Let’s solve this problem using our own comparator.
#include <cstdio>
#include <algorithm>
#define MAX 1001
using namespace std;
int m[MAX];
int i, n;
int f(int a, int b)
{
return a > b;
}
int main(void)
{
scanf("%d", &n);
for (i = 0; i < n; i++)
scanf("%d", &m[i]);
sort(m, m + n, f);
for (i = 0; i < n; i++)
printf("%d ", m[i]);
printf("\n");
return 0;
}
E-OLYMP 4848. Quick sort Sort the given sequence in non-decreasing order.
► Read the sequence of numbers into array till the end of file and use any sorting
algorithm.
Sort the letters / strings
E-OLYMP 8316. Sort the letters A string consisting of lowercase Latin letters is
given. Sort its letters in ascending and then in descending lexicographical order.
► Sort the strings using sort function from STL. Use the comparator
less<int>() for sorting in increasing order and comparator greater<int>() for
sorting in decreasing order.
Declare the character array.
#define MAX 101
char s[MAX];
Read the string.
gets(s);
Sort the letters in increasing order. Print the resulting string.
sort(s,s+strlen(s),less<int>());
puts(s);
Sort the letters in decreasing order. Print the resulting string.
sort(s,s+strlen(s),greater<int>());
puts(s);
Implementation using strings.
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
string s;
int main(void)
{
cin >> s;
sort(s.begin(),s.end(),less<int>());
cout << s << "\n";
sort(s.begin(),s.end(),greater<int>());
cout << s << "\n";
return 0;
}
E-OLYMP 2166. Anagrams The word is an anagram of another word, if it can be
obtained by rearrangement of its letters.
► Sort the letters in each word in lexicographic order. If the obtained words are the
same, then they consist of the same letters and thus are anagrams.
