सॉर्टिंग क्या है?

सॉर्टिंग से तात्पर्य डेटा आइटमों के बीच रैखिक संबंध के आधार पर डेटा को एक विशिष्ट क्रम में, आमतौर पर आरोही या अवरोही क्रम में व्यवस्थित करने की प्रक्रिया से है।

हमें छँटाई की आवश्यकता क्यों है?

संरचित डेटा के साथ काम करते समय सॉर्टिंग महत्वपूर्ण है क्योंकि यह कुशल डेटा पुनर्प्राप्ति की अनुमति देता है, डेटा विश्लेषण को सरल बनाता है, और समग्र डेटा प्रबंधन को बढ़ाता है।

छँटाई एल्गोरिदम

यह पोस्ट निम्नलिखित सॉर्टिंग एल्गोरिदम को शामिल करती है: बबल सॉर्ट, चयन सॉर्ट, इंसर्शन सॉर्ट, मर्ज सॉर्ट, और त्वरित सॉर्ट।

बुलबुले की तरह

बबल सॉर्ट बार-बार सरणी के माध्यम से कदम बढ़ाता है, आसन्न तत्वों की तुलना करता है और यदि वे गलत क्रम में हैं तो उन्हें स्वैप करता है। यह प्रक्रिया तब तक जारी रहती है जब तक कि सरणी क्रमबद्ध न हो जाए, बड़े तत्व अंत तक "बुदबुदाते" रहते हैं।

एल्गोरिदम

चरण 1: प्रारंभ करें
चरण 2: i = 0
चरण 3: यदि i पर जाएं चरण 4: जे = 0
चरण 5: यदि j पर जाएं चरण 6: यदि सरणी[जे] > सरणी[जे 1], तो चरण 7; अन्यथा चरण 8
पर जाएं चरण 7: सरणी[जे] और सरणी[जे 1]
को स्वैप करें चरण 8: वेतन वृद्धि जे; गोटो चरण 5
चरण 9: वेतन वृद्धि I; गोटो चरण 3
चरण 10: समाप्त

कोड

def bubble_sort(arr):
    print("Array Before Sorting: ", end='')
    print(arr)
    for i in range(len(arr)):
        for j in range(len(arr)-i-1):
            if arr[j] > arr[j 1]:
                arr[j], arr[j 1] = arr[j 1], arr[j]

    print("Array After Sorting: ", end='')
    print(arr)

# Main
bubble_sort([7, 4, 1, 3, 4, 7, 87, 9, 6, 4, 2, 2, 3, 5, 6])

समय की जटिलता

सर्वश्रेष्ठ केस: O(n)
औसत मामला: O(n^2)
सबसे खराब स्थिति: O(n^2)

चयन छांटना

चयन सॉर्ट सरणी के अवर्गीकृत हिस्से में सबसे छोटा मान ढूंढता है और उसे उस हिस्से की शुरुआत में रखता है।

एल्गोरिदम

चरण 1 : प्रारंभ करें
चरण 2: i = 0
चरण 3: यदि i पर जाएं चरण 4 : न्यूनतम_मूल्य = i; जे = मैं 1
चरण 5: यदि j पर जाएं चरण 6: यदि सरणी[न्यूनतम_मूल्य] > सरणी[जे], तो चरण 7; अन्यथा चरण 8
पर जाएं चरण 7 : न्यूनतम_मूल्य = जे
चरण 8: वेतन वृद्धि जे; गोटो चरण 5
चरण 9: सरणी[न्यूनतम_मूल्य] और सरणी[i]
को स्वैप करें चरण 10: वेतन वृद्धि I; गोटो चरण 3
चरण 11: समाप्त

कोड

def selection_sort(arr):
    print("Array Before Sorting: ", end='')
    print(arr)
    for i in range(len(arr) - 1):
        min_val = i
        for j in range(i   1, len(arr)):
            if arr[j] 




  
  
  समय की जटिलता


सर्वश्रेष्ठ केस: O(n^2)

औसत मामला: O(n^2)

सबसे खराब स्थिति: O(n^2) 


  
  
  प्रविष्टि क्रम


इंसर्शन सॉर्ट प्रत्येक तत्व को अवर्गीकृत हिस्से से लेकर और उसे क्रमबद्ध हिस्से में सही स्थिति में डालकर एक समय में एक तत्व को क्रमबद्ध सरणी बनाता है।


  
  
  एल्गोरिदम


चरण 1: प्रारंभ करें

चरण 2: i = 1

चरण 3: यदि i  पर जाएं
चरण 4: कुंजी = गिरफ्तार[i]

चरण 5: जे = आई - 1

चरण 6: यदि j >= 0 और arr[j] > कुंजी, चरण 7 पर जाएं; अन्यथा चरण 10
 पर जाएं
चरण 7: गिरफ्तार[जे 1] = गिरफ्तार[जे]

चरण 8: j को 1 से घटाएं

चरण 9: गोटो चरण 6

चरण 10: गिरफ्तारी[जे 1] = कुंजी

चरण 11: 1 से वृद्धि; गोटो चरण 3

चरण 12: समाप्त


  
  
  कोड




def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1

        while j >= 0 and arr[j] > key:
            arr[j   1] = arr[j]
            j -= 1

        arr[j   1] = key

# Main
arr = [7, 4, 1, 3, 4, 7, 87, 9, 6, 4, 2, 2, 3, 5, 6]
print("Array Before Sorting:", arr)
insertion_sort(arr)
print("Array After Sorting:", arr)





  
  
  समय की जटिलता


सर्वश्रेष्ठ केस: O(n)

औसत मामला: O(n^2)

सबसे खराब स्थिति: O(n^2) 


  
  
  मर्ज सॉर्ट करें


मर्ज सॉर्ट एक डिवाइड-एंड-कॉन्कर एल्गोरिदम है जो सरणी को पुनरावर्ती रूप से छोटे उप-सरणी में विभाजित करता है, उन्हें सॉर्ट करता है, और फिर उन्हें वापस एक साथ विलय कर देता है।


  
  
  एल्गोरिदम


मर्ज सॉर्ट एल्गोरिदम


चरण 1: प्रारंभ करें

चरण 2: यदि लंबाई (सरणी) 
चरण 3: मध्य बिंदु = लंबाई (सरणी) // 2

चरण 4: बायाँ_आधा = सरणी[:मध्य_बिंदु]

चरण 5: दायां_आधा = सरणी[मध्य_बिंदु:]

चरण 6: sorted_left = merge_sort(left_half)

चरण 7: सॉर्टेड_राइट = मर्ज_सॉर्ट(राइट_हाफ)

चरण 8: रिटर्न मर्ज(सॉर्टेड_लेफ्ट, सॉर्टेड_राइट)

चरण 9: समाप्त

मर्ज फ़ंक्शन


चरण 1: प्रारंभ करें

चरण 2: sorted_merge = []

चरण 3: एल = 0, आर = 0

चरण 4: यदि एल  पर जाएं
चरण 5: यदि बाएं[एल]  पर जाएं
चरण 6: sorted_merge में बाएँ[l] जोड़ें; 1 से वेतन वृद्धि

चरण 7: sorted_merge में दाएँ[r] जोड़ें; 1 से वेतन वृद्धि

चरण 8: गोटो चरण 4

चरण 9: यदि एल  पर जाएं
चरण 10: sorted_merge में बाएँ[l] जोड़ें; 1 से वृद्धि एल 

चरण 11: गोटो चरण 9

चरण 12: यदि r 
चरण 13: sorted_merge में दाएँ[r] जोड़ें; 1 से वेतन वृद्धि

चरण 14: चरण 12 पर जाएं

चरण 15: सॉर्टेड_मर्ज लौटाएँ

चरण 16: समाप्त


  
  
  कोड




def merge(left, right):
    sorted_merge = []
    l = r = 0
    while l 




  
  
  समय की जटिलता


सर्वश्रेष्ठ केस: ओ(एन लॉग एन)

औसत मामला: O(n log n)

सबसे खराब स्थिति: O(n log n) 


  
  
  त्वरित छँटाई


क्विक सॉर्ट एक कुशल, इन-प्लेस सॉर्टिंग एल्गोरिदम है जो फूट डालो और जीतो दृष्टिकोण का उपयोग करता है। यह एक धुरी तत्व का चयन करता है और धुरी के चारों ओर सरणी को विभाजित करता है ताकि धुरी से छोटे तत्व इसके बाईं ओर हों और धुरी से बड़े तत्व इसके दाईं ओर हों। यह प्रक्रिया फिर उप-सरणियों पर पुनरावर्ती रूप से लागू की जाती है।


  
  
  एल्गोरिदम


त्वरित क्रमबद्ध


चरण 1: प्रारंभ करें

चरण 2: यदि कम  पर जाएं
चरण 3: पिवोट_इंडेक्स = विभाजन (एआर, निम्न, उच्च) 

चरण 4: त्वरित सॉर्ट(arr, low, pivot_index - 1)

चरण 5: त्वरित सॉर्ट(arr, pivot_index 1, उच्च)

चरण 6: समाप्त करें 

विभाजन समारोह


चरण 1: प्रारंभ करें

चरण 2: धुरी = गिरफ्तारी[उच्च]

चरण 3: बाएँ = निचला, दाएँ = ऊँचा - 1

चरण 4: यदि बाएँ 
चरण 5: यदि गिरफ्तारी[बाएं] > धुरी और गिरफ्तारी[दाएं]  को स्वैप करें
चरण 6: यदि गिरफ्तारी[बाएं] 
चरण 7: यदि गिरफ्तारी[दाएं] >= धुरी, कमी सही

चरण 8: गोटो चरण 4

चरण 9: गिरफ्तारी [बाएं] और गिरफ्तारी [उच्च] 
 को स्वैप करें
चरण 10: बाईं ओर लौटें

चरण 11: समाप्त करें 


  
  
  कोड




def partition(arr, low, high):
    pivot = arr[high]
    left = low
    right = high - 1
    while left  pivot and arr[right] = pivot:
            right -= 1
    arr[left], arr[high] = arr[high], arr[left]
    return left

def quicksort(arr, low, high):
    if low 




  
  
  समय की जटिलता


सर्वश्रेष्ठ केस: ओ(एन लॉग एन)

औसत मामला: O(n log n)

सबसे खराब स्थिति: O(n^2)