Stooge sort is an algorithm based on recursion that applies the divide and conquer strategy. Despite being less popular compared to sorting methods such as quicksort or merge sort, Stooge sort offers a straightforward implementation, which can be valuable for illustrating recursive sorting strategies. The algorithm was introduced by Steve Abbott in 1975 and earned its name due to its perceived inefficiency.
The approach operates by iteratively splitting the array into smaller subarrays for sorting, utilizing recursion, and subsequently merging the resulting arrays. The strategy involves comparing two elements by evaluating their positions relative to each other and exchanging them if they are incorrectly placed. This way, Stooge sort diverges from the conventional method by initially sorting the array into the initial and final two-thirds, followed by further sorting iterations involving the initial two-thirds. Through this iterative process, the elements are arranged in the correct sequence.
The computational complexity of the Stooge sort algorithm is represented by O(n^(log3 / log1.5)) ≈ O(n^2.7095), indicating a time complexity of around O(n^2.7095). Despite being O(n^2), its efficiency is lower compared to quick sort and merge sort, which have complexities of O(n log n) and O(n^2) respectively.
A distinctive feature of the Stooge sort method is its notable inefficiency when handling extensive datasets. Due to its recursive nature, the algorithm needs to compare elements in a predetermined sequence, causing a significant slowdown when processing arrays with numerous elements. Additionally, Static Sorts lack stability, potentially disrupting the original order of elements within the array.
While the Stooge sort may not be the most efficient option, it stands out due to its recursive approach and distinct sorting technique. While it may not be ideal for sorting extensive datasets in a production environment, it adds value to the array of sorting algorithms due to its straightforward nature.
Approach-1: Using vectors.
Implementing Stooge Sort using the std::vector structure in C++ allows for a reliable way to achieve sorting. This method utilizes the dynamic array features of the std::vector container sourced from the C++ STL library. The std::vector container adjusts its size dynamically and offers efficient indexing, making it a suitable choice for efficient sorting operations.
Program:
#include <iostream>
#include <vector>
using namespace std;
// Function to swap two elements
void swap(int& a, int& b) {
int temp = a;
a = b;
b = temp;
}
// Function to perform Stooge Sort
void stoogeSort(vector<int>& arr, int low, int high) {
if (low >= high)
return;
// If the first element is greater than the last, swap them
if (arr[low] > arr[high])
swap(arr[low], arr[high]);
// If there are more than 2 elements in the array
if (high - low + 1 > 2) {
int t = (high - low + 1) / 3; // Calculate a third of the array size
// Recursively sort the first two-thirds of the array
stoogeSort(arr, low, high - t);
// Recursively sort the last two-thirds of the array
stoogeSort(arr, low + t, high);
// Recursively sort the first two-thirds again
stoogeSort(arr, low, high - t);
}
}
// Function to print the elements of a vector
void printVector(const vector<int>& arr) {
for (int num : arr)
cout << num << " ";
cout << endl;
}
int main() {
vector<int> arr = {5, 8, 2, 6, 1, 9, 3, 7, 4};
cout << "Original vector: ";
printVector(arr);
// Call Stooge sort function
stoogeSort(arr, 0, arr.size() - 1);
cout << "Sorted vector: ";
printVector(arr);
return 0;
}
Output:
Original vector: 5 8 2 6 1 9 3 7 4
Sorted vector: 1 2 3 4 5 6 7 8 9
Explanation:
Header Files and Namespace:
The code imports the <iostream> and <vector> header files to facilitate input and output tasks and to work with the std::vector data structure. The std namespace serves as a mechanism to access functions and classes from the standard library.
Swap Function:
The function swaps two integers through reference variables. It acts as a placeholder for elements when they are being rearranged within a vector during sorting.
Stooge Sort Function:
The StoogeSort function executes the StoogeSort algorithm, accepting three arguments: arr (the array to be sorted), low, and high which indicate the range of elements to be sorted. The termination condition is when low>= high, indicating either a single element remains in the subvector or the elements are already sorted in ascending order. The function checks if the first and last elements in the subvector are in descending order and swaps them if necessary.
When the size of the subvector exceeds 2, the algorithm calculates a variable t that occupies one-third of the subvector's size. The algorithm iterates recursively to rearrange the largest elements to their correct positions by splitting the subvector into the initial two-thirds and the final two-thirds, and then performing individual sorting operations on each subvector.
Finally, it executes a rapid sorting algorithm on the initial two-thirds of the sub-array to further enhance the order of elements.
Print Vector Function:
The printVector function accepts a constant reference to an array and displays each element within the vector.
Main Function:
In the primary function, a vector named arr is initialized with specific values. The initial vector is displayed using the printVector function. The stoogesSort function is then employed to arrange the vector utilizing the Stooge Sort algorithm. Finally, the sorted vector is displayed in position by calling the printVector function.
Complexity Analysis:
Time Complexity:
Stooge Sort exhibits a greater time complexity compared to Quicksort and Mergesort, which offer superior time efficiency despite sacrificing sorting speed. Stooge Sort operates with a time complexity of O(n(log 3) / (log 1.5)), roughly equivalent to O(n^2.7095). Consequently, as the size of the array grows, Stooge Sort will require progressively more time to process. Therefore, Stooge Sort is less practical for sorting large datasets that demand faster processing speeds.
Space Complexity:
The space usage of the Stooge Sort algorithm remains at O(1) when executing in-place sorting. This is due to its direct manipulation of the input array without utilizing additional data structures. However, if the stack consumes space for recursive calls or other purposes, the space complexity may escalate. Overall, Stooge Sort typically maintains a minimal space complexity in comparison to its time complexity, making it a memory-efficient albeit time-consuming process.
Approach-2: Using Linked lists.
Program:
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
Node(int val) : data(val), next(nullptr) {}
};
// Function to merge two sorted linked lists
Node* merge(Node* l1, Node* l2) {
if (l1 == nullptr)
return l2;
if (l2 == nullptr)
return l1;
if (l1->data < l2->data) {
l1->next = merge(l1->next, l2);
return l1;
} else {
l2->next = merge(l1, l2->next);
return l2;
}
}
// Function to perform Stooge sort on a linked list
Node* stoogeSortLinkedList(Node* head) {
if (head == nullptr || head->next == nullptr)
return head;
Node* slow = head;
Node* fast = head;
Node* prev = nullptr;
while (fast != nullptr && fast->next != nullptr) {
prev = slow;
slow = slow->next;
fast = fast->next->next;
}
Node* mid = slow;
prev->next = nullptr;
head = stoogeSortLinkedList(head);
mid = stoogeSortLinkedList(mid);
return merge(head, mid);
}
// Function to print the elements of a linked list
void printLinkedList(Node* head) {
while (head != nullptr) {
cout << head->data << " ";
head = head->next;
}
cout << endl;
}
int main() {
// Create a linked list
Node* head = new Node(5);
head->next = new Node(3);
head->next->next = new Node(7);
head->next->next->next = new Node(1);
head->next->next->next->next = new Node(9);
cout << "Original linked list: ";
printLinkedList(head);
// Perform Stooge sort on the linked list
head = stoogeSortLinkedList(head);
cout << "Sorted linked list: ";
printLinkedList(head);
return 0;
}
Output:
Original linked list: 5 3 7 1 9
Sorted linked list: 1 3 5 7 9
Explanation:
Structure of Node:
The SinglyLinkedListstruct is made up of a Node struct, representing a single node in a singly linked list. It includes an integer data field to store the node's value and the nextNode pointer, which indicates the succeeding element in the linked list. The constructor method initializes the node with the provided value and assigns "nextNode = nullptr" to signify the end of the list.
Merge Function:
The merge operation merges two pre-sorted linked lists into a single linked list in ascending order. During the merging process, the pointers to the head of the merged lists, referred to as l1 and l2, are utilized. If either of the input lists points to a nullptr, the function simply returns the other list, as it is already sorted.
The function compares the data elements of the head nodes to determine how the remaining lists should be merged while maintaining the original order.
Stooge Sort Function for Linked List:
The stoogeSortLinkedList function receives a list as an argument and arranges it utilizing the Stooge Sort algorithm. This involves dividing the list into multiple sublists, sorting each sublist, and then merging them back together.
The method employed involves testing, achieved through the utilization of a slow pointer and a fascpp tutorialer to determine the midpoint. This process typically involves dividing the list into two equal parts, which are subsequently organized by the stoogeSortLinkedList function. Following the joining of these two divided arrays, the merger function combines them using the merge operation to obtain the final sorted array.
Print Function:
Printing the linked list involves iterating through the list starting from the head node and displaying the data of each node sequentially. It includes validation checks both before and after the sorting process within the list.
Main Function:
Within the primary function, a linked list reference is established, containing an initial set of elements. The 'printLinkedList' method is then employed to display the original linked list. Following this, the 'stoogeSortLinkedList' function arranges the linked list utilizing the Stooge Sort algorithm. Subsequently, the printLinkedList function is invoked once more to exhibit the sorted linked list.
Complexity Analysis:
Time Complexity:
Stooge Sort for Linked List:
A crucial factor to take into account for the Stooge Sort algorithm when applied to linked lists is the level of recursion and the intricacy of the merging operation. In the most unfavorable scenario, the list undergoes recursive division into halves until each individual node is isolated. Consequently, the recursion depth is O(log n), with 'n' denoting the quantity of nodes within the linked list.
Additionally, with each merge request, the time complexity deteriorates linearly at O(n), where n represents the collective number of nodes being merged. Consequently, the overall complexity of Stooge Sort for a linked list is ultimately O(n log n), with n denoting the quantity of nodes within the linked list.
Merge Function:
The merge function operates on two sorted linked lists with sizes m and n, representing the lengths of the lists. It traverses both lists once, conducting comparison operations to merge them, resulting in a time complexity of O(m + n). Since the lengths of the lists being merged can vary, the merge function may exhibit variable time complexity based on the input length.
Space Complexity:
The space efficiency of this code is primarily determined by the memory required to store the elements within the linked list and the memory allocated for recursive function invocations. The space complexity of the linked list is O(n), where 'n' represents the total number of nodes present in the list.
Furthermore, within the stoogeSortLinkedList function, the recursive calls consume stack space that scales with the recursion depth (O(log n) in the worst-case scenario).
So, the overall spatial efficiency mentioned earlier is in the form of O(n + log n) where n represents the quantity of nodes in the linked list and log n signifies the recursive depth of the stoogeSortLinkedList function.
Approach-3: Recursive Function with Swapping
A "Recursive function with swapping" refers to the implementation of the Swap Sort algorithm using a recursive function that handles both sorting the array elements and performing swap operations to adjust the elements as needed.
Program:
#include <iostream>
using namespace std;
void swap(int& a, int& b) {
int temp = a;
a = b;
b = temp;
}
void stoogeSort(int arr[], int low, int high) {
if (low >= high)
return;
if (arr[low] > arr[high])
swap(arr[low], arr[high]);
if (high - low + 1 > 2) {
int t = (high - low + 1) / 3;
stoogeSort(arr, low, high - t);
stoogeSort(arr, low + t, high);
stoogeSort(arr, low, high - t);
}
}
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
int main() {
int arr[] = {5, 8, 2, 6, 1, 3, 7, 4};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Original array: ";
printArray(arr, n);
stoogeSort(arr, 0, n - 1);
cout << "Sorted array: ";
printArray(arr, n);
return 0;
}
Output:
Original array: 5 8 2 6 1 3 7 4
Sorted array: 1 2 3 4 5 6 7 8
Explanation:
Header Files and Namespace:
The program directive in this header file enables input and output functionalities, while the std namespace is utilized for standard library operations.
Swap Function:
Function swap takes in two integer pointers as parameters to swap their values. This operation is commonly used to maintain the sorting of an array based on the values, whether in ascending or descending order.
Stooge Sort Function:
The stoogeSort function executes the Stooge Sort algorithm, which is tailored for handling extensive datasets. It requires three parameters: a pointer pointing to arr, along with low and high as arguments to specify a range of elements. The base case scenario occurs when high is equal to or less than the base case value, which represents subarrays with either zero or one element that are already in sorted order.
A technique for arranging an array of numbers in their inherent order is known as quick sort. This method relies on selecting a pivot element using the partition method, then evaluating if the first and last elements of the subarray need to be exchanged. If necessary, the elements are swapped accordingly.
When the size of the subarray exceeds 2, a new variable t is introduced to represent one-third of the subarray's length.
The recursion occurs as the function recursively invokes itself to sort the initial two-thirds and final two-thirds of the subarray independently, ensuring the correct placement of the largest elements. Additionally, it iterates through the first two-thirds of the subarray once more to refine the sorting process for greater precision.
Print Array Function:
The printArray function is defined with the array arr and its length as input parameters. Its main objective is to showcase all elements contained within the array.
Main Function:
Inside the main function, a integer array named arr is populated with multiple values. The size of the array, denoted by n, is calculated by multiplying the sizeof operator with the size of a single element and then dividing it by the total number of elements in the array. The printArray function is then used to display all the numbers stored in the original array on the screen.
The stoogeSort function is called to arrange the array using the Stooge Sorting algorithm. Subsequently, the printArray function is utilized to showcase the resulting array.
Complexity Analysis:
Time Complexity:
This is due to the fact that Stooge Sort's performance is primarily influenced by the quantity of comparisons and exchanges it performs during the sorting operation. In each invocation of the stoogesort function, the algorithm conducts a pair of comparisons to evaluate the arrangement of the first and last elements within the subset. Following this, the algorithm initiates two additional recursive calls to sort the initial two-thirds and the last two-thirds segments of the array individually.
Consequently, the time complexity of Stooge Sort can be described through the subsequent recurrence relation:
The time complexity function t(n) is defined as t(n) = 3T(2n/3) + O(1), where n represents the size of the array.
The following equation yields a time complexity of O(n^(log 3 / log 1.5)), which may reach up to O(n^2.7095) in the most unfavorable scenario.
Consequently, Stooge Sort demonstrates a relatively high time complexity when contrasted with sorting algorithms such as Quicksort or Mergesort, which boast lower time complexity metrics.
Space Complexity:
The space efficiency of the Stooge Sort algorithm primarily depends on the recursive invocations during the sorting procedure and the extra memory allocated for variable storage and the stooge call stack.
We view the space needed for recursive calls as O(log n) due to the worst-case recursion depth being O(log n). Additionally, no additional space is necessary for data structures or auxiliary arrays since the input array is sorted in-place.
Therefore, the space efficiency of Stooge Sort algorithm is in O(log n) when n represents the array's size.
