This code demonstrates an implementation of the **randomized quicksort algorithm**,...

This code demonstrates an implementation of the randomized quicksort algorithm, which uses a pseudo-random number generator (instead of the standard <cstdlib> or <ctime> libraries) to select the pivot for partitioning the array. Here's a breakdown of the code:

1. swap function:

• A helper function that swaps the values of two integer variables by using pass-by-reference.

void swap(int &a, int &b) {
    int temp = a;
    a = b;
    b = temp;
}

2. pseudo_random function:

• Implements a very basic linear congruential generator (LCG) to generate pseudo-random numbers.
• Given a seed, it computes the next pseudo-random number using the formula:

  seed = (seed * 1103515245 + 12345) & 0x7fffffff;
  

• The & 0x7fffffff ensures the generated value is non-negative (within the 31-bit range).

int pseudo_random(int seed) {
    return (seed * 1103515245 + 12345) & 0x7fffffff;
}

3. partition function:

• Implements the Lomuto Partition Scheme for quicksort.
• Rearranges the sub-array arr[low..high] such that:
  • Elements smaller than the pivot are moved to the left.
  • Elements larger than or equal to the pivot are moved to the right.
• Returns the final index of the pivot (i + 1), dividing the array for further recursion.

int partition(int arr[], int low, int high, int pivotIndex) {
    swap(arr[pivotIndex], arr[high]);  // Move pivot element to the end
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);  // Place pivot in its correct position
    return i + 1;  // Return the pivot index
}

4. randomized_quick_sort function:

• Implements the randomized version of the quicksort algorithm.
• Recursively sorts the elements in the array arr[low..high]:
  1. A random pivot index is generated using the pseudo_random function.
  2. Calls partition to rearrange the sub-array based on the pivot element.
  3. Recursively sorts the left and right partitions:
  • Left: arr[low..pi - 1]
  • Right: arr[pi + 1..high]

void randomized_quick_sort(int arr[], int low, int high, int &seed) {
    if (low < high) {
        // Generate a "random" pivot index
        seed = pseudo_random(seed);
        int pivotIndex = low + (seed % (high - low + 1));

        int pi = partition(arr, low, high, pivotIndex);

        // Recursively sort the partitions
        randomized_quick_sort(arr, low, pi - 1, seed);
        randomized_quick_sort(arr, pi + 1, high, seed);
    }
}

5. main function:

• The entry point of the program.
• An example array arr[] is defined and initialized.
• A starting pseudo-random seed value is set (int seed = 12345).
• Calls randomized_quick_sort to sort the array.
• Prints the sorted array.

int main() {
    int arr[] = {3, 6, 8, 10, 1, 2, 1};  // Input array
    int n = sizeof(arr) / sizeof(arr[0]);  // Calculate size of array

    int seed = 12345;  // Initial seed for pseudo-random generator
    randomized_quick_sort(arr, 0, n - 1, seed);  // Sort the array

    // Print the sorted array
    cout << "Sorted array: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

What the Code Does:

1. Generates a random pivot index using a simple pseudo-random number generator (pseudo_random) with an initial seed.
2. Partitions and recursively sorts the array using the randomized quicksort algorithm.
3. Prints the sorted array after sorting is complete.

Input Example:

Input array: {3, 6, 8, 10, 1, 2, 1}

Output Example:

Output after sorting: 1 1 2 3 6 8 10