Sorting
嚜澠ntroduction to Programming
(in C++)
Sorting
Jordi Cortadella, Ricard Gavald角, Fernando Orejas
Dept. of Computer Science, UPC
Sorting
? Let elem be a type with a ? operation, which is a
total order
? A vector v is (increasingly) sorted if
for all i with 0 ? i ? v.size()-1, v[i] ? v[i+1]
? Equivalently:
if i ? j then v[i] ? v[j]
? A fundamental, very common problem: sort v
Order the elements in v and leave the result in v
Introduction to Programming
? Dept. CS, UPC
2
Sorting
9
-7
0
1
-3
4
3
8
-6
8
6
2
-7
-6
-3
0
1
2
3
4
6
8
8
9
? Another common task: sort v[a..b]
9
9
-7
-7
Introduction to Programming
0
a
1 -3
0
a
-3
1
4
b
3
8
-6
8
6
2
3
b
4
8
-6
8
6
2
? Dept. CS, UPC
3
Sorting
? We will look at four sorting algorithms:
每
每
每
每
Selection Sort
Insertion Sort
Bubble Sort
Merge Sort
? Let us consider a vector v of n elems (n = v.size())
每 Insertion, Selection and Bubble Sort make a number of
operations on elems proportional to n2
每 Merge Sort is proportional to n﹞log2n: faster except for
very small vectors
Introduction to Programming
? Dept. CS, UPC
4
Selection Sort
? Observation: in the sorted vector, v[0] is the smallest
element in v
? The second smallest element in v must go to v[1]#
? # and so on
? At the i-th iteration, select the i-th smallest element
and place it in v[i]
Introduction to Programming
? Dept. CS, UPC
5
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related searches
- letter sorting word generator
- waste sorting slogan
- garbage sorting slogan
- garbage sorting for kids
- garbage sorting in china
- garbage sorting why
- sorting for kids
- why waste sorting is important
- sorting activities for preschoolers
- sorting games for kindergarten
- color sorting activities for preschoolers
- garbage sorting china