Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Aliru
0 / 0 / 0
Регистрация: 07.05.2013
Сообщений: 83
#1

quickSelect - C++

05.01.2014, 15:48. Просмотров 216. Ответов 2
Метки нет (Все метки)

Есть несколько вопросов.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
// QuickSelect.cpp : Defines the entry point for the console application.
//
 
#include "stdafx.h"
#include <iostream>
#include "conio.h"
 
using namespace std;
 
template<class T>
void printArray(T *A, long N)
{
    for (long i = 0; i < N; i++) 
    {
        cout << A[i];
        if (i < N - 1)
            cout << ' ';
    }
    cout << endl;
}
 
template<class T>
long partition(T* a, T &p, long N) 
{
// На входе - массив a[], a[N] - его последний элемент.
 
  long i = 0, j = N - 1;        // поставить указатели на исходные места
  T temp;
 
  printArray(a,N);
  p = a[(i + j)/2];        // центральный элемент
 
  // процедура разделения
  do 
  {
    while ( a[i] < p ) i++;
    while ( a[j] > p ) j--;
    if (i <= j) 
    {
      temp = a[i]; a[i] = a[j]; a[j] = temp;
      i++; j--;
    }
  } 
  while ( i<=j );
  printArray(a,N);
  return ++j;
}
 
 
template<class T>
T quickSelect(T* input, T &p, long N, long k)
{
           long j = partition(input,p, N);
    long pivot = j + 1;
    if ( j == k - 1) 
        return p;
    else 
        if ( k < pivot ) 
            return quickSelect(input, p, j, k);
        else  
            return quickSelect(input + j, p, N - j, k - j);
}
 
int _tmain(int argc, _TCHAR* argv[])
{
    int A[] = {-900,1,0,777,-34,4,-87,6};
    int pivot = A[0];
    cout << quickSelect(A, pivot, sizeof(A)/sizeof(int), 2);
    _getch();
    return 0;
}
1. Как partition() знает что делать и как с помощью printArray() - я думал, это возможно в случае когда printArray() передается как параметр partition() и quickSelect() cоответственно.
2. В рекурсивном варианте
C++
1
quickSelect(input + j, p, N - j, k - j);
ошибка когда доходит до массива из 2 элементов и выбирается не искомый элемент - начинается зацикливание

Добавлено через 1 час 15 минут
Немного переделал
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
if (2 < N)
    {
        if ( j == k - 1) 
            return p;
        else 
            if ( k < pivot ) 
                return quickSelect(input, p, j, k);
            else  
                return quickSelect(input + j, p, N - j, k - j);
    }
    else 
    {
        if ( j == k - 1) 
            return p;
        else
            return input[1];
    }
Теперь вроде бы работает.
Есть еще какие-то варианты?
Ну кроме -
C++
1
std::nth_element
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
outoftime
║XLR8║
511 / 433 / 33
Регистрация: 25.07.2009
Сообщений: 2,295
05.01.2014, 16:44 #2
Aliru, заведите себе привычку сначала описывать то что вы пытаетесь сделать а потом уже то как вы это делаете и что у вас не получается.
0
Aliru
0 / 0 / 0
Регистрация: 07.05.2013
Сообщений: 83
05.01.2014, 17:17  [ТС] #3
А, точно.
Есть входной массив - неотсортированный.
Надо найти минимкльный элемент №к за время O(n)
0
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru