What is Bingo Sort?
This Sorting Technique is similar to the Selection Sort in which we first find the smallest element called Bingo Element, and then we repeatedly iterate the elements of the array to get the correct positions of all the elements. Similarly, find the next bingo element for the next pass, and so on. Every distinct element is considered a Bingo Element and called out in increasing order.
Relation between Selection Sort and Bingo Sort
Selection sort does one pass through the remaining items for each item moved. Bingo sort does one pass for each distinct value (not item) and moves every item with that value to its final location
How does Bingo Sort work?
In this sorting technique, each distinct element is considered a Bingo value. And Bingo Values are called out in increasing order. During each pass, if the array element is equal to Bingo element then it is shifted to its correct position.
Follow the below illustration for a better understanding.
Illustration:
Let’s consider the following array as an example: arr[] = [5, 4, 8, 5, 4, 8, 5, 4, 4, 4]
5
4
8
5
4
8
5
4
4
4
Step 1: Find the smallest value which is called a Bingo Element. Smallest element = 4
Step 2: Shift all the elements of the array to their correct position which is equal to the Smallest element by swapping the position of Elements.
- First Pass:
4
5
8
5
4
8
5
4
4
4
- Second Pass
4
4
8
5
5
8
5
4
4
4
- Third Pass:
4
4
4
5
5
8
5
8
4
4
- Fourth Pass:
4
4
4
4
5
8
5
8
5
4
- Fifth Pass:
4
4
4
4
4
8
5
8
5
5
Step 3: Similarly find the next Bingo Element (or smallest element) and shift the elements to their correct position that are equal to Bingo Element. Next Bingo Element = 5
- Sixth pass:
4
4
4
4
4
5
8
8
5
5
- Seventh Pass:
4
4
4
4
4
5
5
8
8
5
- Eighth Pass:
4
4
4
4
4
5
5
5
8
8
Finally, Our array has been arranged in the increasing order as you can see above
Note: You can see that the number of steps that are required to sort the element of Array = number of distinct element -1.
Follow the below steps to solve the problem:
- Find the smallest and the largest element from the array. And smallest element is known as Bingo Element.
- Create a global variable named start position that will keep the track of the element position to be shifted to their correct position.
- Run a while loop until the number of distinct Elements – 1.
- Run a loop inside the while loop that will shift elements of the array to their correct position by checking the equality with bingo Element and find the next Bingo Element.
- Finally Print your Array that has been sorted.
Below is the Implementation of the above approach:
C++
#include <iostream>#include <vector>using namespace std;// Function for finding the maximum and minimum element of// the Arrayvoid maxMin(vector<int> vec, int n, int& bingo, int& nextBingo){ for (int i = 1; i < n; bingo = min(bingo, vec[i]), nextBingo = max(nextBingo, vec[i]), i++) ;}// Function to sort the arrayvoid bingoSort(vector<int>& vec, int n){ int bingo = vec[0]; int nextBingo = vec[0]; maxMin(vec, n, bingo, nextBingo); int largestEle = nextBingo; int nextElePos = 0; while (bingo < nextBingo) { // Will keep the track of the element position to // shifted to their correct position int startPos = nextElePos; for (int i = startPos; i < n; i++) { if (vec[i] == bingo) { swap(vec[i], vec[nextElePos]); nextElePos = nextElePos + 1; } // Here we are finding the next Bingo Element // for the next pass else if (vec[i] < nextBingo) nextBingo = vec[i]; } bingo = nextBingo; nextBingo = largestEle; }}// Function to print the arrayvoid printArray(vector<int> arr, int n){ cout << "Sorted Array: "; for (int i = 0; i < n; i++) { cout << arr[i] << " "; } cout << endl;}// Driver Codeint main(){ vector<int> arr = { 5, 4, 8, 5, 4, 8, 5, 4, 4, 4 }; bingoSort(arr, arr.size()); printArray(arr, arr.size()); vector<int> arr2 = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 }; bingoSort(arr2, arr2.size()); printArray(arr2, arr2.size()); vector<int> arr3 = { 0, 1, 0, 1, 0, 1 }; bingoSort(arr3, arr3.size()); printArray(arr3, arr3.size()); return 0;} |
Java
// Java Code for the above approachimport java.io.*;class GFG { static int bingo; static int nextBingo; // Function for finding the maximum and minimum element // of // the Array static void maxMin(int[] vec, int n) { for (int i = 1; i < n; i++) { bingo = Math.min(bingo, vec[i]); nextBingo = Math.max(nextBingo, vec[i]); } } // Function to sort the array static int[] bingoSort(int[] vec, int n) { bingo = vec[0]; nextBingo = vec[0]; maxMin(vec, n); int largestEle = nextBingo; int nextElePos = 0; while (bingo < nextBingo) { // Will keep the track of the element position // to // shifted to their correct position int startPos = nextElePos; for (int i = startPos; i < n; i++) { if (vec[i] == bingo) { int temp = vec[i]; vec[i] = vec[nextElePos]; vec[nextElePos] = temp; nextElePos = nextElePos + 1; } // Here we are finding the next Bingo // Element for the next pass else if (vec[i] < nextBingo) nextBingo = vec[i]; } bingo = nextBingo; nextBingo = largestEle; } return vec; } // Function to print the array static void printArray(int[] arr, int n) { System.out.print("Sorted Array: "); for (int i = 0; i < n; i++) { System.out.print(arr[i] + " "); } System.out.println(); } public static void main(String[] args) { int[] arr = { 5, 4, 8, 5, 4, 8, 5, 4, 4, 4 }; arr = bingoSort(arr, arr.length); printArray(arr, arr.length); int[] arr2 = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 }; arr2 = bingoSort(arr2, arr2.length); printArray(arr2, arr2.length); int[] arr3 = { 0, 1, 0, 1, 0, 1 }; arr3 = bingoSort(arr3, arr3.length); printArray(arr3, arr3.length); }}// This code is contributed by lokeshmvs21. |
Python3
# Function to print the Arraydef printArray(arr): print("Sorted Array: ",end="") for ele in arr: print(ele, end=" ") print()# function for Sorting the Arraydef bingoSort(arr, size): # Finding the smallest element From the Array bingo = min(arr) # Finding the largest element from the Array largest = max(arr) nextBingo = largest nextPos = 0 while bingo < nextBingo: # Will keep the track of the element position to # shifted to their correct position startPos = nextPos for i in range(startPos, size): if arr[i] == bingo: arr[i], arr[nextPos] = arr[nextPos], arr[i] nextPos += 1 # Here we are finding the next Bingo Element # for the next pass elif arr[i] < nextBingo: nextBingo = arr[i] bingo = nextBingo nextBingo = largest # Printing the ELements of the Sorted Array printArray(arr) arr = [ 5, 4, 8, 5, 4, 8, 5, 4, 4, 4 ]bingoSort(arr, size = len(arr))arr2 = [ 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 ]bingoSort(arr2, size = len(arr2)) arr3 = [ 0, 1, 0, 1, 0, 1 ]bingoSort(arr3, size = len(arr3))# This code is contributed by sdeadityasharma. |
C#
// C# Code for the above approachusing System;public class GFG { static int bingo; static int nextBingo; // Function for finding the maximum and minimum element // of // the Array static void maxMin(int[] vec, int n) { for (int i = 1; i < n; i++) { bingo = Math.Min(bingo, vec[i]); nextBingo = Math.Max(nextBingo, vec[i]); } } // Function to sort the array static int[] bingoSort(int[] vec, int n) { bingo = vec[0]; nextBingo = vec[0]; maxMin(vec, n); int largestEle = nextBingo; int nextElePos = 0; while (bingo < nextBingo) { // Will keep the track of the element position // to // shifted to their correct position int startPos = nextElePos; for (int i = startPos; i < n; i++) { if (vec[i] == bingo) { int temp = vec[i]; vec[i] = vec[nextElePos]; vec[nextElePos] = temp; nextElePos = nextElePos + 1; } // Here we are finding the next Bingo // Element for the next pass else if (vec[i] < nextBingo) nextBingo = vec[i]; } bingo = nextBingo; nextBingo = largestEle; } return vec; } // Function to print the array static void printArray(int[] arr, int n) { Console.Write("Sorted Array: "); for (int i = 0; i < n; i++) { Console.Write(arr[i] + " "); } Console.WriteLine(); } static public void Main() { // Code int[] arr = { 5, 4, 8, 5, 4, 8, 5, 4, 4, 4 }; arr = bingoSort(arr, arr.Length); printArray(arr, arr.Length); int[] arr2 = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 }; arr2 = bingoSort(arr2, arr2.Length); printArray(arr2, arr2.Length); int[] arr3 = { 0, 1, 0, 1, 0, 1 }; arr3 = bingoSort(arr3, arr3.Length); printArray(arr3, arr3.Length); }}// This code is contributed by lokesh. |
Javascript
// JavaScript Code for above approach// Function to sort the arrayfunction bingoSort(vec, n) { let bingo = vec[0]; let nextBingo = vec[0]; // For finding the maximum and minimum element of // the Array for (let i = 1; i < n; bingo = Math.min(bingo, vec[i]), nextBingo = Math.max(nextBingo, vec[i]), i++) ; let largestEle = nextBingo; let nextElePos = 0; while (bingo < nextBingo) { // Will keep the track of the element position to // shifted to their correct position let startPos = nextElePos; for (let i = startPos; i < n; i++) { if (vec[i] == bingo) { [vec[i], vec[nextElePos]] = [vec[nextElePos], vec[i]]; nextElePos = nextElePos + 1; } // Here we are finding the next Bingo Element // for the next pass else if (vec[i] < nextBingo) nextBingo = vec[i]; } bingo = nextBingo; nextBingo = largestEle; } for (let i = 0; i < vec.length; i++) { // console.log("arr: ",vec[i]); }}// Function to print the arrayfunction printArray(arr, n) { console.log("Sorted Array: "); for (let i = 0; i < n; i++) { console.log(arr[i] + " "); } console.log("\n");}// Driver Codelet arr = [5, 4, 8, 5, 4, 8, 5, 4, 4, 4];bingoSort(arr, arr.length);printArray(arr, arr.length);let arr2 = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1];bingoSort(arr2, arr2.length);printArray(arr2, arr2.length);let arr3 = [0, 1, 0, 1, 0, 1];bingoSort(arr3, arr3.length);printArray(arr3, arr3.length);// This code is contributed by ishankhandelwals. |
Sorted Array: 4 4 4 4 4 5 5 5 8 8 Sorted Array: 1 2 3 4 5 6 7 8 9 10 Sorted Array: 0 0 0 1 1 1
Time Complexity:
- Average and Worst Case: O(M * N) where M = number of distinct elements and N = size of the array
- Best Case: O(N + M2 )
Auxiliary Space: O(1)
When to use the Bingo Sort among all Sorting Technique?
You should use the bingo sort if you know that the repetition of every element is large in the array. In that case, you can use this for better time complexity.
Note: It performs better than the quick sort, merge sort and heap sort if the m < log n and performs worst if the distinct element is equal to the number of elements in the Array.
Related Articles:
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
