Chapter 5
Sorting
Sorting:
• Ordering or arrangement of elements in some particular order.
• In terms of numbers the arrangement is done on basis of ascending or descending
order.
• In terms of characters the arrangement is done according to the alphabets.
• Eg: Dictionary are sorted in alphabetical order.
Seats in an examination hall are ordered according to candidates’ roll number.
• sorting helps save time later – Although sorting takes effort, it makes finding things
easier.
• Searching in a sorted list is faster – It's quicker to find something in an organized list
than in a messy one. Sorting first makes everything simpler.
Bubble sort:
• It is simple technique where it sorts a given list of elements by repeatedly comparing
the adjacent elements and swapping them if they are unordered.
• Swapping means changing the position with each other- this happens only when the
compared element is lesser.
• Pass:- A pass means going through a list one time, checking each item. In sorting,
each pass helps organize the list step by step until everything is in order.
• Bubble sort makes n-1 passes to get a sorted elements.
• Compare neighboring elements – Each time, the algorithm checks two adjacent
elements in the list.
• Swap if needed – If they are in the wrong order, they are swapped to arrange them
correctly.
• Largest element moves to the end – After one full pass through the list, the biggest
element reaches to the rightest.
• Repeat for remaining elements – The process continues, ignoring the already sorted
largest elements in later passes.
• List gets smaller in each pass – With each round, fewer elements need sorting,
making the process quicker towards the end.
Advantages: (For your reference)
• Simple to understand and implement: It has a straightforward logic, making it easy
to code and grasp, especially for beginners learning sorting algorithms.
• Works well with small datasets: While inefficient for large lists, bubble sort can be
used for short lists where performance is not a major concern.
• Can detect if a list is already sorted: If no swaps occur during a pass, the algorithm
can stop early, making it slightly optimized in best-case scenarios.
• Minimal memory usage: It operates in-place, meaning it doesn't require extra
storage beyond the original list being sorted.
• Stable sorting algorithm: It preserves the relative order of equal elements, which can
be useful in certain applications where stability matters.
Disadvantages: (for your reference)
• Slow performance: It has a worst-case and average-case time complexity ,which
makes it impractical for sorting large lists.
• Not suitable for large datasets: Because it repeatedly swaps adjacent elements, it
requires multiple passes, leading to high processing time.
• Consumes more swaps: Compared to other sorting algorithms, bubble sort performs
many unnecessary swaps, making it inefficient.
• Lack of adaptability: Even in nearly sorted lists, bubble sort still goes through all
elements, making it slower than adaptive algorithms like insertion sort.
Eg:
No change
Selection sort:
• The list is divided into 2 parts- 1) sorted: left list
2) unsorted: right list
• Initially the left list is empty, and right list contains all the unsorted elements.
• Working principle:
1) Firstly, all the elements in the list are unsorted , should be traversed to find the
minimum element from the list.
2) The smallest element is swapped with the leftmost element, which is the first
position and is not considered for further sorting.
3) The unsorted list reduces by one element for the second pass.
4) In second step , search for the next smallest element from the remaining unsorted
elements, then swap it with the second left position.
5) The unsorted list reduces by one element for the third pass.
6) This will continues upto n-1 passes, until all the minimum elements are found and
placed respectively.
Advantages:
• Simple to understand and implement: It follows an intuitive approach—finding the
smallest (or largest) element and placing it in order—making it easy to grasp.
• Works well for small datasets: Although slow for large lists, selection sort performs
decently on small lists where performance isn’t a major concern.
• Fewer swaps compared to bubble sort: Unlike bubble sort, selection sort minimizes
the number of swaps, which can be beneficial in scenarios where swapping elements
is costly.
• Minimal memory usage: It requires no additional memory beyond the original list,
making it space-efficient.
Disadvantages:
• Slow performance: It has a worst-case and average-case time complexity of O(n²),
making it inefficient for sorting large lists.
• Too many comparisons: Regardless of the initial arrangement of elements, selection
sort always performs O(n²) comparisons, even if the list is nearly sorted.
• Not adaptive: Unlike insertion sort, which can perform faster on nearly sorted data,
selection sort doesn't take advantage of existing order.
• Poor scalability: As the dataset size increases, the algorithm's inefficiency becomes
more evident.
• Unstable sorting: Selection sort does not preserve the relative order of equal
elements, which can be a drawback in certain applications
Eg: refer from notes
Insertion sort:
• The list is divided into two parts – 1)sorted elements – left list
2)unsorted elements- right list.
1. Take each element one by one from the unsorted list.
2. Find the correct position for the element in the sorted part.
3. Insert the element at its appropriate place by shifting other elements if needed.
4. Repeat until the whole list is sorted.
Hence called insertion sort - each element is inserted into its correct place one at a time.
Working principle:
• Take the first element from the unsorted list.
• Compare it with each element in the sorted list.
• Shift elements to the right to make space for it.
• Insert it at the correct position.
• Repeat until all elements are sorted in ascending order.
Advantages:
• Efficient for small or nearly sorted datasets: Performs well when the input is small or
already mostly sorted, with a best-case time complexity of O(n).
• Adaptive nature: Unlike selection sort or bubble sort, insertion sort can stop early if
elements are already in order, making it faster in certain cases.
• Stable sorting algorithm: It preserves the relative order of equal elements, which can
be important in certain applications.
• Minimal memory usage: It doesn't require extra memory beyond the given dataset,
making it space-efficient
Disadvantages:
• Slow for large datasets: making it inefficient for sorting big lists.
• High number of shifts: Every time an element is inserted into its correct position,
other elements may need to shift, increasing computational effort.
• Not ideal for highly unsorted data: If the input is randomly ordered, insertion sort
performs many unnecessary comparisons and movements.
• Doesn't scale well: As data size increases, insertion sort becomes significantly slower
compared to advanced algorithms.
Eg: refer notes.
Time complexity:
• The amount of time an algorithm takes to process a given data can be called as time
complexity.
• Figuring out how fast or efficient different algorithms are , it requires complex math
and in-depth analysis.
• Constant Time Algorithms: If an algorithm doesn’t have loops, it takes the same
amount of time to run, no matter the data size.
• Linear Time Algorithms: If an algorithm has a single loop that runs n times, its
execution time increases as n increases.
• Quadratic Time Algorithms: If an algorithm has a loop inside another loop (nested
loops), the number of operations grows quickly—roughly n² times.
• Prioritizing Nested Loops: If there’s both a nested loop and a single loop, the overall
complexity is mainly determined by the nested loop.