Learn Important Sorting Techniques using Python

There are various sorting techniques. They are as follows:

• Selection Sort

• Bubble Sort

  • Iterative Bubble Sort

  • Recursive Bubble Sort

• Insertion Sort

  • Iterative Insertion Sort

  • Recursive Insertion Sort

• Merge Sort

• Quick Sort

Selection Sort

Selection sort is a straightforward sorting algorithm. Here are the detailed steps to perform the selection sort:

1. Start with the first element:

   • Find the smallest element in the array.

   • Swap this smallest element with the first element of the array.

2. Move to the next element:

   • Now consider the subarray starting from the second element to the last element.

   • Find the smallest element in this subarray.

   • Swap this smallest element with the second element of the array.

3. Continue this process:

   • Repeat the above steps for the remaining unsorted subarray. Each time, the starting index of the subarray will increase by one, and you find the smallest element in the remaining subarray and swap it with the element at the current starting index.

4. Stop when the array is sorted:

   • This process continues until you reach the last element of the array. By then, the array should be sorted in ascending order.

Here is a step-by-step example:

Example Array: [29, 10, 14, 37, 13]

• Step 1: Find the minimum element in [29, 10, 14, 37, 13]. The minimum element is 10. Swap 10 with 29.

  • Resulting Array: [10, 29, 14, 37, 13]

• Step 2: Find the minimum element in [29, 14, 37, 13]. The minimum element is 13. Swap 13 with 29.

  • Resulting Array: [10, 13, 14, 37, 29]

• Step 3: Find the minimum element in [14, 37, 29]. The minimum element is 14. It is already in the correct position, so no swap is needed.

  • Resulting Array: [10, 13, 14, 37, 29]

• Step 4: Find the minimum element in [37, 29]. The minimum element is 29. Swap 29 with 37.

  • Resulting Array: [10, 13, 14, 29, 37]

• Step 5: The last element is already sorted.

The array is now sorted: [10, 13, 14, 29, 37].

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        minindex = i
        for j in range(i+1,n):
            if arr[minindex] > arr[j]:
                minindex = j
        arr[i],arr[minindex] = arr[minindex],arr[i]

Explanation of Pseudocode

• We loop through each element in the array (outer loop for i in range(n)).

• We assume the current index i is the minimum (min_index = i).

• We then find the actual minimum element in the remaining part of the array (inner loop for j in range(i+1, n)).

• After finding the minimum element in the remaining subarray, we swap it with the element at the index i.

• This process is repeated until the entire array is sorted.

Selection sort is simple to implement but not the most efficient for large datasets due to its O(n^2) time complexity.

Bubble Sort

Bubble sort is another straightforward sorting algorithm. Here are the detailed steps to perform bubble sort:

1. Start at the beginning of the array:

   • Compare the first two elements. If the first element is greater than the second element, swap them.

   • Move to the next pair of elements, repeat the comparison, and swap if needed.

   • Continue this process until the end of the array is reached. After this pass, the largest element will have "bubbled up" to its correct position at the end of the array.

2. Repeat the process:

   • Start again from the beginning of the array, but this time only goes up to the second-to-last element (since the last element is already sorted).

   • Repeat the comparison and swapping process for the remaining elements.

3. Continue this process:

   • The next largest element will bubble up to its correct position with each pass.

   • Repeat this process, each time reducing the range of elements to be considered until no more swaps are needed.

4. Stop when the array is sorted:

   • The array is sorted when a pass through the array results in no swaps.

Here is a step-by-step example:

Example Array: [29, 10, 14, 37, 13]

• Pass 1:

  • Compare 29 and 10, swap → [10, 29, 14, 37, 13]

  • Compare 29 and 14, swap → [10, 14, 29, 37, 13]

  • Compare 29 and 37, no swap → [10, 14, 29, 37, 13]

  • Compare 37 and 13, swap → [10, 14, 29, 13, 37]

  • End of Pass 1: Largest element 37 is at the end.

• Pass 2:

  • Compare 10 and 14, no swap → [10, 14, 29, 13, 37]

  • Compare 14 and 29, no swap → [10, 14, 29, 13, 37]

  • Compare 29 and 13, swap → [10, 14, 13, 29, 37]

  • End of Pass 2: The second largest element 29 is in its correct position.

• Pass 3:

  • Compare 10 and 14, no swap → [10, 14, 13, 29, 37]

  • Compare 14 and 13, swap → [10, 13, 14, 29, 37]

  • End of Pass 3: Third largest element 14 is in its correct position.

• Pass 4:

  • Compare 10 and 13, no swap → [10, 13, 14, 29, 37]

  • End of Pass 4: The fourth largest element 13 is in its correct position.

• Pass 5:

  • There is only one element left, so the array is sorted.

The array is now sorted: [10, 13, 14, 29, 37].

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j],arr[j+1] = arr[j+1],arr[j]

Explanation of Pseudocode

1. Initialization:

   • n = len(arr): Get the length of the input array arr.

2. Outer Loop (for i in range(n)):

   • Run n passes over the array.

3. Inner Loop (for j in range(0, n-i-1)):

   • Start from the beginning of the array and go up to the element just before the already sorted part.

   • This ensures that each pass compares and possibly swaps all necessary elements.

4. Comparison and Swap:

   • Compare adjacent elements and swap if necessary to bubble the larger element towards the end of the array.

In summary, the provided code contains a deviation from the standard bubble sort implementation that can lead to incorrect sorting. The corrected version ensures that each pass starts from the beginning of the array and considers all necessary elements for comparison and swapping.