Bubble Sort
- Also call as sinking sort or exchange sort
- Ascending : sorting from small to big
- Descending : sorting from big to small
- Value into array
- Adjacent value compared
- If increasing, then change to become decreasing
- At round :
- 2, array at 2 ( index 1) is a second smallest value
- n-1. array at n ( index n-1 ) is a biggest value
- Number of round = n - 1
void swap ( int & a, int & b ){
int temp = a
a = b;
b = temp;
Bubble sort
void bubbleSort ( int arr[], int n) {
for ( int i = 0; i < n - 1; i++ ) {
for ( int j= n-1; j > i; j-- ) { //Mulai dari belakang
if (arr [j] < arr [j - 1] {
swap ( arr [j], arr [j - 1 ]);
}
}
}
}
main
int main () {
int arr[] = {5 ,1, 4, 2, 8};
int n = sizeof(arr) / siozeof(arr[o]);
bubbleSort ( arr, n );
for ( int i = 0; i < n, i++ ) {
cout << arr[i] << "";
}
cout << endl;
return 0;
}
Kode Lengkap
#include <iostream>
using namespace std;
void bubbleSort ( int arr[], int n ) {
for ( int i = 0; i< n-1 1; i++) {
for (int j = n -1; j < i; j--) { //Mulai dari belakang
if ( arr[j] < arr [j - 1 ] ){
swap (arr [j] < arr [ j -1 ];
}
}
}
}
int main () {
int arr [] = { 5, 1, 4, 2, 8 };
int n = sizeoff (arr) / sizeof (arr[0]);
bubbleSort (arr , n );
for (int i = 0; i < n; i++) {
cout << arr [i] << "";
}
cout << endl;
return 0;
}
Selection Sort
- Value sent into array
- Search for the biggest value put at the end of arrray
- At round :
-2. array at 2 ( index 1 ) is a second small value
- n -1, array at n ( index n-1 ) is a biggest value number of round = n -1
Kode selectionSort
void selectionSort ( int arr [], int n ) {
for ( int i = n -1; i > =0; i--) {
int maxldx = 0;
for ( int j =1; j <= i;j++){
if ( arr [j] > arr { maxldx]) {
maxldx = j;
}
}
// Tukar elemen terbesar dengan elemen di posisi i swap ( arr [maxldx], arr [i]);
}
}
main
int main () {
int arr [] = { 64, 25 , 12, 22, 11 };
int n = sizeof(arr)/ sizeof(arr[0]);
cout << " Array sebelum sorting:";
for ( int i = 0;i < n; i++ ) {
cout << arr [i] << "";
}
cout << endl;
selectionSort (arr,n);
cout << " Array setelah sorting descending:";
for ( int i=0; i< n; i++) {
cout << arr[i] << "";
}
cout << endl;
return 0;
}
Insertion Sort
- Value sent into array
- Using helper container
- Value compared with index previously
- Every round did not produce the biggest value or the smallest value,
- Number of round = n -1
#include <iostream>
using namespace std;
void insertionSort (int arr[], int n) {
for (int i =1; i< n; i++) {
int key = arr[i];
int j = i - 1;
// Geser elemen yang lebih besar dari key ke kanan
while (j >= 0 && arr [j] > key) {
arr [ j + 1 ] = arr [j];
j-;
}
// Sisipkan key di posisi yang tepat
arr [ j + 1 ] = key;
}
}
int main () {
int arr [] = { 12, 11, 13, 5, 6 };
int n = sizeof (arr) / sizeof ( arr[0]);
cout << " Array sebelum sorting:";
for ( int i = 0; i < n; i++) {
cout << arr [i] << "";
}
cout << endl;
insertionSort (arr,n);
cout << " Array setelah sorting:";
for ( int i= 0; i < n; i++ ) {
cout << arr [i] << "";
}
cout << endl;
return 0;
}
Merge Sort
- Value sent into array
- divided data become two based on index
- Each one sorted
- Re-Merge data
Tidak ada komentar:
Posting Komentar