Sorting algorithm

Bubble Sort

Bubble sort repeatedly compares adjacent elements and swaps them if they are in the wrong order. This process is repeated until the array is completely sorted. It is called "bubble sort" because with each pass, the largest element gradually "bubbles" up to its correct position.
You can see a short video about moving

Explanation

We start with the original array [1, 0, 5, 8, -1, -2].
The algorithm compares adjacent elements in pairs and swaps them if they are in the wrong order. In each pass, the largest element "bubbles" up to its correct position at the end of the array.
Step 1: Comparing 1 and 0, they are in the correct order. Comparing 0 and 5, they are in the correct order. Comparing 5 and 8, they are in the correct order. Comparing 8 and -1, they are in the wrong order, so we swap them. Comparing 8 and -2, they are in the wrong order, so we swap them. The array becomes [1, 0, 5, -1, -2, 8].
Step 2: Comparing 1 and 0, they are in the wrong order, so we swap them. Comparing 1 and 5, they are in the correct order. Comparing 5 and -1, they are in the wrong order, so we swap them. Comparing 5 and -2, they are in the wrong order, so we swap them. The array becomes [0, 1, -1, -2, 5, 8]. The algorithm repeats the passes until the array is completely sorted.
Step 3: Comparing 0 and 1, they are in the correct order. Comparing 1 and -1, they are in the wrong order, so we swap them. Comparing 1 and -2, they are in the wrong order, so we swap them. The array becomes [0, -1, -2, 1, 5, 8].
Step 4: Comparing 0 and -1, they are in the correct order. Comparing -1 and -2, they are in the correct order. The array remains [0, -1, -2, 1, 5, 8].
Step 5: Comparing 0 and -1, they are in the correct order. Comparing -1 and -2, they are in the correct order. The array remains [0, -1, -2, 1, 5, 8].
The array is now sorted, and the final result is [0, -1, -2, 1, 5, 8].

Explanation

Here's how it works using the example array [1, 0, 5, 8, -1, -2]:
We start with the original array [1, 0, 5, 8, -1, -2].
The algorithm divides the array into two parts: the sorted part and the unsorted part. Initially, the sorted part contains only the first element, and the unsorted part contains the remaining elements.
In each iteration, the algorithm takes an element from the unsorted part and inserts it into its correct position within the sorted part.
In the first iteration, we take the second element, 0, from the unsorted part. We compare it with the first element, 1, in the sorted part. Since 0 is smaller, we shift 1 one position to the right and insert 0 at the beginning of the sorted part. The array becomes [0, 1, 5, 8, -1, -2].
In the second iteration, we take the third element, 5, from the unsorted part. We compare it with the elements in the sorted part [0, 1]. Since 5 is greater than 1 and smaller than 8, we insert it between 1 and 8 in the sorted part. The array becomes [0, 1, 5, 8, -1, -2].
In the third iteration, we take the fourth element, 8, from the unsorted part. We compare it with the elements in the sorted part [0, 1, 5]. Since 8 is greater than all the elements in the sorted part, we leave it at its current position. The array remains unchanged.
In the fourth iteration, we take the fifth element, -1, from the unsorted part. We compare it with the elements in the sorted part [0, 1, 5, 8]. Since -1 is smaller, we shift 0, 1, 5, and 8 one position to the right and insert -1 at the beginning of the sorted part. The array becomes [-1, 0, 1, 5, 8, -2].
In the fifth iteration, we take the last element, -2, from the unsorted part. We compare it with the elements in the sorted part [-1, 0, 1, 5, 8]. Since -2 is smaller, we shift all the elements in the sorted part one position to the right and insert -2 at the beginning of the sorted part. The array becomes [-2, -1, 0, 1, 5, 8].
The algorithm repeats the iterations until the entire array is sorted.
The final result is the sorted array [-2, -1, 0, 1, 5, 8]. Insertion sort builds the sorted portion of the array by taking one element at a time from the unsorted part and inserting it into its correct position within the sorted part. This process continues until the entire array is sorted.

Explanation

Here's how it works using the example array [1, 0, 5, 8, -1, -2]:
We start with the original array [1, 0, 5, 8, -1, -2].
The algorithm divides the array into two parts: the sorted part and the unsorted part. Initially, the sorted part is empty, and the unsorted part is the entire array.
In each iteration, the algorithm finds the minimum element from the unsorted part and swaps it with the first element of the unsorted part.
In the first iteration, the minimum element of the unsorted part [-2, -1, 0, 5, 8] is -2. It is swapped with the first element, resulting in [-2, 0, 5, 8, -1, 1].
In the second iteration, the minimum element of the unsorted part [-1, 0, 5, 8, -1] is -1. It is swapped with the second element, resulting in [-2, -1, 5, 8, 0, 1].
In the third iteration, the minimum element of the unsorted part [0, 5, 8, 0] is 0. Since it is already at its correct position, no swap is performed. The array remains unchanged.
In the fourth iteration, the minimum element of the unsorted part [5, 8, 0] is 0. It is swapped with the fourth element, resulting in [-2, -1, 0, 8, 5, 1].
In the fifth iteration, the minimum element of the unsorted part [8, 5, 1] is 1. It is swapped with the fifth element, resulting in [-2, -1, 0, 1, 5, 8].
The algorithm repeats the iterations until the entire array is sorted.
The final result is the sorted array [-2, -1, 0, 1, 5, 8].

• Start with the least significant digit (the rightmost digit) of the numbers. In this case, it's the ones place digit.
• Group the numbers based on their digit values. Create 10 buckets (0 to 9) to temporarily store the numbers. Go through each number in the array and put it in the corresponding bucket based on its digit value.
  • Buckets:
  • 0:
  • 1: [110]
  • 2: [2]
  • 3: [37]
  • 4: [14]
  • 5: [50]
  • 6:
  • 7:
  • 8:
  • 9: [29]
• Take the numbers out of the buckets and put them back into the array in the order they appear in the buckets. Start with bucket 0 and go through each bucket from 0 to 9, putting the numbers back into the array.
  • Array: [110, 2, 37, 14, 50, 29]
• Now, move to the next significant digit, which is the tens place digit.
• Repeat steps 2 and 3, sorting the numbers based on the tens place digit. Put the numbers into the buckets and then back into the array.
  • Buckets:
  • 0: [2, 14]
  • 1:
  • 2: [29]
  • 3: [37]
  • 4:
  • 5: [50]
  • 6:
  • 7:
  • 8:
  • 9: [110]
  • Array: [2, 14, 29, 37, 50, 110]
• Continue this process for the remaining digits. In this case, there is only one digit left, which is the hundreds place digit.
  • Buckets:
  • 0: [2, 14, 29, 37, 50, 110]
  • 1:
  • 2:
  • 3:
  • 4:
  • 5:
  • 6:
  • 7:
  • 8:
  • 9:
  Array Sorted : [2, 14, 29, 37, 50,110]
  After sorting based on the hundreds place digit, the array is now fully sorted in ascending order.
  
  

  Solution

  
              def radix_sort(arr):
              # Find the maximum number in the array to determine the maximum number of digits
              max_num = max(arr)
              
              # Perform counting sort for every digit
              exp = 1
              while max_num // exp > 0:
                  counting_sort(arr, exp)
                  exp *= 10
          
          def counting_sort(arr, exp):
              n = len(arr)
              output = [0] * n
              count = [0] * 10
              
              # Count the occurrences of each digit
              for num in arr:
                  index = num // exp % 10
                  count[index] += 1
              
              # Calculate the cumulative count
              for i in range(1, 10):
                  count[i] += count[i - 1]
              
              # Build the sorted output array
              for i in range(n - 1, -1, -1):
                  num = arr[i]
                  index = num // exp % 10
                  output[count[index] - 1] = num
                  count[index] -= 1
              
              # Copy the sorted elements back to the original array
              for i in range(n):
                  arr[i] = output[i]
          
          # Test the radix sort algorithm
          arr = [14, 29, 37, 50, 110]
          radix_sort(arr)
          print("Sorted array:", arr)
          
          
      

Quick sort is a sorting algorithm that follows a divide-and-conquer approach. Here's a simple explanation of how quick sort works using your example array [5, 2, 6, 9, 3, 1, 6, 4]:

• Choose a pivot element from the array. The pivot can be any element, but for simplicity, let's choose the last element, 4, as the pivot.
• Partition the array into two sub-arrays:
  • All elements smaller than the pivot are moved to the left sub-array.
  • All elements greater than the pivot are moved to the right sub-array.
  • The pivot element is placed in its final sorted position.
  For our example, after the first partition step, we might have:
  • [2, 3, 1, 4] [5] [6, 9, 6]
• Now, recursively apply the above steps to the left and right sub-arrays. Choose a pivot for each sub-array and partition them until each sub-array contains only one element, as this means they are already sorted.
  • For the left sub-array [2, 3, 1, 4]:
  • Choose 4 as the pivot.
  • After partitioning, we might have: [2, 3, 1] [4]
  • For the right sub-array [6, 9, 6]:
  • Choose 6 as the pivot.
  • After partitioning, we might have: [6, 6] [9]
• At this point, all sub-arrays are sorted individually. Concatenate the sorted sub-arrays in the order: left sub-array, pivot element, right sub-array.
  • Final sorted array: [1, 2, 3, 4, 5, 6, 6, 9]

Solution

        def quick_sort(arr):
            if len(arr) <= 1:
                return arr
        
            # Select the pivot element (for simplicity, let's choose the first element)
            pivot = arr[0]
        
            # Partition the array into elements smaller than pivot and elements greater than pivot
            lesser = [x for x in arr[1:] if x <= pivot]
            greater = [x for x in arr[1:] if x > pivot]
        
            # Recursively sort the sub-arrays and combine them
            return quick_sort(lesser) + [pivot] + quick_sort(greater)
    
        
        # Example usage
        arr = [5, 2, 7, 9, 3, 1, 8, 4]
        sorted_arr = quick_sort(arr)
        print(sorted_arr)
        
    

Merge Sort

The merge sort algorithm recursively divides the array into smaller subarrays, sorts them individually, and then merges them back together to produce a sorted array. This process guarantees that the array will be sorted correctly.

Explanation

Divide: The array is divided into smaller parts until we have single-element subarrays. This is done recursively. In our example, we start by dividing the array into individual elements: [8], [2], [7], [9], [3], [1], [2], [4].
Merge: The algorithm then merges the smaller subarrays back together in a sorted manner. It compares elements from the divided subarrays and combines them in ascending order. The merging process continues until we have a single sorted array.
First, we compare and merge pairs of subarrays: [2, 8] and [7, 9] become [2, 7, 8, 9], and [1, 3] and [2, 4] become [1, 2, 3, 4]. Next, we merge the resulting subarrays [2, 7, 8, 9] and [1, 2, 3, 4]. Comparing the elements one by one, we construct a new sorted subarray: [1, 2, 2, 3, 4, 7, 8, 9].
Final Result: The final step gives us the completely sorted array [1, 2, 2, 3, 4, 7, 8, 9].

    def merge_sort(arr):
        if len(arr) <= 1:
            return arr

        mid = len(arr) // 2
        left_half = arr[:mid]
        right_half = arr[mid:]

        left_half = merge_sort(left_half)
        right_half = merge_sort(right_half)

        return merge(left_half, right_half)
    
    
    def merge(left, right):
        merged = []
        left_index = 0
        right_index = 0
    
        while left_index < len(left) and right_index < len(right):
            if left[left_index] <= right[right_index]:
                merged.append(left[left_index])
                left_index += 1
            else:
                merged.append(right[right_index])
                right_index += 1
    
        while left_index < len(left):
            merged.append(left[left_index])
            left_index += 1
    
        while right_index < len(right):
            merged.append(right[right_index])
            right_index += 1
    
        return merged
    
    
    # Example usage
    arr = [8, 2, 7, 9, 3, 1, 2, 4]
    sorted_arr = merge_sort(arr)
    print(sorted_arr)