Pengurutan

Pengurutan, secara umum, adalah konsep ketika elemen-elemen dalam sebuah wadah disusun ulang dalam urutan yang logis.

Pengurutan adalah salah satu teknik paling dasar dan mendasar yang diterapkan pada data melalui fungsi. Artinya, pengurutan memungkinkan kita menyusun rangkaian elemen dengan cara tertentu sesuai keinginan kita, mengikuti urutan yang logis.

Algoritma pengurutan membantu memanipulasi data sekaligus membantu menyelesaikan banyak masalah matematika dan pemrograman.

*Untuk menggunakan method tersebut, kita perlu menyertakan file header algorithm di bagian atas file C++ kita menggunakan #include <algorithm>.

Kamu akan mempelajari fungsi bawaan dalam library algoritma STL yang digunakan untuk mengurutkan data. 
Tiga fungsi yang akan kita pelajari adalah:

• sort()
• is_sorted()
• partial_sort()

method sort

method sort() dari STL mengurutkan isi rentang yang diberikan. method ini memerlukan iterator awal dan iterator akhir, lalu mengurutkan elemen dalam rentang tersebut secara menaik.

Kita dapat menggunakannya dalam dua versi:

• sort(starting_iterator, ending_iterator) - mengurutkan rentang yang ditentukan oleh iterator secara menaik
• sort(starting_iterator, ending_iterator, comparing_function) - mengurutkan rentang yang ditentukan oleh iterator berdasarkan fungsi yang diberikan sebagai parameter ketiga

vector<int> numbers = {3, 5, 1, 2, 4};

sort(numbers.begin(), numbers.end());

for(auto i = numbers.begin(); i != numbers.end(); i++)
	cout << *i << " ";

Output:
1 2 3 4 5

Seperti yang kamu lihat dari kode di atas, method sort() mengurutkan vector secara menaik.

bool compare(int a, int b)
{
	return a > b; // kembalikan 1 jika a lebih besar dari b
}

int main()
{
	vector<int> numbers = {3, 5, 1, 2, 4};
	
	sort(numbers.begin(), numbers.end(), compare);
	
	for(auto i = numbers.begin(); i != numbers.end(); i++)
		cout << *i << " ";

Output:
5 4 3 2 1

Jadi, kamu bisa melihat bagaimana kita menggunakan versi kedua method sort. Kita membuat fungsi compare() agar mengembalikan nilai true jika a lebih besar daripada b. Ini memungkinkan kita mengurutkan vector secara menurun.

method is_sorted

method is_sorted() adalah fungsi STL yang mengembalikan true atau false untuk menunjukkan apakah rentang yang diberikan sudah diurutkan atau belum. 

Ada juga dua versi method is_sorted(), sama persis seperti method sort():

• is_sorted(starting_iterator, ending_iterator) - Memeriksa apakah rentang yang ditentukan oleh kedua iterator diurutkan secara menaik, mengembalikan true jika ya, dan mengembalikan false jika tidak
• is_sorted(starting_iterator, ending_iterator, comparing_function) - Memeriksa apakah rentang yang ditentukan oleh kedua iterator sudah diurutkan berdasarkan fungsi pembanding.

vector<int> numbers = {3, 5, 1, 2, 4};

cout << is_sorted(numbers.begin(), numbers.end()) << endl;

sort(numbers.begin(), numbers.end());

cout << is_sorted(numbers.begin(), numbers.end());

Output:
0
1

bool compare(int a, int b)
{
	return a > b; // kembalikan 1 jika a lebih besar dari b
}

int main()
{
	vector<int> numbers = {3, 5, 1, 2, 4};
	
	cout << is_sorted(numbers.begin(), numbers.end(), compare) << endl;
	
	sort(numbers.begin(), numbers.end(), compare);
	
	cout << is_sorted(numbers.begin(), numbers.end(), compare);

Output:
0
1

method partial_sort

method parital_sort() mengurutkan separuh pertama elemen dalam rentang yang diberikan dan membiarkan separuh elemen lainnya seperti semula. 
method ini juga memiliki dua versi:

• partial_sort(start, middle, end) - Mengurutkan rentang dari start hingga end sehingga elemen dari iterator awal hingga iterator tengah diurutkan secara menaik, sedangkan elemen dari iterator tengah hingga iterator akhir dibiarkan seperti semula
• partial_sort(start, middle, end, compare) - Mengurutkan rentang dari start hingga end sehingga elemen dari start hingga middle diurutkan berdasarkan fungsi pembanding, sedangkan elemen dari middle hingga end dibiarkan seperti semula

vector<int> numbers = {3, 5, 1, 2, 4, 10, 7};

partial_sort(numbers.begin(), numbers.begin() + 4, numbers.end());

for(auto i = numbers.begin(); i != numbers.end(); i++)
		cout << *i << " ";

Output:
1 2 3 4 5 10 7

bool compare(int a, int b)
{
	return a > b; // kembalikan 1 jika a lebih besar dari b
}

int main()
{
	vector<int> numbers = {3, 5, 1, 2, 4, 10, 7};
	
	partial_sort(numbers.begin(), numbers.begin() + 3, numbers.end(), compare);
	
	for(auto i = numbers.begin(); i != numbers.end(); i++)
		cout << *i << " ";

Output:
10 7 5 1 2 3 4

Seperti yang kamu lihat, method partial_sort() bekerja sedikit berbeda, tetapi kamu tidak perlu memusingkannya karena kamu akan jarang menggunakan pengurutan parsial. 

Untuk saat ini, ingatlah apa itu pengurutan, ingat cara menggunakan method sort() dan is_sorted() dengan benar, lalu berlatihlah menggunakannya.