Data Structures and Algorithm
(CC-2042)
Lecture 7
E N G R. D R B I L A L A S H FA Q A H M E D
S C H O O L O F S Y S T E M S A N D T E C H N O LO GY ( S S T )
C O M P U T E R S C I E N C E FA C U LT Y
, Sorting Algorithms
Sorting is the process of arranging items in a specifi
sequence or order, most commonly ascending or
descending. In data processing, sorting helps organ
data, making it easier to locate, manage, and retrie
information.
Formally
Input: A sequence of n numbers <a1,a2,…,an>
Output: A reordering <a’1,a’2,…,a’n> of the sequen
that a’1 ≤ a’2 ≤ … ≤ a’n
Given the input <6, 3, 1, 7>, the algorithm should p
<1, 3, 6, 7>
Called an instance of the problem
09/06/2025 DS
,Why?
Sorting prices from lowest to highest
We encounter sorting almost Sorting flights from earliest to latest
everywhere: Sorting grades from highest to lowest
Sorting songs based on artist, album, playlist, etc.
Enhanced Data Accessibility: Organized data is easier to search
and manipulate.
Foundation for Other Algorithms: Many algorithms (like binary
search) require sorted data to function correctly.
Applications: Sorting is used across various fields including
database management, scheduling tasks, file organization, and dat
processing.
09/06/2025 DS
, Types of Sortin
Algorithms
§ Comparison-Based Sorting:
Definition: These algorithms sort data by co
elements to each other. They are suitable fo
general-purpose sorting
Examples: Quick Sort, Merge Sort, Heap So
Characteristics: They typically have time
complexities that are logarithmic, or quadra
on the number of comparisons made.
§ Non-Comparison-Based Sorting:
Definition: These algorithms sort without co
elements directly, often using the propertie
elements (like counting occurrences or proc
digits).
Examples: Counting Sort, Radix Sort, Bucke
Characteristics: These are highly efficient fo
scenarios, especially for sorting integers wi
limited range.
09/06/2025 DS
(CC-2042)
Lecture 7
E N G R. D R B I L A L A S H FA Q A H M E D
S C H O O L O F S Y S T E M S A N D T E C H N O LO GY ( S S T )
C O M P U T E R S C I E N C E FA C U LT Y
, Sorting Algorithms
Sorting is the process of arranging items in a specifi
sequence or order, most commonly ascending or
descending. In data processing, sorting helps organ
data, making it easier to locate, manage, and retrie
information.
Formally
Input: A sequence of n numbers <a1,a2,…,an>
Output: A reordering <a’1,a’2,…,a’n> of the sequen
that a’1 ≤ a’2 ≤ … ≤ a’n
Given the input <6, 3, 1, 7>, the algorithm should p
<1, 3, 6, 7>
Called an instance of the problem
09/06/2025 DS
,Why?
Sorting prices from lowest to highest
We encounter sorting almost Sorting flights from earliest to latest
everywhere: Sorting grades from highest to lowest
Sorting songs based on artist, album, playlist, etc.
Enhanced Data Accessibility: Organized data is easier to search
and manipulate.
Foundation for Other Algorithms: Many algorithms (like binary
search) require sorted data to function correctly.
Applications: Sorting is used across various fields including
database management, scheduling tasks, file organization, and dat
processing.
09/06/2025 DS
, Types of Sortin
Algorithms
§ Comparison-Based Sorting:
Definition: These algorithms sort data by co
elements to each other. They are suitable fo
general-purpose sorting
Examples: Quick Sort, Merge Sort, Heap So
Characteristics: They typically have time
complexities that are logarithmic, or quadra
on the number of comparisons made.
§ Non-Comparison-Based Sorting:
Definition: These algorithms sort without co
elements directly, often using the propertie
elements (like counting occurrences or proc
digits).
Examples: Counting Sort, Radix Sort, Bucke
Characteristics: These are highly efficient fo
scenarios, especially for sorting integers wi
limited range.
09/06/2025 DS
