निर्दिष्ट करें कि कथन कब किया जाएगा [बबल सॉर्ट एल्गोरिदम] - एल्गोरिदम, सॉर्टिंग

1. for i=1 to n-1 do
2.    for j=1 to n-i do
3.       if a[j]>A[j+1] then
4.          Change A[j] with A[j+1]

बताएं कि तीसरी पंक्ति में कितनी बार निर्देश (द if कथन) किया जाएगा।

मुझे लगता है कि संशोधन के बिना यह पहला, प्राथमिक बबल सॉर्ट एल्गोरिदम है।
सबसे पहले मैं तीन मामलों पर विचार करूंगा: सर्वोत्तम, औसत और सबसे खराब।

में सबसे अच्छा अगर स्टेटमेंट एन-1 बार किया जाएगा। सरणी में डेटा पहले से ही अलग हो जाएगा। यह सरणी और अंत एल्गोरिदम के माध्यम से चलने के लिए पर्याप्त है।

में सबसे खराब अगर मामला पूरा किया जाएगा:

<a href="http://www.codecogs.com/eqnedit.php?latex=sum_{i=1}^{n-1}tfrac{n(n-1)}{2}" target="_blank"><img src="/images/http://latex.codecogs.com/gif.latex?sum_{i=1}^{n-1}tfrac{n(n-1)}{2}" title="sum_{i=1}^{n-1}tfrac{n(n-1)}{2}" /></a>

<a href="http://www.codecogs.com/eqnedit.php?latex=sum_{i=1}^{n-1}tfrac{n(n-1)}{4}" target="_blank"><img src="/images/http://latex.codecogs.com/gif.latex?sum_{i=1}^{n-1}tfrac{n(n-1)}{4}" title="sum_{i=1}^{n-1}tfrac{n(n-1)}{4}" /></a>

अस्सलाम वालेकुम,

उत्तर:

कोई जांच नहीं है - यदि सरणी पहले ही सॉर्ट की गई है - आपके कोड में, तो if-statement की संख्या हमेशा होती है

Q = 1 + 2 + 3 + ... + n-1  = n * (n-1) / 2

नहीं कि विकी कोड चेकों

   ....
until not swapped

और निष्पादित कर सकते हैं (n-1) सर्वोत्तम मामले में अगर-कथन (क्रमबद्ध सरणी)

अगर कथन हमेशा सटीक उसी संख्या को निष्पादित किया जाएगा, लगभग n ^ 2/2।

कितनी बार कथन 4 निष्पादित किया जाएगा, यह एक दिलचस्प सवाल है। खासकर औसत संख्या के लिए, गणित दिलचस्प होगा।