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

COMP2521
Data Structures & Algorithms

Week 8.1
Sorting Overview

 

1

In this lecture

Why?

Sorting elements can help us speed up searching, and
arranges data in a useful way (for both humans and
computers)

What?

Overview of sorting

2

Sorting

Sorting refers to arranging a collection of items in order.

E.G. Sorting arrays, linked lists, files
Typically sorted in either ascending or descending order

 
Typically items are sorted based on an ordering relation of that property:

For numbers, you sort them numerically
For characters, you sort them alphabetically

 

3

The Sorting Problem

For array a[N], we would sort it by saying lo = 0, hi = N-1
 

4 . 1

The Sorting Problem

Pre-conditions:

lo, hi are valid indexes (i.e. 0 <= lo < hi <= N-1) a[lo..hi] contains defined values of type Item   Post-conditions: a[lo..hi] contains the same set of values as before the sort foreach i in lo..hi-1, it's true that a[i] <= a[i + 1] 4 . 2 The Sorting Problem Generally speaking, most algorithms do a sort "in-place" (consists of doing a series of intelligent swapping between elements). These swaps help move unsorted items to the beginning of the array. 4 . 3 Sorting Algorithm Properties Stable sort: Maintains order for duplicates: Given that x == y, if x precedes y in an unsorted list, then x precedes y in the sorted list Adaptive sort: Performance is affected by actual values of items Best, average, and worst case performance differs E.G. Bubble sort is adaptive   5 Sorting Complexity Three main cases we focus on when sorting: Random order Sorted order Reverse order When we look at an algorithm, we are trying to minimise: The number of comparisons between items The number of swaps between items Most sorts are of two types of complexity: O(n^2) -> This is totally fine for small numbers (hundreds)
O(n * log(n)) -> This is ideal

 
6

Sorting Programming
// we deal with generic Items
typedef SomeType Item;

// abstractions to hide details of Items
#define swap(A,B) {Item t; t = A; A = B; B = t;}

// Sorts a slice of an array of Items, a[lo..hi]
void sort(Item a[], int lo, int hi); // TODO

// Check for sortedness (to validate functions)
bool isSorted(Item a[], int lo, int hi)
{
for (int i = lo; i < hi; i++) { if (!less(a[i], a[i+1])) return false; } return true; } 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 7 Feedback 8