Radix Sort in Python (in HINDI) | पाइथन में रेडिक्स सॉर्ट।

कथन:
प्राकृतिक क्रम में उन्हें पुनर्व्यवस्थित, पूर्णांकों की एक अव्यवस्थित सूची को देखते हुए।

नमूना इनपुट: [534, 246, 933, 127, 277, 321, 454, 565, 220]

नमूना आउटपुट: [127, 220, 246, 277, 321, 454, 534, 565, 933]

:समाधान की समय जटिलता (Time Complexity)
सबसे अच्छा मामले ओ (के एन) O(kn); औसत के मामले ओ (के एन)O(kn); सबसे खराब स्थिति हे (के .एन.)O(kn),

जहाँ पर के (k) सबसे लम्बे नंबर की लम्बाई है।

k lon(n) "क लॉग (एन)" से अधिक है तो एक nlog (एन) एल्गोरिथ्म एक बेहतर फिट होगा। हकीकत में हम हमेशा मूलांक बदल सकते हैं

दृष्टिकोण:
मूलांक तरह, प्रकार और बाल्टी प्रकार की गिनती की तरह, आधारित एक पूर्णांक है
इनपुट सरणी के मूल्यों यानी # एल्गोरिथ्म (माना जाता है पूर्णांकों)। इसलिए मूलांक तरह सबसे तेजी से छँटाई एल्गोरिदम के बीच है चारों ओर, सिद्धांत में। मूलांक तरह के लिए विशेष भेद है
यह प्रत्येक सिफर (यानी अंकों) के लिए एक बाल्टी बनाता है कि #; जैसे की, प्रकार बाल्टी के लिए भी इसी तरह, मूलांक तरह प्रत्येक बाल्टी होना चाहिए अलग चाबियाँ स्वीकार कर सकते हैं कि # उगने वाली दाढ़ी सूची।
दशमलव मूल्यों के लिए , बकेट की संख्या दशमलव के रूप में 10 है, प्रणाली 10 अंकों के / Cyphers (यानी 0,1,2,3,4,5,6,7,8,9) है। फिर चाबियाँ लगातार महत्वपूर्ण अंक के अनुसार क्रमबद्ध हैं।

प्रोग्राम के नीचे लिखा है :-

def RadixSort(A):
    RADIX = 10
    maxLength = False
    tmp , placement = -1, 1

    while not maxLength:
        maxLength = True
        buckets = [list() for _ in range(RADIX)]
        for  i in A:
            tmp = i / placement
            buckets[tmp % RADIX].append(i)
            if maxLength and tmp > 0:
                maxLength = False

        a = 0
        for b in range(RADIX):
            buck = buckets[b]
            for i in buck:
                A[a] = i
                a += 1
    # move to next digit
    placement *= RADIX
    return A
A = [534, 246, 933, 127, 277, 321, 454, 565, 220]
print(RadixSort(A))

यही प्रोग्राम अगर आप सभी प्रकार के इनपुट के लिए लिखना चाहते हैं तो वह भी निचे लिखा गया है।

def RadixSort(A):
    RADIX = 10
    maxLength = False
    tmp , placement = -1, 1

    while not maxLength:
        maxLength = True
        buckets = [list() for _ in range(RADIX)]
        for  i in A:
            tmp = i / placement
            buckets[tmp % RADIX].append(i)
            if maxLength and tmp > 0:
                maxLength = False

        a = 0
        for b in range(RADIX):
            buck = buckets[b]
            for i in buck:
                A[a] = i
                a += 1
    # move to next digit
    placement *= RADIX
    return A
A = []
n = input("Enter the numebr of elements you want to sort : ")
print("Enter the numbers : \n")
for i in range(0, n):
    num = int(input())
    A.append(num)
print(RadixSort(A))

धन्यवाद

Time Complexity involving if, elif and else condition in Python Program (in HINDI)

पाइथन प्रोग्राम की समय जटिलता ( टाइम कोम्प्लेक्सिटी ) जिनमे if, elif, अथवा else कंडीशंस इस्सतमल किया गया है।

निचे कुछ उदाहरण मैंने लिख रखे है। 

पहला उद्धरण

def SimpleIfCondition(n):
    i = n
    if i == 0: 
        i = i + 1
    print i

इस प्रोग्राम की समय जटिलता ( टाइम कोम्प्लेक्सिटी ) ओ(1) यानी  "O(1)" है।

विवरण / व्याख्या
हम मान लेते हैं की असाइनमेंट (assignment) ऑपरेटर केवल एक यूनिट समय लेता है। 
साथ ही में अगर कोई कंडीशनल if , elif अथवा else कंडीशन है तो वह भी एक यूनिट समय लेता है। 

अब हम साफ देख सकते हैं की ४ (4) स्टेटमेंट निष्पादित (execute) होंगे अथार्त हम इस फंक्शन की समय जटिलता (time complexity) को O(4) बोल सकते है जो की O(1) के बराबर है।
यह प्रोग्राम कांस्टेंट समय लेता है। 

दूसरा उद्धरण 

def IfElseCondition(n):
    i = n
    if i == 0: 
        i = i + 1
    elif i == 1:
        i += 2    
    print i  
    
# O(1)

यह उदाहरण भी पिछले उदाहरण की तरह है।
इस की टाइम कोम्प्लेक्सिटी भी O(1) ही है।
इस प्रोग्राम के लिए स्पष्टीकरण की कोई जरूरत नहीं है।

कुछ ऐसे प्रोग्राम जिनकी टाइम कोम्प्लेक्सिटी O(n) है। 

तीसरा उद्धरण 

# O(n)    
def testFunction(n):
    for j in range(1,n):
            print j           

इस फंक्शन में फॉर लूप ऍन(n) बार चल रहा है और हर बार j की वैल्यू प्रिंट कर रहा है। अर्थार्त इस फंक्शन की टाइम कोम्प्लेक्सिटी O(n) है। 

चौथा उद्धरण  

# O(n)
def IfElseCondition2(n):
    i = n
    if i > 0: 
        for j in range(1,n):
            print j
    elif i < 0:
        i += 2    
    print i   

अगर हम इस फंक्शन में ऍन (n) की वैल्यू 0 से बड़ी डालते है तो इस प्रोग्राम की टाइम कोम्प्लेक्सिटी भी हो O(n) जाएगी। 
जैसा की हम जानते हैं  प्रोग्राम की सबसे खराब मामले की प्रतिनिधिनित्वा करता है। इसीलिए इस का टाइम कोम्प्लेक्सिटी O(n) है। 

पांचवा उद्धरण 

# O(n^2): Note that if testFunction is executed always
def IfElseCondition3(n):
    i = n
    if testFunction(n) > 0: 
        for j in range(1,n):
            print j
    elif i < 0:
        i += 2    
    print i   

नोट है कि अगर हमेशा चलता है तो इस्सकी टाइम कोम्प्लेक्सिटी ओ(n^2) हो जाएगी। 

आप को किसी भी प्रकार का संदेह है तो इस पोस्ट की टिप्पणी अनुभाग में पूछ सकते है। 

धन्यवाद 

Time Complexity of Python Programs With Break Statement

हिंदी में प्रोग्राम को समझाया गया है 

यह पोस्ट में python कार्यक्रम से जुड़े बयानों (functions) अथवा प्रोग्राम की समय जटिलता ( Time Complexity ) खोजने के बारे में है।
ये break स्टेटमेंट इस्सतमल किये हुए प्रोग्राम की समय जटिलता बताता है।

def Function(n):
   count = 0
   for i in range(n / 2, n):  # बाहरी पाश एन / 2 बार निष्पादित होता है।(Outer loop execute n/2 times)
      j = 1
      while j + n / 2 <= n:  # मध्य पाश के पास ब्रेक स्टेटमेंट है (Middle loop has break)
         break
         j = j * 2

      print (count)

Function(20)

इस प्रोगाम में आप ऍन की कोई भी वैल्यू लें सकते है परन्तु जो परिस्थिति दी हुई है ( j + n/2 <= n ) वो हमेशा ही सही रहेगी। इसके परिणाम के रूप में while लूप ख़त्म ( terminate ) हो जाता है। यह प्रोग्राम का while ब्लॉक केवल एक ही बार चलेगा क्योकि ब्रेक स्टेटमेंट प्रोग्राम को while लूप से बहार ले जायेगा और लूप ख़त्म हो जायेगा।
परन्तु फॉर लूप वाला ब्लॉक ऍन बार चलेगा। 

प्रणाम स्वरूप इस पाइथन प्रोग्राम इस समय जटिलता ( Time Complexity ) ओ(n) अथवा  O(n) हो जाएगी। 

Python program explained in English

Here we are going to learn how to find the time complexity of a python program which involves the a break statement.
The program is written in the above segment of this post.

In the program if we put any value of n ( in this case I have taken 20 as the value of n), then the condition inside the while loop ( j + n/2 <= n) remains true and then the execution of break statement takes place which brings us out of the while loop and then clearly we can see that the for loop is running n times. So the overall time complexity of the above program is O(n).