16. Selection Sort
Sorting algorithms are crucial for efficient searching, particularly when using a binary search on sorted data. This chapter presents selection sort, demonstrating its step-by-step mechanism of repeatedly selecting the minimal element and placing it at the beginning of the unsorted portion. The selection sort algorithm is intuitive, although it can be inefficient for large datasets due to its O(n^2) time complexity.
Sections
Navigate through the learning materials and practice exercises.
What we have learnt
- Sorting improves search efficiencies and allows for determining median values and generating frequency tables.
- Selection sort operates by selecting the smallest element from the unsorted part of the array and swapping it with the first unsorted element.
- The time complexity for selection sort is O(n^2), making it unsuitable for very large datasets.
Key Concepts
- -- Selection Sort
- An algorithm that sorts an array by repeatedly selecting the smallest element from the unsorted portion and moving it to the beginning.
- -- Time Complexity
- A computational complexity that describes the amount of time it takes to run an algorithm as a function of the length of the input.
- -- Binary Search
- A search algorithm that finds the position of a target value within a sorted array, halving the search interval with each step.
- -- Median
- The middle value in a sorted list of numbers, with half the values larger and half smaller.
- -- Big O Notation
- A mathematical notation used to describe the upper bound of the time complexity of an algorithm in terms of input size.
Additional Learning Materials
Supplementary resources to enhance your learning experience.