Sorting Algorithms

Sorting algorithms are used to arrange the elements of a list or array in a particular order, such as ascending or descending.

Common Sorting Algorithms

• Bubble Sort: A simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order.
• Selection Sort: Divides the input list into two parts: a sorted and an unsorted part, repeatedly selecting the smallest element from the unsorted part and moving it to the sorted part.
• Insertion Sort: Builds a sorted array one element at a time by repeatedly taking the next element and inserting it into the correct position.
• Merge Sort: A divide-and-conquer algorithm that divides the list into halves, sorts each half, and merges them back together.
• Quick Sort: Selects a 'pivot' element and partitions the array into two halves, recursively sorting the halves.

Bubble Sort

Bubble Sort is a simple comparison-based sorting algorithm where each element in the array is compared with the next one. If an element is larger than the next one, the two elements are swapped. This process is repeated until the entire array is sorted.

#include <stdio.h>
void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr)/sizeof(arr[0]);
    bubbleSort(arr, n);
    printf("Sorted array: ");
    printArray(arr, n);
    return 0;
}

Explanation:
• Function 1: bubbleSort:
  • Outer Loop (i): Runs for n-1 iterations because after n-1 passes, all elements are sorted.
  • Inner Loop (j): Compares adjacent elements and swaps them if necessary. The number of comparisons decreases after each pass since the largest elements are moved to the end.
  • Swapping: If arr[j] > arr[j + 1], the two elements are swapped to ensure that the largest element is moved to the correct position.
• Function 2: printArray:
  • Prints the elements of the array. The loop iterates through each element, printing it followed by a space. A newline is printed at the end.
• Main Function:
  • Array Initialization: The array arr[] is initialized with unsorted values: {64, 34, 25, 12, 22, 11, 90}.
  • Size Calculation: The size of the array is calculated using sizeof(arr) / sizeof(arr[0]) to determine how many elements are in the array.
  • Bubble Sort Function Call: The bubbleSort function is called to sort the array.
  • Print Sorted Array: The sorted array is printed using the printArray function.
• How Bubble Sort Works:
  • First Pass:
    • Compare 64 and 34 → swap → {34, 64, 25, 12, 22, 11, 90}
    • Compare 64 and 25 → swap → {34, 25, 64, 12, 22, 11, 90}
    • Compare 64 and 12 → swap → {34, 25, 12, 64, 22, 11, 90}
    • Compare 64 and 22 → swap → {34, 25, 12, 22, 64, 11, 90}
    • Compare 64 and 11 → swap → {34, 25, 12, 22, 11, 64, 90}
    • Compare 64 and 90 → no swap → {34, 25, 12, 22, 11, 64, 90}
    • At the end of the first pass, 90 is in its correct position.
  • Second Pass:
    • Compare 34 and 25 → swap → {25, 34, 12, 22, 11, 64, 90}
    • Compare 34 and 12 → swap → {25, 12, 34, 22, 11, 64, 90}
    • Compare 34 and 22 → swap → {25, 12, 22, 34, 11, 64, 90}
    • Compare 34 and 11 → swap → {25, 12, 22, 11, 34, 64, 90}
    • Compare 34 and 64 → no swap → {25, 12, 22, 11, 34, 64, 90}
    • At the end of the second pass, 64 is in its correct position.
  • Third Pass:
    • Compare 25 and 12 → swap → {12, 25, 22, 11, 34, 64, 90}
    • Compare 25 and 22 → swap → {12, 22, 25, 11, 34, 64, 90}
    • Compare 25 and 11 → swap → {12, 22, 11, 25, 34, 64, 90}
    • Compare 25 and 34 → no swap → {12, 22, 11, 25, 34, 64, 90}
    • At the end of the third pass, 34 is in its correct position.
  • Final Sorted Array:
    • After all passes, the array is sorted as:
    {11, 12, 22, 25, 34, 64, 90}.
  • Conclusion: The bubble sort algorithm sorts an array by repeatedly comparing adjacent elements and swapping them if they are in the wrong order, with each pass "bubbling" the largest unsorted element to its correct position.
  ← Previous Topic

  Introduction to Algorithms

  Searching Algorithms

  Next Topic →