CS计算机代考程序代写 Excel algorithm CS1-FULL-FALL2021

CS1-FULL-FALL2021

459

Sorting

460

why study sorting?
Sorting is a classic subject in computer science. There
are three reasons for studying sorting algorithms.

• First, sorting algorithms illustrate many creative
approaches to problem solving and these
approaches can be applied to solve other problems.

• Second, sorting algorithms are good for practicing
fundamental programming techniques using selection
statements, loops, methods, and arrays.

• Third, sorting algorithms are excellent examples to
demonstrate algorithm performance.

461

what data to sort?
The data to be sorted might be integers, floats, words, or
anything.

For simplicity, we will assume:

! data to be sorted are integers,
! data are sorted in ascending order, and
! data are stored in an list or a numpy array

462

Insertion Sort
myList = [2, 9, 5, 4, 8, 1, 6] // Unsorted

The insertion sort
algorithm sorts a
list of values by

repeatedly
inserting an

unsorted element
into a sorted

sublist until the
whole list is

sorted.

2 9 5 4 8 1 6

Step 1: Initially, the sorted sublist contains the
first element in the list . Insert 9 into the sublist .

2 9 5 4 8 1 6

Step2: The sorted sublist is {2, 9}. Insert 5 into
the sublist.

2 5 9 4 8 1 6

Step 3: The sorted sublist is {2, 5, 9}. Insert 4
into the sublist.

2 4 5 9 8 1 6

Step 4: The sorted sublist is {2, 4, 5, 9}. In sert 8
into the sublist.

2 4 5 8 9 1 6

Step 5: The sorted sublist is {2, 4, 5, 8, 9}. In sert
1 into the sublist.

1 2 4 5 8 9 6

Step 6: The sorted sublist is {1, 2, 4, 5, 8, 9}.
Insert 6 into the sublist.

1 2 4 5 6 8 9

Step 7: The entire list is now sorted.

463

Insertion Sort

2 9 5 4 8 1 6
2 9 5 4 8 1 6

2 5 9 4 8 1 6

2 4 5 8 9 1 6
1 2 4 5 8 9 6

2 4 5 9 8 1 6

1 2 4 5 6 8 9

myList = [2, 9, 5, 4, 8, 1, 6] // Unsorted

464

How to Insert?

The insertion sort
algorithm sorts a list

of values by
repeatedly inserting
an unsorted element
into a sorted sublist
until the whole list

is sorted.

[0] [1] [2] [3] [4] [5] [6]
2 5 9 4 list Step 1: Save 4 to a temporary variable currentElement

[0] [1] [2] [3] [4] [5] [6]
2 5 9 list Step 2: Move list[2] to list[3]

[0] [1] [2] [3] [4] [5] [6]

2 5 9 list Step 3: Move list[1] to list[2]

[0] [1] [2] [3] [4] [5] [6]

2 4 5 9 list Step 4: Assign currentElement to list[1]

465

https://visualgo.net/en/sorting

Insertion Sort Animation

466

Bubble Sort

2 5 9 4 8 1
2 5 4 9 8 1
2 5 4 8 9 1
2 5 4 8 1 9

(a) 1st pass

2 4 5 8 1 9
2 4 5 8 1 9
2 4 5 1 8 9

(b) 2nd pass

2 4 5 1 8 9
2 4 1 5 8 9

(c) 3rd pass

2 1 4 5 8 9

(d) 4th pass

2 9 5 4 8 1

(e) 5th pass

2 5 4 8 1 9

2 4 5 1 8 9

2 4 1 5 8 9

1 2 4 5 8 9

467

Bubble Sort Animation

https://visualgo.net/en/sorting

468

Quick Sort
Quick sort, developed by C. A. R. Hoare (1962), works
as follows:
• The algorithm selects an element, called the pivot, in

the array.
• Divide the array into two parts such that all the

elements in the first part are less than or equal to the
pivot and all the elements in the second part are
greater than the pivot.

• Recursively apply the quick sort algorithm to the first
part and then the second part.

469

Quick Sort

5 2 9 3 8 4 0 1 6 7

pivot

(a) The original array

4 2 1 3 0 5 8 9 6 7

pivot

(b)The original array is partitioned

0 2 1 3 4 (c) The partial array (4 2 1 3 0) is partitioned

0 2 1 3 (d) The partial array (0 2 1 3) is
partitioned

1 2 3

pivot

pivot

pivot

(e) The partial array (2 1 3) is
partitioned

470

Partition

5 2 9 3 8 4 0 1 6 7

pivot low high

(a) Initialize pivot, low, and high

5 2 9 3 8 4 0 1 6 7

pivot low high

(b) Search forward and backward

5 2 1 3 8 4 0 9 6 7

pivot low high

(c) 9 is swapped with 1

5 2 1 3 8 4 0 9 6 7

pivot low high

(d) Continue search

5 2 1 3 0 4 8 9 6 7

pivot low high

(e) 8 is swapped with 0

5 2 1 3 0 4 8 9 6 7

pivot low high

(f) when high < low, search is over 4 2 1 3 0 5 8 9 6 7 pivot (g) pivot is in the right place The index of the pivot is returned Merge Sort 2 9 5 4 8 1 6 7 2 9 5 4 8 1 6 7 split 2 9 split 5 4 2 split 9 5 4 8 1 6 7 8 1 6 7 2 9 merge 4 5 1 8 6 7 2 4 5 9 1 6 7 8 1 2 4 5 6 7 8 9 merge merge divide conquer