Złoż ono ci obliczeniowe algorytmów sortowania ś

Algorytm

l. porówna l. przestawie ń

ń

2

n − n

2

n

prosty wybór

+ (

3 n − ) 1

2

4

2

n − n

2

n + 3 n − 4

proste wstawianie

−1

2

2

2

n − n

prosta zamiana (b belkowe)

(

5

,

1

2

n − n) ą

2

stogowe

≈ c ⋅ nlog n

2

szybkie

≈ c ⋅ nlog n

2

Czasy wykonania algorytmów sortowania odwrotnie

uporz dkowane

losowe

ą

uporz dkowane

ą

algorytm

klucze

klucze

klucze

klucze

klucze

klucze

+dane

+dane

+dane

prosty wybór

489

547

509

607

695

1430

proste wstawianie

12

46

366

1129

704

2150

b belkowe

540

610

1026

3212

1492

5599

ą

mieszane

5

5

961

3071

1619

5757

stogowe

116

264

110

246

104

227

szybkie

31

55

60

137

37

75

Sortowanie przez wybór z zamian ą

44 55 12 42 94 18 06 67

06

06 55 12 42 94 18 44 67

12

06 12 55 42 94 18 44 67

18

06 12 18 42 94 55 44 67

42

06 12 18 42 94 55 44 67

44

06 12 18 42 94 55 94 67

55

06 12 18 42 94 55 94 67

67

06 12 18 42 94 55 67 94

Sortowanie przez wstawianie z zamian ą

…………………...

12

44 55 12 42 94 18 06 67

42

12 44 55 42 94 18 06 67

94

12 42 44 55 94 18 06 67

18

12 42 44 55 94 18 06 67

06

12 18 42 44 55 94 06 67

67

06 12 18 42 44 55 94 67

06 12 18 42 4 44 55 67 94

Sortowanie b belkowe (D-G) ą

Sortowanie b belkowe (G-D) ą

Sortowanie drzewiaste

Sortowanie stogowe

Quicksort

44

55

12

42

94

18

06

67

06

18

12

42

94

55

44

67

06

12

18

42

94

55

44

67

06

12

18

42

44

55

94

67

06

12

18

42

44

55

67

94

06

12

18

42

44

55

67

94