当前位置：网站首页>CPT 102_LEC 17

CPT 102_LEC 17

2022-06-11 01:52:00 【NONE_WHY】

1. Binary Search

见 INT 102_LEC 03_1.2

2. Sorting

2.1. Ways of sorting

2.1.1. Selecting sorts

Find the next largest/smallest item and put in place
Builds the correct list in order

2.1.2. Inserting Sorts

For each item, insert it into an ordered sublis
Builds a sorted list, but keeps changing it

2.1.3. Compare and Swap Sorts

Find two items that are out of order, and swap them
Keeps “improving” the list

2.1.4. Radix Sorts

Look at the item and work out where it should go
Only works on some kinds of values

2.2. Analysing Sorting Algorithms

Efficiency
Requirements on Data
Space Usage

2.3. Implementation

2.3.1. Selection Sort

Code

public void selectionSort(E[ ] data, int size, Comparator<E> comp){
    // for each position, from 0 up, find the next smallest item 
    // and swap it into place
    for (int place=0; place<size-1; place++){
        int minIndex = place;
        for (int sweep=place+1; sweep<size; sweep++){
            if (comp.compare(data[sweep], data[minIndex]) < 0)
                minIndex=sweep;
            }
        swap(data, place, minIndex);
    }
}

Analysis

2.3.2. Bubble Sort

Code

public void bubbleSort(E[] data, int size, Comparator<E> comp){
    // Repeatedly scan array, swapping adjacent items if out of order
    // Builds a sorted region from the end
    for (int top=size-1; top>0; top--){
        for (int sweep=0; sweep<top; sweep++){
            if (comp.compare(data[sweep], data[sweep+1]) >0) {
                swap(data, sweep, sweep+1);
            }
        }
    }
}