<jupyter_start><jupyter_text>**Sorting with python.**  **Bubble Sorting.** * simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order.* ![Imgur](https://i.imgur.com/9Pxe3S3.png) **Complexities.*** **Worst and Average Case Time Complexity:** O(n*n).     * Worst case occurs when array is reverse sorted.* **Best Case Time Complexity:** O(n).     * Best case occurs when array is already sorted.* **Auxiliary Space:** O(1)* **Boundary Cases:** Bubble sort takes minimum time (Order of n) when elements are already sorted.* **Sorting In Place:** Yes* **Stable:** Yes* Due to its simplicity, bubble sort is often used to introduce the concept of a sorting algorithm. **Usage.*** In computer graphics it is popular for its capability to detect a very small error (like swap of just two elements) in almost-sorted arrays and fix it with just linear complexity (2n).<jupyter_code>#let's write a code for bubble sort.
def Bubble_Sort(array):
    n=len(array)
    for i in range(n):
        for j in range(0,n-i-1):
            if array[j]>array[j+1]:
                array[j],array[j+1]=array[j+1],array[j]


#driver program.
if __name__ == "__main__":
    arr=[5,1,4,2,8,9]
    print("The array before sorting is: ",arr)
    #now let's call the bubble sort function.
    sort_array = Bubble_Sort(arr)
    print("The array after sorting is: ",arr)<jupyter_output>The array before sorting is:  [5, 1, 4, 2, 8, 9]
The array after sorting is:  [1, 2, 4, 5, 8, 9]<jupyter_text>**Insertion Sorting.*** Insertion sort is a simple sorting algorithm that works the way we sort playing cards in our hands. **Illustration.*** array = 12, 11, 13, 5, 6* Let us loop for i = 1 (second element of the array) to 4 (last element of the array)* i = 1. Since 11 is smaller than 12, move 12 and insert 11 before 12    * 11, 12, 13, 5, 6* i = 2. 13 will remain at its position as all elements in A[0..I-1] are smaller than 13    * 11, 12, 13, 5, 6* i = 3. 5 will move to the beginning and all other elements from 11 to 13 will move one position ahead of their current position.    * 5, 11, 12, 13, 6* i = 4. 6 will move to position after 5, and elements from 11 to 13 will move one position ahead of their current position.    * 5, 6, 11, 12, 13<jupyter_code>#function for insertion sort
def Insertion_Sort(array):
    #first of all we'll store the key variable viz. a boundary between sorted and unsorted array
    #then we'll compare the sorted array with the key.. if key is smaller than sorted array then we swap all 
    #elements in sorted array
    n=len(array)
    for i in range(1,n):
        print("i: ",i)
        key = array[i]
        j=i-1
        print("j: ",j)
        print("array[j]: ",array[j])
        while j>=0 and key<array[j]:
            array[j+1]=array[j]
            j-=1
        array[j+1]=key
        #let's monitor array at every stage.
        print("array: ",arr)

#driver program.
if __name__ == "__main__":
    arr=[5,1,4,2,8,9]
    print("The array before sorting is: ",arr)
    #now let's call the bubble sort function.
    Insertion_Sort(arr)
    print("The array after sorting is: ",arr)<jupyter_output>The array before sorting is:  [5, 1, 4, 2, 8, 9]
i:  1
j:  0
array[j]:  5
array:  [1, 5, 4, 2, 8, 9]
i:  2
j:  1
array[j]:  5
array:  [1, 4, 5, 2, 8, 9]
i:  3
j:  2
array[j]:  5
array:  [1, 2, 4, 5, 8, 9]
i:  4
j:  3
array[j]:  5
array:  [1, 2, 4, 5, 8, 9]
i:  5
j:  4
array[j]:  8
array:  [1, 2, 4, 5, 8, 9]
The array after sorting is:  [1, 2, 4, 5, 8, 9]<jupyter_text>**Selection Sort.*** The selection sort algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at the beginning. The algorithm maintains two subarrays in a given array.* 1) The subarray which is already sorted.* 2) Remaining subarray which is unsorted.* In every iteration of selection sort, the minimum element (considering ascending order) from the unsorted subarray is picked and moved to the sorted subarray.<jupyter_code>#let's write a code for selection sort using python.
def Selection_Sort(array):
    n=len(array)
    for i in range(n):
        
        min_id=i
        for j in range(i+1,n):
            if array[min_id]>array[j]:
                min_id=j
                
        array[i],array[min_id]=array[min_id],array[i]
                
    
#driver program.
if __name__ == "__main__":
    arr=[5,1,4,2,8,9]
    print("The array before sorting is: ",arr)
    #now let's call the bubble sort function.
    Selection_Sort(arr)
    print("The array after sorting is: ",arr)<jupyter_output>The array before sorting is:  [5, 1, 4, 2, 8, 9]
The array after sorting is:  [1, 2, 4, 5, 8, 9]
{'fraction_non_alphanumeric': 0.11882028431996605, 'fraction_numerical': 0.04052620411627413, 'mean_word_length': 3.216457960644007, 'pattern_counts': {'":': 3, '<': 11, '<?xml version=': 0, '>': 13, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '3', 'dir': 'jupyter-structured-clean-dedup', 'id': '113683', 'license': 'MIT', 'n_tokens_mistral': 1700, 'n_tokens_neox': 1525, 'n_words': 668, 'path': 'Algorithms/Sorting with python.ipynb', 'repo_name': 'Dammonoit/Python_Arsenal', 'size': '4713'}