इस ट्यूटोरियल में, आप सीखेंगे कि बबल सॉर्ट कैसे काम करता है। इसके अलावा, आपको C, C ++, Java और पायथन में बबल सॉर्ट के काम करने के उदाहरण मिलेंगे।
बबल सॉर्ट एक एल्गोरिथ्म है जो आसन्न तत्वों की तुलना करता है और यदि वे इच्छित क्रम में नहीं हैं, तो अपनी स्थिति को स्वैप करते हैं। आदेश आरोही या अवरोही हो सकता है।
बुलबुला कैसे काम करता है?
- पहले सूचकांक से शुरू करके, पहले और दूसरे तत्वों की तुलना करें। यदि पहला तत्व दूसरे तत्व से अधिक है, तो उन्हें स्वैप किया जाता है।
अब, दूसरे और तीसरे तत्वों की तुलना करें। यदि वे क्रम में नहीं हैं तो उन्हें स्वैप करें।
उपरोक्त प्रक्रिया अंतिम तत्व तक चलती है।
आसन्न तत्वों की तुलना करें - शेष पुनरावृत्तियों के लिए भी यही प्रक्रिया चलती है। प्रत्येक पुनरावृत्ति के बाद, अंत में अनसोल्ड तत्वों में से सबसे बड़ा तत्व रखा जाता है।
प्रत्येक पुनरावृत्ति में, तुलना अंतिम अनसोल्ड तत्व तक होती है।
सरणी को तब सॉर्ट किया जाता है जब सभी अनसोल्ड तत्वों को उनके सही स्थान पर रखा जाता है।
आसन्न तत्वों की 
तुलना आसन्न तत्वों की 
तुलना आसन्न तत्वों की तुलना करें
बबल सॉर्ट एल्गोरिथम
मैं सही के लिए बबलसोर्ट (सरणी) बायीं ओर स्वैप करें और राईट क्लीयर बबल्ट के लिए बचे
पायथन, जावा और सी / सी ++ उदाहरण
पायथन जावा सी सी ++ # Bubble sort in Python def bubbleSort(array): # run loops two times: one for walking throught the array # and the other for comparison for i in range(len(array)): for j in range(0, len(array) - i - 1): # To sort in descending order, change> to array(j + 1): # swap if greater is at the rear position (array(j), array(j + 1)) = (array(j + 1), array(j)) data = (-2, 45, 0, 11, -9) bubbleSort(data) print('Sorted Array in Asc ending Order:') print(data)
// Bubble sort in Java import java.util.Arrays; class BubbleSort ( void bubbleSort(int array()) ( int size = array.length; // run loops two times: one for walking throught the array // and the other for comparison for (int i = 0; i < size - 1; i++) for (int j = 0; j to array(j + 1)) ( // swap if greater is at the rear position int temp = array(j); array(j) = array(j + 1); array(j + 1) = temp; ) ) // driver code public static void main(String args()) ( int() data = ( -2, 45, 0, 11, -9 ); BubbleSort bs = new BubbleSort(); bs.bubbleSort(data); System.out.println("Sorted Array in Ascending Order:"); System.out.println(Arrays.toString(data)); ) )
// Bubble sort in C #include void bubbleSort(int array(), int size) ( // run loops two times: one for walking throught the array // and the other for comparison for (int step = 0; step < size - 1; ++step) ( for (int i = 0; i " to " array(i + 1)) ( // swap if greater is at the rear position int temp = array(i); array(i) = array(i + 1); array(i + 1) = temp; ) ) ) ) // function to print the array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", array(i)); ) printf(""); ) // driver code int main() ( int data() = (-2, 45, 0, 11, -9); int size = sizeof(data) / sizeof(data(0)); bubbleSort(data, size); printf("Sorted Array in Ascending Order:"); printArray(data, size); )
// Bubble sort in C++ #include using namespace std; void bubbleSort(int array(), int size) ( // run loops two times: one for walking throught the array // and the other for comparison for (int step = 0; step < size - 1; ++step) ( for (int i = 0; i to array(i + 1)) ( // swap if greater is at the rear position int temp = array(i); array(i) = array(i + 1); array(i + 1) = temp; ) ) ) ) // function to print the array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( cout << " " << array(i); ) cout << ""; ) // driver code int main() ( int data() = (-2, 45, 0, 11, -9); int size = sizeof(data) / sizeof(data(0)); bubbleSort(data, size); cout << "Sorted Array in Ascending Order:"; printArray(data, size); )
अनुकूलित बबल सॉर्ट
उपरोक्त कोड में, सभी संभव तुलनाएँ की जाती हैं, भले ही सरणी पहले से ही सॉर्ट की गई हो। यह निष्पादन के समय को बढ़ाता है।
अतिरिक्त वैरिएबल स्वैप की शुरुआत करके कोड को अनुकूलित किया जा सकता है। प्रत्येक पुनरावृत्ति के बाद, यदि कोई स्वैपिंग नहीं हो रही है, तो आगे लूप प्रदर्शन करने की कोई आवश्यकता नहीं है।
ऐसे मामले में, वेरिएबल स्वैप किया गया झूठा सेट किया जाता है। इस प्रकार, हम और पुनरावृत्तियों को रोक सकते हैं।
अनुकूलित बबल सॉर्ट के लिए एल्गोरिदम है
बुलबुलाशर्त (सरणी) अदला - बदली
अनुकूलित बबल सॉर्ट उदाहरण
पायथन जावा सी सी + # Optimized bubble sort in python def bubbleSort(array): # Run loops two times: one for walking throught the array # and the other for comparison for i in range(len(array)): # swapped keeps track of swapping swapped = True for j in range(0, len(array) - i - 1): # To sort in descending order, change> to array(j + 1): # Swap if greater is at the rear position (array(j), array(j + 1)) = (array(j + 1), array(j)) swapped = False # If there is not swapping in the last swap, then the array is already sorted. if swapped: break data = (-2, 45, 0, 11, -9) bubbleSort(data) print('Sorted Array in Ascending Order:') print(data)
// Optimized bubble sort in Java import java.util.Arrays; class BubbleSort ( void bubbleSort(int array()) ( int size = array.length; // Run loops two times: one for walking throught the array // and the other for comparison for (int i = 0; i < size - 1; i++) ( // swapped keeps track of swapping boolean swapped = true; for (int j = 0; j to array(j + 1)) ( // Swap if greater is at the rear position int temp = array(j); array(j) = array(j + 1); array(j + 1) = temp; swapped = false; ) ) // If there is not swapping in the last swap, then the array is already sorted. if (swapped == true) break; ) ) // Driver code public static void main(String args()) ( int() data = ( -2, 45, 0, 11, -9 ); BubbleSort bs = new BubbleSort(); bs.bubbleSort(data); System.out.println("Sorted Array in Ascending Order:"); System.out.println(Arrays.toString(data)); ) )
// Optimized bubble sort in C #include void bubbleSort(int arrayay(), int size) ( for (int step = 0; step < size - 1; ++step) ( // Swapped keeps track of swapping int swapped = 0; // Run loops two times: one for walking throught the array // and the other for comparison for (int i = 0; i to arrayay(i + 1)) ( // Swap if greater is at the rear position int temp = arrayay(i); arrayay(i) = arrayay(i + 1); arrayay(i + 1) = temp; swapped = 1; ) ) // If there is not swapping in the last swap, then the array is already sorted. if (swapped == 0) break; ) ) // Function to print an array void printarrayay(int arrayay(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", arrayay(i)); ) printf(""); ) // Driver code int main() ( int data() = (-2, 45, 0, 11, -9); int size = sizeof(data) / sizeof(data(0)); bubbleSort(data, size); printf("Sorted Array in Ascending Order:"); printarrayay(data, size); )
// Optimized bubble sort in C++ #include using namespace std; void bubbleSort(int array(), int size) ( for (int step = 0; step < size - 1; ++step) (
// Run loops two times: one for walking throught the array // and the other for comparison int swapped = 0; for (int i = 0; i to array(i + 1)) ( // Swap if greater is at the rear position int temp = array(i); array(i) = array(i + 1); array(i + 1) = temp; swapped = 1; ) ) // If there is not swapping in the last swap, then the array is already sorted. if (swapped == 0) break; ) ) // Function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( cout << " " << array(i); ) cout << ""; ) // Driver code int main() ( int data() = (-2, 45, 0, 11, -9); int size = sizeof(data) / sizeof(data(0)); bubbleSort(data, size); cout << "Sorted Array in Ascending Order:"; printArray(data, size); )
जटिलता
बबल सॉर्ट सबसे सरल सॉर्टिंग एल्गोरिदम में से एक है। एल्गोरिथ्म में दो छोरों को लागू किया गया है।
| चक्र | तुलना की संख्या |
|---|---|
| पहली बार | (एन -1) |
| 2 रा | (एन -2) |
| ३ | (एन -3) |
| …। | … |
| अंतिम | 1 है |
तुलना की संख्या: (n - 1) + (n - 2) + (n - 3) +… + 1 = n (n - 1) / 2 लगभग बराबर n 2
जटिलता: O (n 2 )
इसके अलावा, हम केवल छोरों की संख्या को देखकर जटिलता का विश्लेषण कर सकते हैं। 2 छोरें हैं इसलिए जटिलता हैn*n = n2
समय जटिलताएं:
-
सबसे खराब स्थिति जटिलता: यदि हम बढ़ते क्रम में क्रमबद्ध करना चाहते हैं और सरणी अवरोही क्रम में है, तो सबसे खराब स्थिति होती है।
O(n2) -
बेस्ट केस कॉम्प्लेक्सिटी:
O(n)
अगर एरे को पहले ही सॉर्ट कर लिया जाए, तो सॉर्ट करने की कोई जरूरत नहीं है। -
औसत केस जटिलता: यह तब होता है जब सरणी के तत्व जंबल्ड ऑर्डर में होते हैं (न तो आरोही और न ही अवरोही)।
O(n2)
अंतरिक्ष जटिलता:
अंतरिक्ष जटिलता O(1)इसलिए है क्योंकि स्वैप करने के लिए एक अतिरिक्त चर अस्थायी का उपयोग किया जाता है।
अनुकूलित एल्गोरिथ्म में, वैरिएबल स्वैप को अंतरिक्ष जटिलता में जोड़ता है, इस प्रकार O(2)।
बुलबुला क्रमबद्ध अनुप्रयोग
बबल सॉर्ट का उपयोग निम्नलिखित मामलों में किया जाता है जहां
- कोड की जटिलता कोई मायने नहीं रखती।
- एक छोटा कोड पसंद किया जाता है।
