Chapter 10: Basic Sorting Algorithms

Hello readers! Continuing my Java With DSA series, this is Rohit Gawande here.

In this chapter, we will dive into one of the foundational concepts of programming—sorting. Sorting is an essential technique used to arrange data in a particular order, often in ascending or descending form. Whether working with arrays, lists, or more complex data structures, sorting is crucial for efficiently managing and retrieving information.

Throughout this chapter, we will explore various basic sorting algorithms and understand how they work. We'll start by understanding the definition of sorting and then move on to some of the most common sorting algorithms. For each algorithm, we will provide a clear explanation and the corresponding code implementation. By the end of the chapter, we will also cover an efficient in-built sort function provided by most programming languages. Finally, we'll solve some practice questions to reinforce these concepts.

1. What is Sorting?

Sorting

Whenever we talk about sorting, it refers to arranging data in a specific order—either in increasing (ascending) or decreasing (descending) order. Sorting is widely used in real life, such as when you need to organize items by ticket prices, arrange reviews, or manage a list of products based on ratings. Efficiently sorting data makes searching, organizing, and processing easier.

In this section, we'll focus on basic sorting algorithms that work with simple logic and are easy to implement. These include:

• I) Bubble Sort

• II) Selection Sort

• III) Insertion Sort

• IV) Counting Sort (a more advanced algorithm)

In addition to these, there are more advanced sorting techniques like Merge Sort and Quick Sort, which are based on recursion. We’ll cover those topics in the later parts of this series as they involve more complex algorithms.

Now, let's dive into each of the basic sorting algorithms to understand how they work and how we can implement them in code.

2. Bubble Sort

1) Bubble Sort:

Bubble sort is inspired by how bubbles rise to the top of the water. Imagine you have a bottle of water being heated on a stove—just like bubbles rise from the bottom to the top, larger elements in the array "bubble up" to the end by swapping with adjacent elements.

Idea:

The core idea of bubble sort is to repeatedly compare adjacent elements in an array and swap them if they are in the wrong order. After each pass, the largest unsorted element gets placed in its correct position at the end of the array. With each iteration, the size of the unsorted portion of the array decreases, since the largest element is already at its correct position.

Example:

Let's walk through an example to understand how the bubble sort works:

Array: 5, 4, 1, 3, 2

Step-by-Step Breakdown (0th turn):

• We start with the first element (0th index) and compare it with the adjacent element:

    5 4 1 3 2
    ↓ ↓
    Compare 5 and 4 → Swap because 5 > 4
    Array: 4 5 1 3 2
  

• Now, move to the next pair:

    4 5 1 3 2
      ↓ ↓
    Compare 5 and 1 → Swap because 5 > 1
    Array: 4 1 5 3 2
  

• Continue comparing the next adjacent elements:

    4 1 5 3 2
        ↓ ↓
    Compare 5 and 3 → Swap because 5 > 3
    Array: 4 1 3 5 2
  

• Compare the next pair:

    4 1 3 5 2
          ↓ ↓
    Compare 5 and 2 → Swap because 5 > 2
    Array: 4 1 3 2 5
  

At the end of the 0th turn, the largest element (5) has bubbled up to the end of the array.

Step-by-Step Breakdown (1st turn):

Now, we repeat the process but ignore the last element (which is already sorted). For each subsequent turn, we reduce the number of comparisons since the largest elements are already in place.

• Start with the first pair:

    4 1 3 2 5
    ↓ ↓
    Compare 4 and 1 → Swap because 4 > 1
    Array: 1 4 3 2 5
  

• Continue:

    1 4 3 2 5
      ↓ ↓
    Compare 4 and 3 → Swap because 4 > 3
    Array: 1 3 4 2 5
  

• Compare the next pair:

    1 3 4 2 5
        ↓ ↓
    Compare 4 and 2 → Swap because 4 > 2
    Array: 1 3 2 4 5
  

At the end of the 1st turn, the next largest element (4) is in its correct position.

Process continues for further turns until the array is fully sorted.

Key Observations:

• After every turn, the largest unsorted element is moved to its correct position.

• With each subsequent turn, fewer comparisons are needed since the end of the array is already sorted.

• For an array of size n, bubble sort requires n-1 turns to fully sort the array.

3. Bubble Sort Code

This is the complete Bubble Sort code implementation in Java :

// Large elements come to the end of the array by swapping with adjacent elements
public class BubbleSort {
    // Function to perform Bubble Sort
    public static void BubbleSort(int arr[]) {
        // Outer loop to control the number of passes (turns)
        for (int turn = 0; turn < arr.length - 1; turn++) {
            // Inner loop to compare adjacent elements and swap if needed
            for (int j = 0; j < arr.length - 1 - turn; j++) {
                if (arr[j] > arr[j + 1]) {
                    // Swap arr[j] and arr[j+1]
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    // Function to print the array after sorting
    public static void printArr(int arr[]) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    // Main function to test the Bubble Sort
    public static void main(String[] args) {
        // Example array to be sorted
        int arr[] = {5, 4, 1, 3, 2};

        // Calling Bubble Sort function
        BubbleSort(arr);

        // Printing the sorted array
        printArr(arr);
    }
}

Explanation:

1. Outer Loop (turns):

The outer loop (for (int turn = 0; turn < arr.length - 1; turn++)) controls the number of passes through the array. For an array of size n, we need n - 1 turns (passes) because the last element will already be sorted in place.

2. Inner Loop (swaps):

The inner loop (for (int j = 0; j < arr.length - 1 - turn; j++)) compares adjacent elements (arr[j] and arr[j+1]). If arr[j] is greater than arr[j+1], they are swapped to push the larger element toward the end of the array. This continues until the largest unsorted element reaches its correct position.

As the outer loop progresses, the number of elements to check in each pass decreases because the largest elements have already been sorted to the end of the array.

3. Swap Logic:

int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;

The swap logic exchanges the two adjacent elements if they are out of order (i.e., the left element is larger than the right one).

4. Print Function:

public static void printArr(int arr[])

This function prints the sorted array after the sorting process is complete.

Example Walkthrough:

For the array {5, 4, 1, 3, 2}, let's go through the sorting process step by step:

1. Initial Array: [5, 4, 1, 3, 2]

2. 0th Turn: After the first pass, the largest element (5) is moved to the last position:

   • [4, 1, 3, 2, 5]

3. 1st Turn: After the second pass, the second largest element (4) is in its correct position:

   • [1, 3, 2, 4, 5]

4. 2nd Turn: After the third pass, the third largest element (3) is in place:

   • [1, 2, 3, 4, 5]

5. 3rd Turn: The array is now fully sorted:

   • [1, 2, 3, 4, 5]

Time Complexity:

The time complexity of Bubble Sort is O(n²) because:

• The outer loop runs n - 1 times.

• The inner loop runs approximately n - 1 times on the first pass, n - 2 times on the second pass, and so on.

In the worst case, this results in n(n-1)/2 comparisons, which simplifies to O(n²). This is why Bubble Sort is inefficient for large datasets.

Key Points:

• Bubble Sort is a simple but inefficient sorting algorithm.

• It has a time complexity of O(n²) in the worst and average cases.

• Although it's not the most optimal, it's a great starting point for learning sorting algorithms and understanding basic concepts like element comparison and swapping.

4. Selection Sort

Selection Sort is another simple sorting algorithm that divides the list into two parts: a sorted sublist and an unsorted sublist. The algorithm selects the smallest (or largest) element from the unsorted sublist and swaps it with the first element of the unsorted sublist, thereby growing the sorted sublist.

5. Selection Sort Code

Here’s the Java code for Selection Sort:

public class SelectionSort {
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int minIdx = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIdx]) {
                    minIdx = j;
                }
            }
            // Swap arr[i] and arr[minIdx]
            int temp = arr[minIdx];
            arr[minIdx] = arr[i];
            arr[i] = temp;
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 25, 12, 22, 11};
        selectionSort(arr);
        System.out.println("Sorted array: ");
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

6. Insertion Sort

Insertion Sort works similarly to how we sort playing cards in our hands. It builds the sorted array one element at a time by repeatedly picking the next element from the unsorted sublist and inserting it into the correct position in the sorted sublist.

7. Insertion Sort Code

Here’s the Java code for Insertion Sort:

public class InsertionSort {
    public static void insertionSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 25, 12, 22, 11};
        insertionSort(arr);
        System.out.println("Sorted array: ");
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

8. Inbuilt Sort (Using Arrays.sort)

Java provides an inbuilt method to sort arrays efficiently. The Arrays.sort() method is based on the Timsort algorithm, which is a hybrid of Merge Sort and Insertion Sort.

Here’s how you can use the inbuilt sort:

import java.util.Arrays;

public class InbuiltSort {
    public static void main(String[] args) {
        int[] arr = {64, 25, 12, 22, 11};
        Arrays.sort(arr);
        System.out.println("Sorted array using inbuilt sort: ");
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

9. Counting Sort

Counting Sort is a non-comparison-based sorting algorithm. It works by counting the number of occurrences of each element in the array and then using this count to place elements in their correct position.

10. Counting Sort Code

Here’s the Java code for Counting Sort:

import java.util.Arrays;

public class CountingSort {
    public static void countingSort(int[] arr, int max) {
        int[] count = new int[max + 1];
        int[] output = new int[arr.length];

        // Store the count of each element
        for (int i = 0; i < arr.length; i++) {
            count[arr[i]]++;
        }

        // Change count[i] so that it contains the actual position of the element in the output array
        for (int i = 1; i <= max; i++) {
            count[i] += count[i - 1];
        }

        // Build the output array
        for (int i = arr.length - 1; i >= 0; i--) {
            output[count[arr[i]] - 1] = arr[i];
            count[arr[i]]--;
        }

        // Copy the sorted elements back to the original array
        for (int i = 0; i < arr.length; i++) {
            arr[i] = output[i];
        }
    }

    public static void main(String[] args) {
        int[] arr = {4, 2, 2, 8, 3, 3, 1};
        int max = Arrays.stream(arr).max().getAsInt();
        countingSort(arr, max);
        System.out.println("Sorted array: ");
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

---

Assignments:

1. Bubble Sort: Modify the above code to optimize it by stopping early if the array is already sorted in a pass.

2. Selection Sort: Write a version of Selection Sort that finds the maximum element and swaps it to the end.

3. Insertion Sort: Modify the Insertion Sort to sort in descending order.

4. Counting Sort: Write a function that sorts a large array of non-negative integers using Counting Sort.

---

That's it for this chapter! I hope these explanations and codes helped you grasp the basics of sorting algorithms. Stay tuned for the next chapters, where we will explore more advanced sorting techniques and dive deeper into algorithm optimization.

---

Related Posts in My Series:

DSA in Java Series:

• Chapter 2: Operators in Java – Learn about the different types of operators in Java, including arithmetic, relational, logical, and assignment operators, along with examples to understand their usage.

• Chapter 33: Trie in Java – Explore the implementation and use of Trie data structure in Java, a powerful tool for handling strings, with practical coding examples.

Other Series:

• Full Stack Java Development – Master the essentials of Java programming and web development with this series. Topics include object-oriented programming, design patterns, database interaction, and more.

• Full Stack JavaScript Development – Become proficient in JavaScript with this series covering everything from front-end to back-end development, including frameworks like React and Node.js.

---

Connect with Me
Stay updated with my latest posts and projects by following me on social media:

• LinkedIn: Connect with me for professional updates and insights.

• GitHub: Explore my repositories and contributions to various projects.

• LeetCode: Check out my coding practice and challenges.

Your feedback and engagement are invaluable. Feel free to reach out with questions, comments, or suggestions. Happy coding!

Rohit Gawande
Full Stack Java Developer | Blogger | Coding Enthusiast