Decision-Tree Model in Sorting Algorithms

In the context of sorting algorithms, a decision tree is a full binary tree where each internal node represents a comparison between elements, and each leaf node represents a unique permutation of the input elements. The decision tree models the sequence of comparisons made by the sorting algorithm for a given input size. This tree can be used to analyze the efficiency and behavior of the algorithm.

Let’s take the example of a simple sorting algorithm, like Bubble Sort, and see how a decision tree might look for a list of 3 elements [a, b, c].

Java

Here’s a Java example that mimics the decision tree for Bubble Sort on an array of 3 elements.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class DecisionTreeBubbleSort {
    static void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    // swap
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {3, 1, 2};
        bubbleSort(arr);
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

C++

The C++ example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
using namespace std;

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // swap
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

int main() {
    int arr[] = {3, 1, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    bubbleSort(arr, n);
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

Python

Python example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                # swap
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

arr = [3, 1, 2]
bubble_sort(arr)
print(arr)

In each of these implementations, the nested loop structure is what decides the order of element comparisons, effectively making the decisions a full binary tree would. Each comparison if (arr[j] > arr[j + 1]) could be seen as an internal node in the decision tree, directing the sorting algorithm along different paths depending on the outcome of the comparison.