Electronics and Computer Engineering
School of Electronics and Telecommunications
Hanoi University of Science and Technology
1 Dai Co Viet - Hanoi - Vietnam
Data structure and Algorithms
Sorting – Giải thuật sắp xếp
Thanh-Hai Tran
2020 2
Outline
Introduction
Basic sorting algorithms
Selection sort (Sắp xếp chọn)
Bubble sort (Sắp xếp nổi bọt)
Insertion (Sắp xếp chèn)
Advanced sorting algorithms
Quick sort (Sắp xếp nhanh)
Heap sort (Sắp xếp vun đống )
Merge sort (Sắp xếp trộn)
Exercises
References
2020 3
Introduction
Sorting problem:
Given a set of N elements A1, A2, …, AN.
Arrange the elements so that they are placed in some
relevant order (ascending or descending)
Example:
Input:
Output:
Sorting types:
Internal sorting: data stored in computer memory
External sorting: data stored in files
Sorting
A1, A2,…, ANA’1, A’2,…, A’N
2020 4
Sorting on Multiple Keys
In real-world applications, it is desired to sort
arrays of records using multiple keys
Examples: Employees of a big company are sorted
by Department first then name in alphabetical order.
Notes:
Data records can be sorted based on a property. Such
a component or property is called a sort key
A sort key can be defined using two or more sort keys.
In such a case, the first key is called the primary sort
key, the second is known as the secondary sort key,
etc
2020 5
Sorting on Multiple Keys
In real-world applications, it is desired to sort
arrays of records using multiple keys
Examples:
Telephone directories in which names are sorted by
location, category (business or residential), and then in
an alphabetical order
In a library, the information about books can be sorted
alphabetically based on titles and then by authors’
names
Customers’ addresses can be sorted based on the
name of the city and then the street