Міністерство освіти і науки України
Донецький національний університет імені Василя Стуса
Факультет інформаційних і прикладних технологій
Кафедра інформаційних технологій
ЗВІТ
з лабораторної роботи №4
з дисципліни “Алгоритми і структури даних”
на тему: Вдосконалені алгоритми впорядкування ”
Виконав: студент 2 пот. гр. КН-21-Б
Рябошапка О.В.
Вінниця 2021
Робота виконана на мові Kotlin
Посилання на програму в github:
https://github.com/saniaGoldy/UniversityTasks/tree/algo_lab_4
Мета: Набуття практичних навичок та вмінь роботи з логарифмічними алгоритмами впорядкування: пірамідальним, швидким, злиттям
Завдання для самостійного виконання
Проаналізувати приклади і доповнити частини, яких не вистачає.
Проілюструвати графічно роботу пірамідального сортування на прикладі впорядкування масиву з 10 цілих елементів.
Написати програму, яка впорядковує масив з 1000 випадкових елементів на вибір одним із методів: пірамідальним, швидким, злиттям.
Код програми
Main.kt
import domain.BinaryTreeSorter
import domain.MergeSorter
import domain.QuickSorter
import domain.Sorter
import kotlin.system.measureTimeMillis
fun main() {
val data = getListOfRandomNumbers()
println("Initial data: $data")
while (true) {
when (chooseSorter()) {
"1" -> measureSorter(BinaryTreeSorter(), data)
"2" -> measureSorter(QuickSorter(), data)
"3" -> measureSorter(MergeSorter(), data)
else -> break
}
}
}
private fun chooseSorter(): String? {
println("Choose sorting method( 1-for binary search tree, 2-for quick sort, 3-for merge sort, anything else to exit)")
return readLine()
}
private fun measureSorter(sorter: Sorter, data: MutableList
measureTimeMillis {
println("\n Measuring ${sorter::class.java.name}")
val sortedList = sorter.sort(data)
println("Sorted list: [${sortedList?.get(0)},${sortedList?.get(1)}...${sortedList?.get(sortedList.lastIndex)}]")
}.let {
println("\n Execution time: $it ms")
}
Utils.kt
import kotlin.random.Random
private const val DATA_SIZE = 1000
fun getListOfRandomNumbers(): MutableList
val rawData = mutableListOf
for (i in 0 until (DATA_SIZE)) {
rawData.add(Random.nextInt())
}
return rawData
}
Sorter.kt
package domain
interface Sorter {
fun sort(list: List
}
MergeSorter.kt
package domain
class MergeSorter : Sorter {
override fun sort(list: List
if (list.isEmpty()) return listOf()
val data = list.toIntArray()
mergeSort(data, 0, list.lastIndex)
return data.toList()
}
private fun mergeSort(a: IntArray, beg: Int, end: Int) {
if (beg < end) {
val mid = (beg + end) / 2
mergeSort(a, beg, mid)
mergeSort(a, mid + 1, end)
merge(a, beg, mid, end)
}
}
private fun merge(a: IntArray, beg: Int, mid: Int, end: Int) {
val n1 = mid - beg + 1
val n2 = end - mid
val leftArray = IntArray(n1)
val rightArray = IntArray(n2) //temporary arrays
/* copy data to temp arrays */
var i: Int = 0
while (i < n1) {
leftArray[i] = a[beg + i]
i++
}
var j: Int = 0
while (j < n2) {
rightArray[j] = a[mid + 1 + j]
j++
}
i = 0 /* initial index of first sub-array */
j = 0 /* initial index of second sub-array */
var k: Int = beg /* initial index of merged sub-array */
while (i < n1 && j < n2) {
if (leftArray[i] <= rightArray[j]) {
a[k] = leftArray[i]
i++
} else {
a[k] = rightArray[j]
j++
}
k++
}
while (i < n1) {
a[k] = leftArray[i]
i++
k++
}
while (j < n2) {
a[k] = rightArray[j]
j++
k++
}
}
}
QuickSorter.kt
package domain
import swap
class QuickSorter : Sorter {
override fun sort(list: List
val values = list.toMutableList()
var leftBorder = 0
var rightBorder = values.lastIndex
val middleElement = list[values.lastIndex / 2]
while (leftBorder < rightBorder) {
while (values[leftBorder] < middleElement)
leftBorder++
while (values[rightBorder] > middleElement)
rightBorder--
if (leftBorder < rightBorder) {
values.swap(leftBorder, rightBorder)
leftBorder++
rightBorder--
}
}
val firstMiddleElementId = values.indexOfFirst { it == middleElement }
val leftValues =
if (firstMiddleElementId > 1)
sort(values.subList(0, firstMiddleElementId))
else
values.subList(0, firstMiddleElementId)
val lastMiddleElementId = values.lastIndexOf(middleElement)
val rightValues =
if (lastMiddleElementId < values.lastIndex - 1)
sort(values.subList(lastMiddleElementId + 1, values.size))
else
values.subList(lastMiddleElementId + 1, values.size)
return leftValues.plus(values.subList(firstMiddleElementId, lastMiddleElementId + 1)).plus(rightValues)
}
}
BinaryTreeSorter.kt
package domain
import domain.dataStructures.BinaryTree
class BinaryTreeSorter : Sorter {
private val binaryTree = BinaryTree()
override fun sort(list: List
list.forEach { binaryTree.insert(it) }
return binaryTree.getAsList()
}
}
BinaryTree.kt
package domain.dataStructures
class BinaryTree {
var rootNode: Node
private val comparator = { oldValue: Int, newValue: Int ->
newValue <= oldValue
}
fun insert(value: Int) {
if (rootNode == null) {
rootNode = Node(value, comparator = comparator)
} else {
rootNode?.insert(value)
}
}
fun getAsList(): List
return rootNode?.getChildrenAndValueSorted() ?: listOf()
}
}
Node.kt
package domain.dataStructures
/** [comparator] have to return [true] if new value should go in the left node otherwise [false]
*
* [leftNode] and [rightNode] are [null] by default
*/
data class Node
val value: T,
var leftNode: Node
var rightNode: Node
val comparator: (thisNodeValue: T, newValue: T) -> Boolean
) {
fun insert(value: T) {
Node(value, comparator = comparator).let { node ->
if (comparator(this.value, value)) {
if (leftNode == null) {
leftNode = node
} else {
leftNode?.insert(value)
}
} else {
if (rightNode == null){
rightNode = node
}else{
rightNode?.insert(value)
}
}
}
}
/**
* @return list of all nodes to the left of this node + [value] + list of all nodes to the right
* in ascending order (order depends on [comparator])
*/
fun getChildrenAndValueSorted(): List
val leftValues = leftNode?.getChildrenAndValueSorted() ?: listOf()
val rightValues = rightNode?.getChildrenAndValueSorted() ?: listOf()
return leftValues.plus(value).plus(rightValues)
}
}
Приклад роботи
Заповнити таблицю
| Алгоритм | Час (в мілісекундах) | Додаткова пам’ять | Стійкість | Природність | |||||
| | 100N | 1000N | 10000N | | | | |||
| Пірамідальне впорядкування | 33 ms | 73 ms | 400 ms | O(1) | Не стійкий | Природний | |||
| Швидке впорядкування | 16 ms | 57 ms | 254 ms | O(1) | Стійкий | Не природний | |||
| Впорядкування злиттям | 36 ms | 47 ms | 100 ms | O(n) | Стійкий | Природний | |||