Виды алгоритмов сортировки Сортировка пузырьком / Bubble sort

жүктеу/скачать 121,16 Kb. бет 7/12 Дата 16.10.2023 өлшемі 121,16 Kb. #115872

Бұл бет үшін навигация:

• Сортировка слиянием / Merge sort Сортировка слиянием - это алгоритм типа “разделяй и властвуй”. Общая идея алгоритма
• Пример реализации на Kotlin
• Пример реализации на С++

Сложность	Лучшее	Среднее
Худшее
Время	O(n)	O(n log n)	O(n2)
Память			O(n)

Сортировка слиянием / Merge sort
Сортировка слиянием - это алгоритм типа “разделяй и властвуй”.
Общая идея алгоритма:

• 
  Массив разбивается на две части примерно одинакового размера. Разбиение получившихся массивов повторяется до тех пор, пока размер каждого массива не достигнет единицы.
  
• 
  Каждая из получившихся частей сортируется отдельно, после чего происходит слияние двух массивов следующим образом:
  
  • 
    На каждом шаге сравниваем первые элементы массивов, берём наименьшее значение и записываем в результирующий массив.
    
  • 
    Когда один из массив закончился, добавляем оставшиеся элементы второго массива в результирующий массив.
    
• 
  Слияние подмассивов продолжается до тех пор, пока не получим один, отсортированный массив.
  

Пример реализации на Kotlin:
fun mergeSort(list: List): List {
if (list.size <= 1) {
return list
}

val middle = list.size / 2

var left = list.subList(0, middle)
var right = list.subList(middle, list.size)

return merge(mergeSort(left), mergeSort(right))

}
Пример реализации на С++:
fun merge(left: List, right: List): List {
var indexLeft = 0
var indexRight = 0
var newList: MutableList = mutableListOf()

while (indexLeft < left.count() && indexRight < right.count()) {

if (left[indexLeft] <= right[indexRight]) {
newList.add(left[indexLeft])
indexLeft++
} else {
newList.add(right[indexRight])
indexRight++
}
}

while (indexLeft < left.size) {

newList.add(left[indexLeft])
indexLeft++
}

while (indexRight < right.size) {

newList.add(right[indexRight])
indexRight++
}
return newList;
}

void MergeSort (int* x, int first, int last) {

if (first < last) {
int split = (first + last) / 2;
MergeSort (x, first, split);
MergeSort (x, split + 1, last);
Merge (x, first, split, last);
}
}
void Merge (int* x, int first, int split, int last) {
int pos1 = first, pos2 = split + 1, pos3 = 0;
int* temp = new int [last — first + 1];
while (pos1 <= split && pos2 <= last) {
if (x [pos1] < x [pos2]) temp [pos3++] = x [pos1++];
else temp [pos3++] = x [pos2++];
}
while (pos2 <= last)
temp [pos3++] = x [pos2++];
while (pos1 <= split)
temp [pos3++] = x [pos1++];
for (int i = 0; i < last — first + 1; ++i)
x [first + i] = temp [i];
}

жүктеу/скачать 121,16 Kb.

Достарыңызбен бөлісу: