Searching & Sorting
Searching & Sorting
Dr. Chris Bourke
Department of Computer Science & Engineering
University of Nebraska¡ªLincoln
Lincoln, NE 68588, USA
cbourke@cse.unl.edu
2015/04/29 12:14:51
These are lecture notes used in CSCE 155 and CSCE 156 (Computer Science
I & II) at the University of Nebraska¡ªLincoln.
Contents
1. Overview
1.1. CSCE 155E Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2. CSCE 156 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
5
5
I. Searching
6
2. Introduction
6
3. Linear Search
3.1. Pseudocode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2. Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3. Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
7
7
7
4. Binary Search
4.1. Pseudocode:
4.2. Pseudocode:
4.3. Example . .
4.4. Analysis . .
7
8
9
9
9
Recursive
Iterative .
. . . . . .
. . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
1
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
5. Searching in Java
5.1. Linear Search . .
5.2. Binary Search . .
5.2.1. Preventing
5.3. Searching in Java:
5.4. Examples . . . .
. . . . . . . . . . .
. . . . . . . . . . .
Arithmetic Errors
Doing It Right . .
. . . . . . . . . . .
6. Searching in C
6.1. Linear Search . . . . . . . . .
6.2. Binary Search . . . . . . . . .
6.3. Searching in C: Doing it Right
6.3.1. Linear Search . . . . .
6.3.2. Binary Search . . . . .
6.4. Examples . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
11
11
11
12
13
13
.
.
.
.
.
.
14
14
15
16
16
16
17
II. Sorting
18
7. Bubble Sort
7.1. Basic Idea . .
7.2. Pseudocode .
7.3. Analysis . . .
7.4. Code Samples
.
.
.
.
19
19
20
20
20
.
.
.
.
21
21
22
22
22
.
.
.
.
23
23
24
24
24
.
.
.
.
25
25
26
26
27
11.Merge Sort
11.1. Basic Idea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11.2. Pseudocode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11.3. Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
29
29
29
30
8. Selection Sort
8.1. Basic Idea . .
8.2. Pseudocode .
8.3. Analysis . . .
8.4. Code Samples
9. Insertion Sort
9.1. Basic Idea . .
9.2. Pseudocode .
9.3. Analysis . . .
9.4. Code Samples
10.Quick Sort
10.1. Basic Idea . .
10.2. Pseudocode .
10.3. Analysis . . .
10.4. Code Samples
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
2
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
11.4. Code Samples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
30
12.Heap Sort
32
13.Tim Sort
32
14.Summary
33
15.In Practice: Sorting in Java
15.1. Considerations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15.2. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
33
33
34
16.In Practice: Sorting in C
16.1. Sorting Pointers to Elements . . . . . . . . . . . . . . . . . . . . . . . . .
16.2. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
35
35
37
A. Java: equals and hashCode methods
A.1. Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
38
38
B. Java: The Comparator Interface
B.1. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
B.2. Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
40
41
41
C. C: Function Pointers
C.1. Full Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
42
42
D. C: Comparator Functions
D.1. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
44
45
E. Master Theorem
46
References
46
List of Algorithms
1.
Linear Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
2.
Binary Search ¨C Recursive . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
3.
Binary Search ¨C Iterative . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
4.
Bubble Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
20
5.
Selection Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22
6.
Insertion Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
24
7.
Quick Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
26
8.
In-Place Partition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
26
3
9.
Merge Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
29
Code Samples
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
Java Linear Search for integers . . . . . . . . . . . . .
Java Recursive Binary Search for integers . . . . . . .
Java Iterative Binary Search for integers . . . . . . .
Java Search Examples . . . . . . . . . . . . . . . . .
C Linear Search for integers . . . . . . . . . . . . . .
C Recursive Binary Search for integers . . . . . . . .
C Iterative Binary Search for integers . . . . . . . . .
C Search Examples . . . . . . . . . . . . . . . . . . .
Java Bubble Sort for integers . . . . . . . . . . . . .
C Bubble Sort for integers . . . . . . . . . . . . . . .
Java Selection Sort for integers . . . . . . . . . . . .
C Selection Sort for integers . . . . . . . . . . . . . .
Java Insertion Sort for integers . . . . . . . . . . . .
C Insertion Sort for integers . . . . . . . . . . . . . .
Java Quick Sort for integers . . . . . . . . . . . . . .
Java Partition subroutine for integers . . . . . . . . .
C Quick Sort for integers . . . . . . . . . . . . . . . .
Java Merge Sort for integers . . . . . . . . . . . . . .
Java Merge for integers . . . . . . . . . . . . . . . . .
C Merge Sort for integers . . . . . . . . . . . . . . . .
C Merge Sort for integers . . . . . . . . . . . . . . . .
Handling Null Values in Java Comparators . . . . . .
Using Java Collection¡¯s Sort Method . . . . . . . . .
C Comparator Function for Strings . . . . . . . . . .
Sorting Structures via Pointers . . . . . . . . . . . .
Handling Null Values . . . . . . . . . . . . . . . . . .
Using C¡¯s qsort function . . . . . . . . . . . . . . . .
Java Student class . . . . . . . . . . . . . . . . . . .
Java Comparator Examples for the Student class . .
C Function Pointer Examples . . . . . . . . . . . . .
C Structure Representing a Student . . . . . . . . . .
C Comparator Function Examples for Student structs
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
11
11
12
13
14
15
15
17
20
21
22
23
24
25
27
28
28
30
30
31
32
34
34
35
36
37
37
38
41
42
45
45
List of Figures
1.
2.
Illustrative example of the benefit of ordered (indexed) elements, Windows 7 11
Unsorted Array . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
4
1. Overview
1.1. CSCE 155E Outline
1. Introduction
2. Linear Search (basic idea, example, code, brief analysis)
3. Binary Search (basic idea, example, code, brief analysis, comparative analysis)
4. Bubble Sort (Basic idea, example, code, brief analysis)
5. Selection Sort (Basic idea, example, code, brief analysis)
6. Quick Sort (Basic idea, example, comparative analysis only)
7. Function pointers
8. Sorting & Searching in C
9. Honors: Comparators, Searching, Sorting in Java
1.2. CSCE 156 Outline
1. Introduction
2. Linear Search (basic idea, pseudocode, full analysis)
3. Binary Search (basic idea, pseudocode, full analysis, master theorem application,
comparative analysis)
4. Bubble Sort (Basic idea, example, pseudocode, full analysis)
5. Selection Sort (Basic idea, example, pseudocode, full analysis)
6. Insertion Sort (Basic idea, example, pseudocode, full analysis)
7. Quick Sort (Basic idea, example, pseudocode, full analysis)
8. Merge Sort (Basic idea, example, pseudocode, full analysis)
9. Sorting Stability
10. Comparators in Java
11. Equals & Hash Code in Java
12. Searching in Java
13. Sorting in Java
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
- another word for searching for
- reverse searching and ad picture
- letter sorting word generator
- best car searching sites
- python searching list of dictionaries
- waste sorting slogan
- garbage sorting slogan
- garbage sorting for kids
- garbage sorting in china
- garbage sorting why
- sorting for kids
- best college searching websites