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.

Google Online Preview   Download