Sorting in
Linear Time
Efficient algorithms for fast
data arrangement
Group members
1. Esekon Napokol Mark 6. Alex Kipkoech
2. Stephen Ahurah 7. Derrick Chasimba
3. Stanley Daud 8. Joan Mitei
4. Zipporah Nekesa 9. Eric Mekala
Wanjala 10. Lenah Wanjala
5. Soud Omar 11. Grace Tarbei
GROUP 4: MODULE 4 PRESENTATION
Importance of
Sorting in
Algorithms
Why is sorting essential 1. Efficiency Improvement
in the design and Sorting enables faster problem-
analysis of algorithms? solving techniques like binary search,
reducing search time significantly.
2. Simplified Problem Solving
Sorting makes finding median, mode,
duplicates, and quick access to key
values easier.
3. Data Organization
Sorting organizes data for structured
applications like database indexing
and file retrieval.
4. Algorithm Support and Analysis
Why is sorting essential Many advanced algorithms, like those for
in the design and searching, clustering, or scheduling, rely
analysis of algorithms? on sorting. Algorithms like merge sort and
Cont... quicksort are key examples in divide-and-
conquer strategies.
5. Helps Analyze Efficiency: Sorting
algorithms are often used to study time and
space complexity. Comparing algorithms
like bubble sort, merge sort, and quicksort
helps us understand different techniques
and trade-offs.
6. Enables Efficient Comparisons: Once
data is sorted, tasks like finding duplicates
or comparing datasets can be done more
efficiently, often in O(n) time, improving
overall algorithm performance.
Linear Time
Sorting
Algorithms
What is a linear- Definition and Efficiency
Linear-time sorting sorts data in O(n) time, growing
time sorting proportionally with input size, enabling efficient
processing.
algorithm, and why
is it important? Importance for Large Data
These algorithms handle very large datasets efficiently
compared to slower O(n log n) or O(n²) comparison sorts.
Techniques Used
Linear-time sorting uses techniques like counting
occurrences, digit-wise sorting, and bucket distribution to
organize data.
Examples of Algorithms
Popular linear-time sorting algorithms include Counting
Sort, Radix Sort, and Bucket Sort, optimized for specific
data features.
Counting Sort
How does Counting Counting Element Occurrences
Counting Sort counts the occurrences of each
Sort work? unique element within the input array efficiently.
Position Calculation
The count array is modified to determine the
position of each element in the sorted output array.
Building Sorted Output
Elements are placed into the output array in sorted
order using the modified count array.
Efficiency and Limitations
Counting Sort is efficient for small ranges but less
suitable for large ranges due to auxiliary array size.
Practical Example: Sorting
Exam Scores
You have a list of exam scores for 10 students:
[4, 2, 2, 8, 3, 3, 1, 5, 6, 7]
Steps
1. Counting Occurrences
The algorithm counts the frequency of each exam score using a count
array to track occurrences.
2. Determining Positions
The count array helps determine the correct positions for each score in
the sorted output list.
3. Sorted Output
The final sorted list organizes exam scores efficiently, demonstrating
Counting Sort's effectiveness for limited ranges.
Sorted Output:
[1, 2, 2, 3, 3, 4, 5, 6, 7, 8]
Radix Sort
How does Radix Digit-by-Digit Processing
Radix Sort processes numbers digit by digit, starting from
Sort differ from starting from the least significant digit (LSD) or the most
significant digit (MSD), depending on the variant used.
Counting Sort?
Use of Stable Subroutine
Start from the least significant digit.
Use Counting Sort to sort the numbers based on the current
digit.
Move to the next digit and repeat until all digits are
processed.
Algorithm Efficiency
Radix Sort runs in O(d*(n+k)) time, efficient for large integer or
string data sets.
Stability in Sorting
Radix Sort maintains relative order of elements with the same
key, ensuring stable sorting results.
Practical Example: Sorting
Phone Numbers
Phone numbers: [415, 212, 303, 350, 123, 423, 556],
Initial Digit Sorting
Sorting starts with the least significant digit using Counting Sort to
rearrange phone numbers effectively.
Result: [212, 303, 123, 415, 556]
Progressive Digit Sorting
Sorting proceeds digit by digit from right to left until all digits are
sorted to get final order.
Result: [123, 212, 303, 415, 556]
Advantages of Radix Sort
Radix Sort is efficient for sorting numbers with a limited number of
digits like phone numbers or zip codes.
Bucket Sort
What is Bucket
Sort?
Bucket Sort is a sorting algorithm that works
Efficiency and Usage
by distributing elements into several groups Bucket Sort runs in O(n + k) time, where n is the number
of elements and k is the number of buckets. It is most
(called “buckets”), then sorting each bucket
efficient when the input data is uniformly distributed over
individually, and finally combining all buckets a known range, ensuring balanced bucket distribution.
to get the sorted result/output
Practical Example:Bucket Division
Sorting
Consider a list: [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68]
Floating-Point
The range [0, 1] is divided into equal intervals or buckets to categorize the
Numbers floating-point numbers.
Step 1: Convert elements to integers
Convert the floating-point numbers into integers by multiplying by 10 and
remaining with integers.
[7, 1, 3, 2, 7, 9, 2, 1, 2, 6]
Step 2: Sorting Within Buckets
Create 10 buckets and place each number into the appropriate bucket based on its
value.
1 2 3
1 2
2
6 7 9
7
Step 3:Concatenate Buckets
Final sorted list: [0.12, 0.17, 0.21, 0.23, 0.26, 0.39, 0.68, 0.72, 0.78, 0.94]
Comparison of
Linear-Time
Sorting Algorithms
Counting Sort Overview
How do Counting Sort, Counting Sort efficiently sorts integers within a limited
Radix Sort, and range using counting arrays, achieving O(n + k) time
complexity.
Bucket Sort compare?
Radix Sort Efficiency
Radix Sort handles large datasets of numbers or strings
with fixed digit length, sorting in O(d * (n + k)) time.
Bucket Sort Usage
Bucket Sort is suited for uniformly distributed data,
organizing elements into buckets for sorting in O(n + k)
time.
Choosing the Right Sort
Effectiveness depends on input data's range, distribution,
and structure.
How do Counting Sort, Radix Sort, and Bucket Sort
compare?
MERGE SORT
ALGORITHM
What is merge Merge sort algorithm operates on the principal of
“divide and conquer”. It recursively divides an
sort? unsorted list into smaller sub lists until each sub list
contains only one element (which is considered
sorted). These values are then compared against
each other and merged back together in the correct
order.
QuickSort
Algorithm
What is quick sort QuickSort is a sorting algorithm based on the Divide and
Conquer that picks an element as a pivot and partitions
algorithm? the given array around the picked pivot by placing the
pivot in its correct position in the sorted array.
There are mainly three steps in the algorithm:
Choose a Pivot: Select an element from the array as the
pivot. The choice of pivot can vary (e.g., first element,
last element, random element, or median).
Partition the Array: Re arrange the array around the
pivot. After partitioning, all elements smaller than the
pivot will be on its left, and all elements greater than the
pivot will be on its right. The pivot is then in its correct
position, and we obtain the index of the pivot.
Recursively Call: Recursively apply the same process to
the two partitioned sub-arrays (left and right of the
pivot).
Base Case: The recursion stops when there is only one
element left in the sub-array, as a single element is
already sorted.
BINARY SEARCH
ALGORITHM
What is binary A binary search uses a similar “divide and conquer”
method to a merge sort, to find a specific value in a
search algorithm? list. It works with data that has already been sorted.
The process is as follows:
The specific value to be found is compared to the
median(middle) value in the list.
If the specific value is lower than the median, then
the second half of the list is ignored and the process
is repeated with the first half.
If the specific value is higher than the median, then
the first half of the list is ignored and the process is
repeated with the second half.
This process is repeated until the desired value has
been found.
Thank you.