1 / 3

1 / 3The complexity of different algorithms varies: O(n), Ω(n2), Θ(n·log2(n)), …

Různé algoritmy mají různou složitost: O(n), Ω(n2), Θ(n·log2(n)), …

DSA

Různé algoritmy

mají různou složitost

X36DSA 2005



DSA

The complexity

of different algorithms

varies

X36DSA 2005



Stable sort

Andrew Cook

Amundsen

Brown

Barbara

Charles Cook

sorted

Sort by family name

only

Amundsen

Amundsen

Brown CookBrown

Charles

Charles

Barbara Barbara

Andrew

Andrew

Amundsen

Charles

Barbara

Andrew AmundsenAmundsen

CookCookCookBrown Brown Brown

Barbara Charles Andrew

Charles Andrew Barbara

sorted sorted

X36DSA 2005



Unstable sort

Andrew Cook

Amundsen

Brown

Barbara

Charles Cook

sorted

Sort by family name

only

Amundsen

Amundsen

Brown CookBrown

Charles

Charles

Barbara Barbara

Andrew

Andrew

Amundsen

Charles

Barbara

Andrew AmundsenAmundsen

CookCookCookBrown Brown Brown

Barbara

Charles

Andrew Charles

Andrew Barbara

QuickSort

sorted

X36DSA 2005



Sorting

Heap Sort

Řazení haldou

X36DSA 2005



Heap

A

B D

EJM

KO R

T

UZ

a

cb a cab

Heap

Heaprule

X36DSA 2005



Heap

a

cb

a

Terminology

...... predcessor, parent of b c

b c ...... successor, child of, a

...... předchůdce, rodič

...... následník, potomek

A

BD

...... (heap) top ...... vrchol (haldy)

X36DSA 2005



Heap in an array

1 2 3 4 5 6 7 8 9 10 11 12 A B D EJM KO RT UZ

A

B D

EJM

KO R

T

UZ

5

109

1

6

2

7

3

8

4

1211

r

ts

k

2k 2k+1

r s t

Heap stored in an array

k 2k 2k+1

succesorssuccesors

X36DSA 2005

D

E

K



Repair a heap

A

B D

EJM

KO R

T

UZ

B

JM

O R

T

Z

Top removed (1)

U

Swap B ↔ U

remove top

last first→

1

1

2

2

Ainsert top

3

U > B, U > D, B < D

X36DSA 2005



Repair a heap

B

D

EJM

KO R

T

Z

U

Swap J ↔ U

Top removed (2)

B

D

E

J

M

KO R

T

Z

U

Swap K ↔ U

A A

insert top - continues3

U > M, U > J, J < M U > K, U > R, K < R

X36DSA 2005



Repair a heap

B

D

E

J

M K

O R

T

Z U

Top removed (3)

Heap, OK

Ainsert top - done3

X36DSA 2005



Repair a heap

Top removed II (1)

B

D

E

J

M K

O R

T

Z U

DJ

M K

O

R

T

Z U

E

R > J, R > D, D < J

Aremove top

1

last first→2

1

Swap D ↔ R

insert top3

B A

X36DSA 2005



Repair a heap

D

J

M K

O

R

T

Z U

E

Swap E ↔ R

D

J

M K

O

RT

Z U

E

Heap, OK

Top removed II (2) Top removed II (3)

insert top - continues

B A

R < T, R > E

3

B A

insert top - done3

X36DSA 2005



Heap Sort

AB DEJ M KOR TU Z

Sorted

for (i = 0; i < n; i++) a[i] = “Remove top”;Create a heap

Unsorted

BDEJKORUZ AMT

A

B D

EJM

KO R

T

UZ

M

O

R

TZ U

I

II III

IV

BDEJ AK

X36DSA 2005



Heap recursive property

A

B D

EJM

KO R

T

UZ

is a heap is a heap and is a heap

X36DSA 2005



Create a heap

A B

Z

heapheap

not a heap

Z > A or Z > B

Swap: Z ↔ min(A,B)

X36DSA 2005



Create a heap

BZ

heap

not a heapnot a heap

A

CFheap heap

X36DSA 2005



Create a heap

A

B

D

E

J

M KO

R

T

U

Z

1 Make a heap here…

2

3

4

5

6

… make a heap here…




… make a heap here.

3 2

45

6

1

X36DSA 2005



Heap in an array

1 2 3 4 5 6 7 8 9 10 11 12 A B D EJM KO RT UZ

A

B D

EJM

KO R

T

UZ

5

109

1

6

2

7

3

8

4

1211

r

ts

k

2k 2k+1

r s t

Heap stored in an array

k 2k 2k+1

succesorssuccesors

X36DSA 2005



Create a heap in an array

D

E

J

K

M O

R

T

U ZB

A

21

3456789

101112

A

B

D

E

J

M

KO

R

T

UZ

5

109

1

6

2

7

3

8

4

1211

Not a heapUnsorted

123456

12

34

56

X36DSA 2005




D

E

J

K

M O

R

T

U Z

21

3456789

101112

A

B D E

J

K

M O

R

T

U Z

A

B D E

J

K

M O

R

T

U Z

B

A

21

3456789

101112

21

3456789

101112

D E

J

K

M

O

R

T

U

Z

B

A

21

3456789

101112

D

E

J

K

M

O

R

T

U

Z

B

A

21

3456789

101112

12

34

5

Creating a heap

X36DSA 2005




D

E

J K

M

O

R

T

U

Z

B

A21

3456789

101112

D

E

J

K

M

O

R

T

U

Z

BA

21

3456789

101112

AB

D

E

JM

KO

R

T

U

Z

5

109

1

6

2

7

3

8

4

1211

6

HeapCreating a heap

X36DSA 2005



Heap sort

A B D EJM KO RT UZ

Heap

AB D EJM KO RTU Z 1 2 3 4 5 6 7 8 9 10 11 12

AB D EJ M K O RT UZ

A B D EJM KO RT UZ

heap

Step 1

X36DSA 2005



Heap Sort

ABDEJ MK OR T UStep k

ABDEJM

K

OR T

ABDEJM OR T UZ

1 2 3 4 5 6 7 8 9 10 11 12

heap k

Z U

Z

K

X36DSA 2005



Heap Sort

// array: a[1]...a[n] !!!!void heapSort(Item a[], int size) { int i, j, // create a heap for (i = size/2; i > 0; i--) repairTop(array, i, size);

// sort for (i = size; i > 1; i--) { swap(a, 1, i); repairTop(array, 1, i-1); }}

X36DSA 2005



Heap Sort

// array: a[1]...a[n] !!!!!!void repairTop(Item a[], int top, int bott) { int i = top; // a[2*i] and a[2*i+1] int j = i*2; // are successors of a[i] Item topVal = a[top]; // try to find a successor < topVal if ((j < bott) && (a[j] > a[j+1])) j++; // while (successors < topVal) // move successors up while ((j <= bott) && (topVal > a[j])) { a[i] = a[j]; i = j; j = j*2; // skip to next successor if ((j < bott) && (a[j] > a[j+1])) j++; } a[i] = topVal; // put the topVal }

X36DSA 2005



Heap Sort

repairTop operation worst case ... log2(n) (n=heap size) create a heap ...

log2(n/2) + log2(n/2+1) + ... + log2(n) (n/2)(log2(n)) = (n·log(n))

sort ... n-1 repairTop operations, worst case:

n/2 repairTop operations

log2(n) + log2(n-1) + ... + 1 n · log2(n) =

(n·log2(n))

total ... create heap + sort =

Asymptotic complexity of Heap sort is (n·log2(n)) It is not a stable sort

X36DSA 2005

But even best case = (n·log2(n))

(n·log2(n))



Sorting

Merge Sort

Řazení sléváním

X36DSA 2005



Merge Sort

A

B

D E J

MK

O R

T U Z

A

B

D E J

MK

O R

T U Z

A

B

D E J

MK

O R

T U Z

A

A B

Merge two sorted arrays Compare elements

X36DSA 2005



Merge Sort

A

B

D E J

MK

O R

T U Z

A B D

A

B

D E J

MK

O R

T U Z

A B D E

A

B

D E J

MK

O R

T U Z

A B D E J

Merge two sorted arrays – cont.

X36DSA 2005



Merge Sort

A

B

D E J

MK

O R

T U Z

A B D E J K

A

B

D E J

MK

O R

T U Z

A B D E J K M

A

B

D E J

MK

O R

T U Z

A B D E J K M O

Merge two sorted arrays

X36DSA 2005



Merge Sort

A

B

D E J

MK

O R

T U Z

A B D E J K M O R

A

B

D E J

MK

O R

T U Z

A B D E J K M O R T U Z

Merge two sorted arrays - cont

Sorted

Copy the rest

X36DSA 2005



Divide & Conquer! Divide et Impera!

The problem

The problem

The solution The solution

The problem The problem

The solution

Solve the subproblem Solve the subproblem

their work

our work

Merge!Merge!

Divide!

X36DSA 2005

Processseparately

Sorted



Merge Sort

A B D E J K M O R T U Z

AB DE JK M ORTUZ

BK M TUZ A DE J OR

AB D E JMK O RT U Z

Unsorted

Divide!

Processseparately

Conquer! Merge!

Sort! Sort!

X36DSA 2005

Sorted



Merge Sort

BK M TUZ A DE J OR

AB D E JMK O RT U Z

Unsorted

Divide!

Divide!

…… …… …… ……Divide!

K UZ B M T AE J D OR

K U Z B M T A E J ROD

Merge!

Merge!

Merge!

X36DSA 2005



Merge Sort

void mergeSort (int a[], int aux[], int low, int high) { int half = (low+high)/2; int i; if (low >= high) return; // too small! // sort mergeSort(a, aux, low, half); // left half mergeSort(a, aux, half+1, high); // right half merge(a, aux, low, high); // merge halves // put result back to a for (i = low; i <= high; i++) a[i] = aux[i];

// optimization idea: /* swapArray(a, aux) */ // better to swap // references to a & aux! }

X36DSA 2005



Merge Sort

void merge(int in[], int out[], int low, int high) { int half = (low+high)/2; int i1 = low; int i2 = half+1; int j = low;

// compare and merge while ((i1 <= half) && (i2 <= high)) { if (in[i1] <= in[i2]) { out[j] = in[i1]; i1++; } else { out[j] = in[i2]; i2++; } j++; } // copy the rest while (i1 <= half) { out[j] = in[i1]; i1++; j++; } while (i2 <= high) { out[j] = in[i2]; i2++; j++; }}

X36DSA 2005



Merge Sort

Asymptotic complexity

log2(n) timesDivide! ........

Asymptotic complexity of MergeSort is (n·log2(n))

log2(n) timesMerge! ........

Divide! ........ (1) operationsMerge! ........ (n) operations

Total ........ (n)· (log2(n)) = (n·log2(n)) operations

X36DSA 2005



Merge Sort

Stability

Divide! ........ Does not move the elements Nepohybuje prvky

Merge! ….... “ if (in[i1] <= in[i2]) { out[j] = in[i1]; …” process the left element first when merging equal values Zařaď nejprve levý prvek když slučuješ stejné hodnoty

MergeSort is a stable sort

X36DSA 2005



Sorting

Radix Sort

Přihrádkové řazení

X36DSA 2005



Radix sort

DaD

DbD

DCaaDb

aDDCCC

aDCDDb

babbbC

aCb

Cbb

Cba

5

109

1

6

2

7

3

8

4

1211

13

B_ _ a _ _ b _ _ C _ _ D

Cbb DaDaDb

DCa CCCaDD

DDbaDCbbC

babDbD

Cba1 23

4 56

789

1011

12

aCb13

12

567

34

1098

1211

13

Unsorted

Sort by 3rd digit

X36DSA 2005



Radix sort

5

109

1

6

2

7

3

8

4

1211

13

B_ a _ _ b _ _ C _ _ D_Cbb

DaD

aDb

DCa

CCC

aDD

DDb

aDCbbC

bab

DbD

Cba

aCb

12

56

734

10

98

1211

13

Sorted by 3rd digit Sort by 2nd digit

DCaCbaCbb

aDbDDb

babaCbCCC aDCbbC

DaD

aDDDbD

123

45

678 910

11

1213

X36DSA 2005



Radix sort

5

109

1

6

2

7

3

8

4

1211

13

Ba _ _ b _ _ C _ _ D_ _

12

56

7

34

10

98

1211

13

Sorted by 2nd digit Sort by 1st digit

DCa

CbaCbb

aDbDDb

bab

aCbCCC

aDC

bbC

DaD

aDD

DbDbab DaDCba

CbbbbC DbDDCa

aCb

CCCaDb

DDbaDCaDD

1 2345 6

7

8

910

111213

Sorted!

X36DSA 2005

Example



Radix sort implementation

DaD

DbD

DCaaDb

aDDCCC

aDCDDb

babbbC

aCb

Cbb

Cba

5

109

1

6

2

7

3

8

4

1211

13

B_ _ a

_ _ b

_ _ C

_ _ D

DaD

aDb

DCa

CCC

aDD

DDb

aDCbbC

bab

DbD

Cba

13

4

5

7

89

10

12

aCb13

12

567

34

1098

1211

13

Unsorted

Sorted by 3rd digit

2611

start & end next

abC

6

Cbb

4152

1213911

123456789

10111213

D

7128

111090

13000

3

Array data structure

3

Example

X36DSA 2005



d digits ............ d loops

loop ............

RadixSort never changes order of equal values

d << n ..….

(n) operations

Asymptotic complexity of RadixSort is (n)

Summary

(d·n) operationstotal ............

(n) operations

Přihrádkové řazení nemění pořadí stejných hodnot

It is a stable sort

X36DSA 2005



DSA

Různé algoritmy

mají různou složitost

X36DSA 2005



DSA

The complexity

of different algorithms

varies

X36DSA 2005

Date post:	19-Mar-2016
Category:	Documents
Upload:	willis
View:	42 times
Download:	2 times

1 / 3

Documents