Найти медиану массива

Question

#include<iostream>
#include <cstdlib>
#include <time.h>
using namespace std;
int main() 
{
setlocale(LC_ALL, "RUS");
int n;
int y = 0;
cout << "print N" << endl;
cin >> n;
n = n + 15;
srand(time(0));
int *arr=new int[n];

for (int i = 0; i < n; i++) 
{
    arr[i] = rand() % (n + n + 1) - n;
}
}

После этого нужно найти медиану данного масива, идей 0

Answer 1

Нахождение медианы с сортировкой массива

Скорость алгоритма: O(n^2)

float getMedianWithSort(int* arr, int size) {
int temp;

//Отсортируем массив методом пузырька
for (int i = 0; i < size - 1; ++i) {
    for (int j = 0; j < size - i - 1; ++j) {
        if (arr[j] > arr[j + 1]) {
            // меняем элементы местами
            temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp;
        }
    }
}

//Осталось найти медиану
if (size % 2 == 1)
    return arr[size / 2];
else return (arr[size / 2 - 1] + arr[size / 2]) / 2;
}

Если вам нужен алгоритм быстрее, то советую ознакомится с этой статьей на хабре.

Или использовать вместо сортировки пузырьком, например quicksort.

БЛОГ НА HUSL

Найти медиану массива

Ответы (1 шт):

Нахождение медианы с сортировкой массива