AVAILABLE: 5
Sorting is defined as reorganizing a set of objects according to certain rules. Types of sorting include:
- Ascending order: Arranging data from the smallest to the largest.
- Descending order: Arranging data from the largest to the smallest.
The advantages of sorted data include ease in searching for specific data, and convenience in updating, inserting new data, deleting, or merging datasets.
1. Direct Insertion Sorting
Pseudocode:
- Start with
n = 1
. - Take the
n
-th element and find the insertion position based on the criteria. - Shift elements from the insertion position up to the
n
-th element. - Insert the element into the appropriate position.
- Increment
n
by 1. - Repeat steps 2–5 until all elements are sorted.
Example:
Initial Data | 10 | 5 | 12 | 0 | 32 | 56 | 34 | 6 | 11 | 99 |
---|---|---|---|---|---|---|---|---|---|---|
Process 1 | 5 | 10 | 12 | 0 | 32 | 56 | 34 | 6 | 11 | 99 |
Process 2 | 5 | 10 | 12 | 0 | 32 | 56 | 34 | 6 | 11 | 99 |
Process 3 | 0 | 5 | 12 | 10 | 32 | 56 | 34 | 6 | 11 | 99 |
Process 4 | 0 | 5 | 10 | 12 | 32 | 56 | 34 | 6 | 11 | 99 |
Process 5 | 0 | 5 | 10 | 12 | 32 | 34 | 56 | 6 | 11 | 99 |
Process 6 | 0 | 5 | 6 | 10 | 12 | 32 | 34 | 56 | 11 | 99 |
Process 7 | 0 | 5 | 6 | 10 | 12 | 32 | 34 | 56 | 11 | 99 |
Process 8 | 0 | 5 | 6 | 10 | 11 | 12 | 32 | 34 | 56 | 99 |
Sorted | 0 | 5 | 6 | 10 | 11 | 12 | 32 | 34 | 56 | 99 |
Program:
int j, x;
for (int i = 1; i < 10; i++) {
x = arr[i];
j = i - 1;
while (x < arr[j]) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = x;
}
2. Direct Selection Sorting
This method selects the smallest (ascending) or largest (descending) element and places it at the leftmost position through swapping.
Pseudocode:
- Repeat steps 2–4 for
i = 1
ton-1
: - Set
location = i
. - For
j = i+1
ton
:- If
arr[location] > arr[j]
, setlocation = j
.
- If
- Swap
arr[location]
witharr[i]
.
Example:
Initial Data | 10 | 5 | 12 | 0 | 32 | 56 | 34 | 6 | 11 | 99 |
---|---|---|---|---|---|---|---|---|---|---|
Process 1 | 0 | 10 | 12 | 5 | 32 | 56 | 34 | 6 | 11 | 99 |
Process 2 | 0 | 5 | 12 | 10 | 32 | 56 | 34 | 6 | 11 | 99 |
Process 3 | 0 | 5 | 6 | 10 | 32 | 56 | 34 | 12 | 11 | 99 |
Process 4 | 0 | 5 | 6 | 10 | 32 | 56 | 34 | 12 | 11 | 99 |
Process 5 | 0 | 5 | 6 | 10 | 11 | 56 | 34 | 12 | 32 | 99 |
Process 6 | 0 | 5 | 6 | 10 | 11 | 12 | 34 | 56 | 32 | 99 |
Process 7 | 0 | 5 | 6 | 10 | 11 | 12 | 32 | 56 | 34 | 99 |
Process 8 | 0 | 5 | 6 | 10 | 11 | 12 | 32 | 34 | 56 | 99 |
Program:
int location, temp;
for (int i = 0; i < 10; i++) {
location = i;
for (int j = i + 1; j < 10; j++) {
if (arr[location] > arr[j])
location = j;
}
temp = arr[location];
arr[location] = arr[i];
arr[i] = temp;
}
3. Bubble Sort
This method compares adjacent elements and swaps them if they are in the wrong order.
Pseudocode:
- For
i = 1
ton
:- For
j = n
to1
:- If
arr[j-1] > arr[j]
, swaparr[j-1]
andarr[j]
.
- If
- For
Program:
int temp;
for (int i = 1; i < 10; i++) {
for (int j = 9; j > 0; j--) {
if (arr[j - 1] > arr[j]) {
temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
}
}
}
Example Program:
#include <iostream>
#include <conio.h>
void main() {
int arr[10] = {10, 5, 12, 0, 32, 56, 34, 6, 11, 99};
int x, j;
std::cout << "Data before sorting: " << std::endl;
for (int i = 0; i < 10; i++)
std::cout << arr[i] << " ";
std::cout << std::endl;
for (int i = 1; i < 10; i++) {
x = arr[i];
j = i - 1;
while (x < arr[j] && j >= 0) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = x;
}
std::cout << "Data after sorting: " << std::endl;
for (int i = 0; i < 10; i++)
std::cout << arr[i] << " ";
getch();
}
Source:
Data Structures course notes from STMIK EL Rahma Yogyakarta, authored by Eko Riswanto.