Форум программистов, компьютерный форум CyberForum.ru

Перестановка - C++

Восстановить пароль Регистрация
 
Konyahinzhenya
-23 / 1 / 0
Регистрация: 20.09.2011
Сообщений: 32
25.02.2012, 13:54     Перестановка #1
Пусть дан массив а1, ..., аn. Требуется переставить а1 и an так, чтобы вначале в массиве шла группа, больших того элемента, который в исходном массиве располагается на первом месте, затем сам этот элемент, потом группа элементов, меньших или равных ему. Число сравнений и перемещений, каждое в
отдельности не должно превышать n-1.

Нужно придумать алгоритм как можно с наименьшей сложностью

Вот вариант. Подскажите пожалуйста, лучший алгоритм

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
#include <iostream>
#include <stdlib.h>
#include <conio.h>
#include <time.h>
int random(int N)
{
return (rand() % N);
}
 
int main(void)
{ 
    srand(time(0));
    int const n=5;
    int a[n];
    
    for(int i=0; i<n; i++)
      a[i]=random(30);
    for(int i=0; i<n; i++)
      std::cout << a[i] << " " ;
      std::cout << "\n";
 
   int leftpos=1; 
   int rightpos=n-1; 
   bool positive=true; 
 
   while (positive)
   {
      while (a[0]<a[leftpos])
      {
         leftpos++; 
      } 
 
      while (a[0]>=a[rightpos])
      {
         rightpos--; 
      } 
 
      if ((rightpos-leftpos)>0)
      {
        int t=a[leftpos]; 
         a[leftpos]=a[rightpos]; 
         a[rightpos]=t; 
      } 
      else 
      {
         positive=false; 
      } 
   } 
   int t=a[0]; 
   a[0]=a[leftpos-1]; 
   a[leftpos-1]=t; 
  
 
 
   for(int i=0; i<n;i++)
       std::cout << a[i] << " ";
   system("PAUSE");
   return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.02.2012, 13:54     Перестановка
Посмотрите здесь:

Матрицы (перестановка) C++
C++ Перестановка
Перестановка в массиве C++
C++ перестановка
Перестановка чисел C++
Перестановка слов C++
Перестановка строки. C++
Перестановка элементов C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 21:50. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru