CS计算机代考程序代写 data structure Java algorithm COMP2521

COMP2521
Data Structures & Algorithms

Week 8.2
Basic Sorts

 

1

In this lecture

Why?

There are a handful of easy-to-implement, yet not-the-
fastest sorts that are very useful to understand

What?

Bubble Sort
Selection Sort
Insertion Sortt

2

O(n^2) sorts

A few of the popular basic sorting algorithms are:

Bubble Sort
Selection Sort
Insertion Sort

These sorting algorithms all have an O(n^2) worst-case time
complexity. Later we will discuss faster ones.

 

3

Bubble Sort

Moves through the list pair-wise, swapping pairs in the wrong order.
Repeats this process until list is sorted.

Worst case: O(n^2)
Average case: O(n^2)
Best case: O(n)
Adaptive: Yes
Stable: Yes

4 . 1

Bubble Sort

4 . 2

Bubble Sort

void bubbleSort(int a[], int lo, int hi) {
int i, j, nswaps;
for (i = lo; i < hi; i++) { nswaps = 0; for (j = hi; j > i; j–) {
if (less(a[j], a[j-1])) {
swap(a[j], a[j-1]);
nswaps++;
}
}
if (nswaps == 0) break;
}
}

1
2
3
4
5
6
7
8
9

10
11
12
13

4 . 3

Selection Sort

Find the smallest element, swap it with first array slot.
Find the second smallest element, swap it with second array slot.

Etc, until traversed through entire array.

Worst case: O(n^2)
Average case: O(n^2)
Best case: O(n^2)
Adaptive: No
Stable: No

5 . 1

Selection Sort

Source: https://algorithms.tutorialhorizon.com/selection-sort-java-implementation/
5 . 2

Selection Sort

void selectionSort(int a[], int lo, int hi) {
int i, j, min;
for (i = lo; i < hi-1; i++) { min = i; for (j = i+1; j <= hi; j++) { if (less(a[j],a[min])) min = j; } swap(a[i], a[min]); } } 1 2 3 4 5 6 7 8 9 10 5 . 3 Insertion Sort Take first element and treat as sorted array; take next element and insert into sorted part of array so that order is preserved; repeat until whole array is sorted Worst case: O(n^2) Average case: O(n^2) Best case: O(n) Adaptive: Yes Stable: Yes 6 . 1 Insertion Sort 6 . 2 void insertionSort(int a[], int lo, int hi) { int i, j, val; for (i = lo+1; i <= hi; i++) { val = a[i]; for (j = i; j > lo; j–) {
if (!less(val,a[j-1])) break;
a[j] = a[j-1];
}
a[j] = val;
}
}

1
2
3
4
5
6
7
8
9

10
11

Insertion Sort

6 . 3

Sorting Summary

7

Sorting Linked Lists

Most sorts assume we work on arrays. However, we can still sort on
linked lists.

 

8

Feedback

9