C Program to Implement Stooge Sort Algorithm

This C program sorts a given array of integer numbers using Stooge Sort technique.
Stooge sort is a recursive sorting algorithm with a time complexity of O(nlog 3 / log 1.5). The running time of the algorithm is thus extremely slow compared to efficient sorting algorithms, such as Merge sort, and is even slower than Bubble sort, a canonical example of a fairly inefficient and simple sort.

Here is the source code of the C program to sort integers using Stooge Sort technique. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /*
  2.  * C Program to Perform Stooge Sort
  3.  */
  4. #include <stdio.h>
  5. void stoogesort(int [], int, int);
  6.  
  7. void main()
  8. {
  9.     int arr[100], i, n;
  10.  
  11.     printf("How many elements do you want to sort: ");
  12.     scanf("%d", &n);
  13.     for (i = 0;i < n; i++)
  14.         scanf(" %d", &arr[i]);
  15.     stoogesort(arr, 0, n - 1);
  16.     printf("Sorted array : \n");
  17.     for (i = 0;i < n;i++)
  18.     {
  19.         printf("%d ", arr[i]);
  20.     }
  21.     printf("\n");
  22. }
  23.  
  24.  
  25. void stoogesort(int arr[], int i, int j)
  26. {
  27.     int temp, k;
  28.     if (arr[i] > arr[j])
  29.     {
  30.         temp = arr[i];
  31.         arr[i] = arr[j];
  32.         arr[j] = temp;
  33.     }
  34.     if ((i + 1) >= j)
  35.         return;
  36.     k = (int)((j - i + 1) / 3);
  37.     stoogesort(arr, i, j - k);
  38.     stoogesort(arr, i + k, j);
  39.     stoogesort(arr, i, j - k);
  40. }

$ gcc stoogesort.c -o stoogesort
$ ./stoogesort
 
How many numbers you want to sort: 5
 
Enter 5 numbers : 755 32 20 35 333
 
Sorted array is : 20 32 35 333 755

Sanfoundry Global Education & Learning Series – 1000 C Programs.

advertisement
advertisement

Here’s the list of Best Books in C Programming, Data Structures and Algorithms.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.