sort

powrót

Funkcja sort zdefiniowana w bibliotece <algorithm> porządkuje elementy (domyślnie niemalejąco) w czasie O(n log n) a więc bardzo wydajnie. Funkcja ta nie gwarantuje, że pierwotne ustawienie elementów o tych samych wartościach zachowa swoją położenie względem siebie. Funkcja ta jest bardzo przydatna w sytuacji, gdy nie musimy implementować całego wydajnego algorytmu tylko skorzystać gotowego rozwiązania np. na różnego rodzaju konkursach programistycznych oraz  niekiedy na egzaminie maturalnym z informatyki. 

Jak korzystać z funkcji sort

1. Sortowanie tablicy liczb (znaków).

 

sort([nazwa_tablicy], [nazwa_tabilcy] + [liczba_elementów_do_posortowania]);


Posortujemy dziesięć liczb całkowitych:

#include<iostream>
#include<algorithm>
using namespace std;

int main()
{
	int tab[] = {9, 8, 7, 0, 8, 6, 3, 1, 7, 2};
	
	cout<<"Przed sortowaniem:\n";
	for(int i=0;i<10;i++)cout<<tab[i]<<' ';
	
	sort(tab, tab+10);
	
	cout<<"\nElementy uporządkowane:\n";
	for(int i=0;i<10;i++)cout<<tab[i]<<' ';
	
	cin.get();
	
	return 0;
}
 

 

Out:

Przed sortowaniem:
9 8 7 0 8 6 3 1 7 2
Elementy uporządkowane:
0 1 2 3 6 7 7 8 8 9
 

 

2. Sortowanie nie wszystkich elementów tablicy.

sort([nazwa_tablicy]+a, [nazwa_tabilcy] + b);

 

gdzie zaczynamy sortować od znaku o numerze a i kończymy na znaku o numerze b - 1 (numerujemy od 0):

 

#include<iostream>
#include<algorithm>
using namespace std;

int main()
{
	int tab[] = {9, 8, 7, 0, 8, 6, 3, 1, 7, 2};
	
	cout<<"Przed sortowaniem:\n";
	for(int i=0;i<10;i++)cout<<tab[i]<<' ';
	
	sort(tab+2, tab+7);
	
	cout<<"\nElementy uporządkowane:\n";
	for(int i=0;i<10;i++)cout<<tab[i]<<' ';
	
	cin.get();
	
	return 0;
}
 

 

Out:

Przed sortowaniem:
9 8 7 0 8 6 3 1 7 2
Elementy uporządkowane:
9 8 0 3 6 7 8 1 7 2
 

 

3. Sortowanie malejąco.


Najpierw definiujemy własną funkcję porównującą:

bool porownaj(int a, int b)
{
	//sprawdzamy, czy pierwszy element jest większy od drugiego
	return a>b; //domyślnie a<b
}

Następnie uruchamiamy funkcję sort z trzecim argumentem w postaci funkcji porównującej. Zauważmy, że w ten sposób możemy sami zdefiniować kryteria porównywania elementów tablicy.

 

#include<iostream>
#include<algorithm>
using namespace std;

bool porownaj(int a, int b)
{
	//sprawdzamy, czy pierwszy element jest większy od drugiego
	return a>b;
}

int main()
{
	int tab[] = {9, 8, 7, 0, 8, 6, 3, 1, 7, 2};
	
	cout<<"Przed sortowaniem:\n";
	for(int i=0;i<10;i++)cout<<tab[i]<<' ';
	
	sort(tab, tab+10, porownaj);
	
	cout<<"\nElementy uporządkowane:\n";
	for(int i=0;i<10;i++)cout<<tab[i]<<' ';
	
	cin.get();
	
	return 0;
}
 

 

Out:

Przed sortowaniem:
9 8 7 0 8 6 3 1 7 2
Elementy uporządkowane:
9 8 8 7 7 6 3 2 1 0
 

 

4. Sortowanie alfabetyczne (leksykograficzne).


Wystarczy dane wczytać do tablicy stringów, następnie uruchomić funkcję sort. Ta metoda zadziała dla wyrazów składających się wyłącznie z małych lub wyłącznie z wielkich liter. Jeśli chcemy, żeby funkcja działała dla wyrazów złożonych z małych lub wielkich liter, musimy odpowiednio zmodyfikować funkcję porównującą. Wiąże to się z tym, że kod ASCII litery A jest przed wszystkimi małymi literami.

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;

int main()
{
	string wyrazy[5];
	
	cout<<"Podaj dziesięć wyrazów:\n";
	
	//BASIA KASIA DARIA ANNA KAMILA
	for(int i=0;i<5;i++) cin>>wyrazy[i];
	
	sort(wyrazy, wyrazy+5);
	
	cout<<"Elementy posortowane:\n";
	for(int i=0; i<5; i++)
		cout<<wyrazy[i]<<endl;
	
	cin.ignore();
	cin.get();
	
	return 0;
}
 

 

Wejście/wyjście:

Podaj dziesięć wyrazów:
BASIA
KASIA
DARIA
ANNA
KAMILA
Elementy posortowane:
ANNA
BASIA
DARIA
KAMILA
KASIA
 

 

5. Sortowanie elementów vectora.

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;
void wypisz(int l)
{
	cout<<l<<" ";
}
int main()
{
	vector<int> tab;
	
	int n;
	cout<<"Podaj liczbę elementów do posortowania: ";
	cin>>n;
	tab.resize(n);
	
	cout<<"Podaj "<<n<<" elementów:\n";
	
	for(int i=0;i<n;i++)
		cin>>tab[i];
	
	sort(tab.begin(), tab.end());
	
	cout<<"Elementy posortowano:\n";
	//wypisanie elementów tablicy
	for_each(tab.begin(),tab.end(),wypisz);
	
	cin.ignore();
	cin.get();
	
	return 0;
}
 

 

Wejście/wyjście:

Podaj liczbę elementów do posortowania: 5
Podaj 5 elementów:
6 5 7 3 7
Elementy posortowano:
3 5 6 7 7

 

 

Inne artykuły z funkcją sort

  1. Sortowanie struktur