SORTING
I. Learning Objectives
After this lesson, the students will be able to:
1. Explain the concept, characteristics, and purpose of sorting algorithms and distinguish between common sorting
types with at least 80% accuracy in a written assessment.
2. Implement at least five sorting algorithms in Java and correctly demonstrate how each method organizes data
from unsorted to sorted form.
3. Analyze and compare the time and space complexities of different sorting algorithms and justify which algorithm
is best for a given problem scenario by the end of the lesson period.
II. Definition, Characteristics, Pros & Cons, Real-World Applications
Definition of Sorting
Sorting is the process of arranging data in a specific order—typically ascending or descending—based on a defined
comparison rule. It is a fundamental operation in data structures and algorithms because it improves data organization,
retrieval speed, and overall computational efficiency.
Characteristics of Sorting Algorithms
Characteristic Meaning
Time Complexity Measures efficiency; best, average, and worst-case performance.
Space Complexity How much extra memory the algorithm uses (in-place vs not in-place).
Stability Stable algorithms preserve the relative order of equal elements.
Comparison-based / Non- Whether sorting relies on comparing elements (e.g., QuickSort) or uses other
comparison-based techniques (e.g., Counting Sort).
Adaptive Can take advantage of partially sorted input (e.g., Insertion Sort).
Recursive / Iterative Whether the algorithm is implemented using recursion (e.g., Merge Sort) or
loops (e.g., Selection Sort).
Pros and Cons of Sorting Algorithms
1. Bubble Sort
• ✔ Pros: Easy to understand, stable
• ✘ Cons: Very slow for large datasets (O(n²))
2. Selection Sort
• ✔ Pros: Minimal number of swaps
• ✘ Cons: Still O(n²), not stable
3. Insertion Sort
• ✔ Pros: Excellent for nearly-sorted data, stable, adaptive
• ✘ Cons: O(n²) for large unordered data
4. Merge Sort
• ✔ Pros: O(n log n) time always, stable, ideal for large data
• ✘ Cons: Requires extra memory (not in-place)
5. QuickSort
• ✔ Pros: Very fast on average (O(n log n)), in-place
• ✘ Cons: Worst case O(n²) when data is already sorted (unless optimized)
Real-World Applications of Sorting
1. E-commerce
Sorting product listings by price, popularity, ratings, or date added.
2. Search Algorithms
Searching is faster on sorted data (binary search requires sorting).
3. Databases
Efficient indexing, query optimization, and join operations.
4. Operating Systems
Sorting processes, memory blocks, and file indices.
5. Data Analytics & Machine Learning
Sorting large datasets for clustering, preprocessing, or ranking.
6. Networking
Packet management based on priority or arrival time.
III. Five Java Programs Using Sorting
1. Bubble Sort (Ascending Order)
public class BubbleSort {
public static void main(String[] args) {
int[] arr = {5, 1, 4, 2, 8};
for (int i = 0; i < [Link] - 1; i++) {
for (int j = 0; j < [Link] - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
[Link]("Sorted Array:");
for (int x : arr) [Link](x + " ");
}
}
2. Selection Sort
public class SelectionSort {
public static void main(String[] args) {
int[] arr = {29, 10, 14, 37, 13};
for (int i = 0; i < [Link]; i++) {
int minIndex = i;
for (int j = i + 1; j < [Link]; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
for (int x : arr) [Link](x + " ");
}
}
3. Insertion Sort
public class InsertionSort {
public static void main(String[] args) {
int[] arr = {9, 5, 1, 4, 3};
for (int i = 1; i < [Link]; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
for (int x : arr) [Link](x + " ");
}
}
4. Merge Sort
public class MergeSort {
public static void merge(int[] arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int[] L = new int[n1];
int[] R = new int[n2];
for (int i = 0; i < n1; i++)
L[i] = arr[left + i];
for (int j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) arr[k++] = L[i++];
else arr[k++] = R[j++];
}
while (i < n1) arr[k++] = L[i++];
while (j < n2) arr[k++] = R[j++];
}
public static void sort(int[] arr, int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
sort(arr, left, mid);
sort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
public static void main(String[] args) {
int[] arr = {12, 11, 13, 5, 6, 7};
sort(arr, 0, [Link] - 1);
for (int x : arr) [Link](x + " ");
}
}
5. QuickSort
public class QuickSort {
public static int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
public static void main(String[] args) {
int[] arr = {10, 7, 8, 9, 1, 5};
quickSort(arr, 0, [Link] - 1);
for (int x : arr) [Link](x + " ");
}
}
IV. Conclusion
Sorting is one of the foundational operations in computer science, providing structure and efficiency to data processing.
Each sorting algorithm carries unique characteristics—such as stability, time complexity, and memory usage—that
influence its suitability for specific tasks. Understanding sorting allows students to analyze problem requirements and
select the most efficient algorithm for various applications such as databases, search engines, and data analytics. Mastering
sorting algorithms not only enhances programming skills but also deepens comprehension of computational efficiency and
algorithmic design.
V. References
American Psychological Association. (2020). Publication manual of the American Psychological Association (7th ed.). APA.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to algorithms (4th ed.). MIT Press.
Goodrich, M. T., Tamassia, R., & Goldwasser, M. (2014). Data structures and algorithms in Java (6th ed.). Wiley.
Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.). Addison-Wesley.
Weiss, M. A. (2014). Data structures and algorithm analysis in Java (3rd ed.). Pearson.