MAXimal

добавлено: 11 Jun 2008 11:07
редактировано: 11 Jun 2008 11:08

K-ая порядковая статистика за O (N)

Пусть дан массив A длиной N и пусть дано число K. Задача заключается в том, чтобы найти в этом массиве K-ое по величине число, т.е. K-ую порядковую статистику.

 

Основная идея - использовать идеи алгоритма быстрой сортировки. Собственно, алгоритм несложный, сложнее доказать, что он работает в среднем за O (N), в отличие от быстрой сортировки.

 

Реализация в виде нерекурсивной функции:

template <class T>
T order_statistics (std::vector<T> a, unsigned n, unsigned k)
{
	using std::swap;
	for (unsigned l=1, r=n; ; )
	{
		
		if (r <= l+1)
		{
			// текущая часть состоит из 1 или 2 элементов -
			//	 легко можем найти ответ
			if (r == l+1 && a[r] < a[l])
				swap (a[l], a[r]);
			return a[k];
		}
		
		// упорядочиваем a[l], a[l+1], a[r]
		unsigned mid = (l + r) >> 1;
		swap (a[mid], a[l+1]);
		if (a[l] > a[r])
			swap (a[l], a[r]);
		if (a[l+1] > a[r])
			swap (a[l+1], a[r]);
		if (a[l] > a[l+1])
			swap (a[l], a[l+1]);
		
		// выполняем разделение
		// барьером является a[l+1], т.е. медиана среди a[l], a[l+1], a[r]
		unsigned
			i = l+1,
			j = r;
		const T
			cur = a[l+1];
		for (;;)
		{
			while (a[++i] < cur) ;
			while (a[--j] > cur) ;
			if (i > j)
				break;
			swap (a[i], a[j]);
		}

		// вставляем барьер
		a[l+1] = a[j];
		a[j] = cur;

		// продолжаем работать в той части,
		//	 которая должна содержать искомый элемент
		if (j >= k)
			r = j-1;
		if (j <= k)
			l = i;

	}
}

 

Следует заметить, что в стандартной библиотеке C++ этот алгоритм уже реализован - он называется nth_element.