Sorting Algorithms
Sorting is a fundamental problem in computer science and is used to arrange the
elements of a collection (such as an array or list) in a specific order—either in
ascending or descending order. There are several algorithms used for sorting,
each with different performance characteristics. Below is a guide to the most
commonly used sorting algorithms.
1. Bubble Sort
Description:
Bubble Sort is a simple sorting algorithm that repeatedly steps through the
list, compares adjacent elements, and swaps them if they are in the wrong
order.
The algorithm gets its name because smaller elements "bubble" to the top
(beginning of the array).
Algorithm:
1. Starting from the first element, compare each pair of adjacent elements.
2. If the elements are in the wrong order, swap them.
3. Repeat the process for the remaining unsorted portion of the list.
4. Continue until no more swaps are needed.
Time Complexity:
Worst and Average Case: O(n2)O(n^2)O(n2)
Best Case: O(n)O(n)O(n) (when the array is already sorted)
Space Complexity: O(1)O(1)O(1) (in-place sorting)
Applications:
Mainly used in educational contexts due to its simplicity, but not efficient
for large datasets.
, 2. Selection Sort
Description:
Selection Sort repeatedly selects the minimum element from the unsorted
portion of the list and places it at the beginning.
Algorithm:
1. Find the smallest element in the unsorted portion of the array.
2. Swap it with the first unsorted element.
3. Repeat the process for the remaining unsorted portion of the list.
Time Complexity:
Worst, Average, and Best Case: O(n2)O(n^2)O(n2)
Space Complexity: O(1)O(1)O(1) (in-place sorting)
Applications:
Often used when memory space is limited.
3. Insertion Sort
Description:
Insertion Sort builds the final sorted array one item at a time. It is much
more efficient than bubble sort when dealing with small datasets or nearly
sorted lists.
Algorithm:
1. Start with the second element (consider the first element as a sorted part).
2. Compare the current element with the previous element(s) and insert it
into its correct position by shifting elements.
3. Repeat the process for each subsequent element.
Sorting is a fundamental problem in computer science and is used to arrange the
elements of a collection (such as an array or list) in a specific order—either in
ascending or descending order. There are several algorithms used for sorting,
each with different performance characteristics. Below is a guide to the most
commonly used sorting algorithms.
1. Bubble Sort
Description:
Bubble Sort is a simple sorting algorithm that repeatedly steps through the
list, compares adjacent elements, and swaps them if they are in the wrong
order.
The algorithm gets its name because smaller elements "bubble" to the top
(beginning of the array).
Algorithm:
1. Starting from the first element, compare each pair of adjacent elements.
2. If the elements are in the wrong order, swap them.
3. Repeat the process for the remaining unsorted portion of the list.
4. Continue until no more swaps are needed.
Time Complexity:
Worst and Average Case: O(n2)O(n^2)O(n2)
Best Case: O(n)O(n)O(n) (when the array is already sorted)
Space Complexity: O(1)O(1)O(1) (in-place sorting)
Applications:
Mainly used in educational contexts due to its simplicity, but not efficient
for large datasets.
, 2. Selection Sort
Description:
Selection Sort repeatedly selects the minimum element from the unsorted
portion of the list and places it at the beginning.
Algorithm:
1. Find the smallest element in the unsorted portion of the array.
2. Swap it with the first unsorted element.
3. Repeat the process for the remaining unsorted portion of the list.
Time Complexity:
Worst, Average, and Best Case: O(n2)O(n^2)O(n2)
Space Complexity: O(1)O(1)O(1) (in-place sorting)
Applications:
Often used when memory space is limited.
3. Insertion Sort
Description:
Insertion Sort builds the final sorted array one item at a time. It is much
more efficient than bubble sort when dealing with small datasets or nearly
sorted lists.
Algorithm:
1. Start with the second element (consider the first element as a sorted part).
2. Compare the current element with the previous element(s) and insert it
into its correct position by shifting elements.
3. Repeat the process for each subsequent element.
