Sort

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.

Sort

Uploaded by

Copyright:

Available Formats

Sort

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Sort

Uploaded by

Copyright:

Available Formats

SORTING

E-OLYMP 2321. Sort Sort array of integers in nondecreasing order.

Read the numbers into the array.

Sort it with sort function.

Print the elements in nondecreasing order.

for (i = 0; i < n; i++)

E-OLYMP 4738. Sorting Sort array of integers in non-increasing order.

int f(int a, int b)

Comparator a < b is equivalent to less<int>().

Let’s solve this problem using our own comparator.

int f(int a, int b)

for (i = 0; i < n; i++)

Sort the letters / strings

Declare the character array.

Read the string.

Sort the letters in increasing order. Print the resulting string.

Sort the letters in decreasing order. Print the resulting string.

Implementation using strings.

E-OLYMP 2166. Anagrams The word is an anagram of another word, if it can be

You might also like