2018-01-08
213
1. Brian W. KernighanandDennis M. Ritchie «The C ProgrammingLanguage» (SecondEdition). — 1988. [ISBN 0–13–110362–8]
2. Donald E. Knuth «TheArtofComputerProgramming»: «Volume 3: SortingandSearching» (SecondEdition). — 1998. [ISBN 0–201–89685–0]
3. OwenAstrachan «BubbleSort: An ArchaeologicalAlgorithmicAnalysis» // ACM SIGCSE Bulletin, Volume 35, Issue 1. — 2003. [ISSN 0097–8418]
Лабораторна робота № 2
Лабораторна робота № 2
Тема роботи: Метод сортування вибором.
Мета роботи: Вивчити алгоритм сортування вибором. Здійснити програмну реалізацію алгоритму сортування вибором. Дослідити швидкодію алгоритму сортування вибором.
Короткі теоретичні відомості
Сортування вибором (англійською «SelectionSort») — простий алгоритм сортування лінійного масиву, на основі вставок. Має ефективність O (n 2), що робить його неефективним при сортування велеких масивів, і в цілому, менш ефективним за подібний алогоримт сортування включенням. Сортування вибором вирізняється більшою простотою, ніж cортування включенням, і в деяких випадках вищою продуктивністю.
Алгоритм працює наступним чином:
1. Знаходить у списку найменше значення.
|
|
|
2. Міняє його місцями із першим значеннями у списку.
3. Повторює два попередніх кроки, доки список не завершиться (починаючи з другої позиції).
Фактично, таким чином ми поділили список на дві частини: перша (ліва) — повністю відсортована, а друга (права) — ні.
Сортування вибором не є складним в аналізі та порівнянні його з іншими алгоритмами, оскільки жоден з циклів не залежить від даних у списку. Знаходження найменшого елементу вимагає перегляду усіх n елементів (у даному випадку (n − 1) порівняння), і після цього, переситановки його до першої позиції. Знаходження наступного найменшого елементу вимагає перегляду (n − 1) елементів, і так далі, для (n − 1) + (n − 2) +... + 2 + 1 = n (n − 1) / 2 Î Θ (n 2) порівнянь. Кожне сканування вимагає однієї перестановки для (n − 1) елементів (останній елемент знаходитиметься на своєму місці).
