1
00:00:00,000 --> 00:00:05,726
>> [Παίζει μουσική]

2
00:00:05,726 --> 00:00:08,600
DOUG LLOYD: Επιλογή του είδους είναι μια
αλγόριθμο που, όπως μπορείτε να φανταστείτε,

3
00:00:08,600 --> 00:00:10,470
ταξινομεί ένα σύνολο στοιχείων.

4
00:00:10,470 --> 00:00:12,470
Και αλγόριθμος ανάκληση
είναι ένα βήμα-προς-βήμα σύνολο

5
00:00:12,470 --> 00:00:15,260
οδηγιών για την ολοκλήρωση μιας εργασίας.

6
00:00:15,260 --> 00:00:17,580
>> Στην επιλογή ταξινομήσετε
βασική ιδέα είναι αυτό,

7
00:00:17,580 --> 00:00:22,080
βρείτε το μικρότερο στοιχείο και αδιαχώριστα
προσθέστε το στο τέλος της ταξινομημένη λίστα.

8
00:00:22,080 --> 00:00:26,970
Ουσιαστικά αυτό που κάνει αυτό είναι κατασκευής
μια ταξινομημένη λίστα, ένα στοιχείο τη φορά.

9
00:00:26,970 --> 00:00:29,800
Σπάζοντας τα κάτω για να ψευδοκώδικα
θα μπορούσε να αναφέρει αυτόν τον αλγόριθμο

10
00:00:29,800 --> 00:00:34,490
ως εξής, επαναλάβετε αυτό έως ότου
εξακολουθούν να υπάρχουν στοιχεία αδιαχώριστα.

11
00:00:34,490 --> 00:00:38,660
Αναζήτηση μέσω του αδιαχώριστα
δεδομένα για να βρείτε τη μικρότερη τιμή,

12
00:00:38,660 --> 00:00:44,130
να ανταλλάξουν τη μικρότερη τιμή με την
πρώτο στοιχείο της αδιαχώριστα μέρος.

13
00:00:44,130 --> 00:00:47,130
>> Μπορεί να βοηθήσει να απεικονίσει αυτό,
οπότε ας ρίξουμε μια ματιά σε αυτό.

14
00:00:47,130 --> 00:00:49,710
Έτσι αυτό, υποστηρίζουν, είναι ένας
αδιαχώριστα σειρά και έχω

15
00:00:49,710 --> 00:00:53,040
ανέφερε ότι με την ένδειξη ότι όλα
από τα στοιχεία που έχουν κόκκινο χρώμα,

16
00:00:53,040 --> 00:00:54,420
δεν έχουν ακόμη ταξινομηθεί.

17
00:00:54,420 --> 00:00:57,670
Αυτή είναι η πλήρης
αδιαχώριστα μέρος της συστοιχίας.

18
00:00:57,670 --> 00:01:02,020
>> Ας περάσουν από τα στάδια της
Ταξινόμηση επιλογή για να ταξινομήσετε αυτή τη σειρά.

19
00:01:02,020 --> 00:01:05,296
Έτσι και πάλι, είμαστε Θα επανάληψης
μέχρι να μην υπάρχουν αδιαχώριστα στοιχεία.

20
00:01:05,296 --> 00:01:07,920
Είμαστε Θα αναζήτηση μέσω της
δεδομένα για να βρείτε τη μικρότερη τιμή,

21
00:01:07,920 --> 00:01:11,990
και στη συνέχεια να ανταλλάξουν αυτή την τιμή με την
πρώτο στοιχείο της αδιαχώριστα μέρος.

22
00:01:11,990 --> 00:01:14,380
>> Αυτή τη στιγμή, και πάλι, το σύνολο
συστοιχία είναι αδιαχώριστα το μέρος.

23
00:01:14,380 --> 00:01:16,534
Όλα τα κόκκινα στοιχεία δεν έχουν υποστεί διαλογή.

24
00:01:16,534 --> 00:01:18,700
Έτσι ψάχνουμε μέσα και
βρίσκουμε τη μικρότερη τιμή.

25
00:01:18,700 --> 00:01:20,533
Θα ξεκινήσουμε από την αρχή,
πάμε στο τέλος,

26
00:01:20,533 --> 00:01:23,630
βρίσκουμε η μικρότερη τιμή είναι ένα.

27
00:01:23,630 --> 00:01:24,860
Έτσι, αυτό είναι το πρώτο μέρος.

28
00:01:24,860 --> 00:01:29,440
Και στη συνέχεια μέρος δύο, swap agreement που έχει αξία με
Το πρώτο στοιχείο της αδιαχώριστα μέρος,

29
00:01:29,440 --> 00:01:31,340
ή η πρώτη κόκκινη στοιχείο.

30
00:01:31,340 --> 00:01:34,980
>> Σε αυτή την περίπτωση που θα ήταν
πέντε, έτσι ώστε να ανταλλάξουν ένα και πέντε.

31
00:01:34,980 --> 00:01:37,320
Όταν το κάνουμε αυτό, μπορούμε
οπτικά δείτε ότι έχουμε

32
00:01:37,320 --> 00:01:41,260
μετακόμισε το μικρότερο αξιόλογο στοιχείο
της συστοιχίας, με την ίδια αρχή.

33
00:01:41,260 --> 00:01:43,920
Αποτελεσματική ταξινόμηση αυτό το στοιχείο.

34
00:01:43,920 --> 00:01:47,520
>> Και έτσι μπορούμε όντως να επιβεβαιώσει
και να δηλώσει ότι ένα είναι ταξινομημένο.

35
00:01:47,520 --> 00:01:52,080
Και έτσι θα αναφέρει την ταξινόμηση τμήμα
του πίνακα μας, από το μπλε χρωματισμό.

36
00:01:52,080 --> 00:01:53,860
>> Τώρα απλά επαναλάβετε τη διαδικασία.

37
00:01:53,860 --> 00:01:57,430
Ψάχνουμε μέσα από την αδιαχώριστα μέρος του
η συστοιχία να βρει το μικρότερο στοιχείο.

38
00:01:57,430 --> 00:01:59,000
Σε αυτήν την περίπτωση, είναι δύο.

39
00:01:59,000 --> 00:02:02,100
>> Έχουμε ανταλλάξει ότι με την πρώτη
στοιχείο του αδιαχώριστα μέρος.

40
00:02:02,100 --> 00:02:05,540
Σε αυτή την περίπτωση δύο συμβαίνει επίσης να είναι
Το πρώτο στοιχείο της αδιαχώριστα μέρος.

41
00:02:05,540 --> 00:02:08,650
Γι 'αυτό και να ανταλλάξουν δύο με την ίδια,
η οποία πραγματικά αφήνει μόνο δύο

42
00:02:08,650 --> 00:02:11,257
όπου είναι, και είναι ταξινομημένο.

43
00:02:11,257 --> 00:02:13,840
Συνεχίζοντας, ψάχνουμε μέσα
για να βρείτε το μικρότερο στοιχείο.

44
00:02:13,840 --> 00:02:15,030
Είναι τρεις.

45
00:02:15,030 --> 00:02:17,650
Εμείς το swap με την πρώτη
στοιχείο, το οποίο είναι πέντε.

46
00:02:17,650 --> 00:02:19,450
Και τώρα τρεις είναι ταξινομημένο.

47
00:02:19,450 --> 00:02:22,440
>> Ψάχνουμε μέσα και πάλι, και εμείς
βρείτε το μικρότερο στοιχείο είναι τέσσερις.

48
00:02:22,440 --> 00:02:28,070
Εμείς το swap με το πρώτο στοιχείο της
αδιαχώριστα μέρος, και τώρα τέσσερις είναι ταξινομημένο.

49
00:02:28,070 --> 00:02:29,910
>> Θεωρούμε ότι είναι πέντε
το μικρότερο στοιχείο.

50
00:02:29,910 --> 00:02:32,900
Εμείς το swap με την πρώτη
στοιχείο του αδιαχώριστα μέρος.

51
00:02:32,900 --> 00:02:34,740
Και τώρα πέντε είναι ταξινομημένο.

52
00:02:34,740 --> 00:02:36,660
>> Και στη συνέχεια, τέλος, μας
αδιαχώριστα μέρος αποτελείται

53
00:02:36,660 --> 00:02:38,576
από ένα μόνο στοιχείο,
οπότε ψάχνουμε μέσα

54
00:02:38,576 --> 00:02:41,740
και διαπιστώνουμε ότι έξι είναι η
μικρότερο, και στην πραγματικότητα, μόνο το στοιχείο.

55
00:02:41,740 --> 00:02:44,906
Και τότε μπορούμε να δηλώσουμε ότι είναι ταξινομημένο.

56
00:02:44,906 --> 00:02:47,530
Και τώρα έχουμε αλλάξει παράταξη μας
από το να εντελώς άνευ διαλογής

57
00:02:47,530 --> 00:02:52,660
σε κόκκινο, να διευθετηθεί πλήρως
σε μπλε χρώμα, με τη χρήση ταξινόμησης επιλογή.

58
00:02:52,660 --> 00:02:54,920
>> Έτσι ποια είναι η χειρότερη περίπτωση εδώ;

59
00:02:54,920 --> 00:02:57,830
Καλά στην απόλυτη χειρότερη
περίπτωση, πρέπει να κοιτάξουμε πέρα

60
00:02:57,830 --> 00:03:02,170
όλα τα στοιχεία της συστοιχίας σε
βρείτε το μικρότερο αδιαχώριστα στοιχείο,

61
00:03:02,170 --> 00:03:04,750
και θα πρέπει να επαναλάβετε
αυτή η διαδικασία n φορές.

62
00:03:04,750 --> 00:03:09,090
Μόλις για κάθε στοιχείο της συστοιχίας
γιατί μόνο σε αυτόν τον αλγόριθμο,

63
00:03:09,090 --> 00:03:12,180
Ταξινόμηση ένα στοιχείο στο χρόνο.

64
00:03:12,180 --> 00:03:13,595
>> Ποιο είναι το καλύτερο σενάριο;

65
00:03:13,595 --> 00:03:15,040
Καλά είναι ακριβώς το ίδιο, έτσι δεν είναι;

66
00:03:15,040 --> 00:03:18,440
Στην πραγματικότητα έχουμε να εξακολουθούν να το βήμα μέσω
κάθε στοιχείο της συστοιχίας

67
00:03:18,440 --> 00:03:22,040
προκειμένου να επιβεβαιωθεί ότι είναι,
Στην πραγματικότητα, το μικρότερο στοιχείο.

68
00:03:22,040 --> 00:03:26,760
>> Έτσι, η χειρότερη περίπτωση εκτέλεσης, εμείς
πρέπει να επαναλάβετε μια διαδικασία Ν φορές,

69
00:03:26,760 --> 00:03:28,960
μια φορά για κάθε ένα από n στοιχεία.

70
00:03:28,960 --> 00:03:31,940
Και στην καλύτερη περίπτωση,
πρέπει να κάνουμε το ίδιο.

71
00:03:31,940 --> 00:03:35,340
>> Έτσι σκέφτεται πίσω στο μας
υπολογιστική πολυπλοκότητα εργαλειοθήκη,

72
00:03:35,340 --> 00:03:39,250
τι νομίζετε ότι είναι η χειρότερη
περίπτωση εκτέλεσης για ταξινόμηση με επιλογή;

73
00:03:39,250 --> 00:03:41,840
Ποια νομίζετε ότι είναι η καλύτερη
περίπτωση εκτέλεσης για ταξινόμηση με επιλογή;

74
00:03:41,840 --> 00:03:44,760

75
00:03:44,760 --> 00:03:49,325
>> Μήπως να μαντέψετε Big O Ν τετράγωνο,
και Big Ωμέγα Ν τετράγωνο;

76
00:03:49,325 --> 00:03:49,950
Θα ήθελα να είναι σωστή.

77
00:03:49,950 --> 00:03:52,490
Αυτά είναι, στην πραγματικότητα, η
χειρότερη περίπτωση και καλύτερη κίνηση υπόθεση

78
00:03:52,490 --> 00:03:55,100
φορές, για ταξινόμηση με επιλογή.

79
00:03:55,100 --> 00:03:56,260
>> Είμαι ο Νταγκ Lloyd.

80
00:03:56,260 --> 00:03:58,600
Αυτό είναι CS50.

81
00:03:58,600 --> 00:04:00,279