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

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

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

Сортировка - C++

04.10.2011, 04:03. Просмотров 649. Ответов 11
Метки нет (Все метки)

Дан массив из n целых чисел, дан индекс элемента. Требуется расположить элементы массива так, что бы элементы меньше a[index] стояли слева, а элементы больше стояли справа.

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
#include "stdafx.h"
#include "iostream"
 
using namespace std;
 
int _tmain(int argc, _TCHAR* argv[])
{
setlocale(0,"");
const int n=10;
int a[n];
int b[n];
int i,index,k=0;
cout<<"Введите массив из "<<n<<" чисел:\n";
for(i=0;i<n;i++)
    cin>>a[i];
cout<<"\nВведи индекс: ";
    cin>>index;
for(i=0;i<n;i++)
b[i]=0;
for(i=0;i<n;i++)
    if (a[i]<a[index])  
        b[k++]=a[i];
        
for(i=0;i<k;i++)
cout<<b[k]<<" ";
 
    return 0;
}
это не полный код программы, но он уже не правильно работает, можете подсказать, почему он массиву b не присваивает значения массива а?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.10.2011, 04:03     Сортировка
Посмотрите здесь:

Сортировка выбором, сортировка вставкой, сортировка заменой, сортировка обменом ("пузырьковая" сортировка) - C#
Создать класс, содержащий массив и реализующий алгоритмы сортировки и бинарного поиска в этом массиве. Класс описать с помощью...

Блок схема.Сортировка «Пузырьком», Сортировка методом «Последовательных перестановок», Сортировка «Вставками» - Pascal
Помогите, нужны блок схемы Сортировка «Вставками» Program Vstavka; uses dos; Type mass=array of integer; Var i,b,n,j,a:...

Разработать программу сортировки: сортировка перестановкой, сортировка вставкой, быстрая сортировка - Prolog
Задание: Разработать программу сортировки: - сортировка перестановкой - сортировка вставкой - быстрая сортировка

1)Бинарный поиск 2)Сортировка включением 3)Шейкерная сортировка 4)Сортировка разделением - Pascal
1)В заданном массиве К(N) найти индексы элементов, которые кратны минимальному значению элемента массива. 2)Задан массив AX (N). Добавить...

Сортировка массива целых чисел A(n) по убыванию(используя метод обменная сортировка) - Turbo Pascal
Помогите написать программу для сортировки массива целых чисел A(n) по убыванию(используя метод обменная сортировка). Или хотя бы без этого...

Сортировка Шелла. Написал программу, не могу понять, почему сортировка не выполняется - C++
Программа создает динамический массив с рандомным заполнением. Дальше выбор сортировок, пузырьком или сортировка Шелла. Вот она то и не...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
alkagolik
Заблокирован
04.10.2011, 04:35     Сортировка #2
в принципе условие некорректно. например дан массив
C
1
arr[] = {7, 6, 5, 4, 3, 2, 1}
и индекс 2. понятно что 4 элемента разместить "слева" от индекса мы не сможем - места нету в массиве, следовательно придется сдвигать заданный элемент, а это сводит задачу к банальной сортировке. вот код
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
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define size    40
 
int compare(const void *i, const void *j){
  return *(int *)i - *(int *)j;
}
 
int main(void){
    int array[size], i;
    srand(time(NULL));
 
    for(i = 0; i < size; ++i)
        array[i] = rand() % size + 1;
 
    printf("\n\nsourse array:\n");
    for(i = 0; i < size; ++i)
        printf("%d ", array[i]);
 
    qsort(array, size, sizeof(int), compare);
 
    printf("\n\nsort array:\n");
    for(i = 0; i < size; ++i)
        printf("%d ", array[i]);
 
    printf("\n\n");
    return 0;
}
xexew
0 / 0 / 0
Регистрация: 22.02.2011
Сообщений: 76
04.10.2011, 04:45  [ТС]     Сортировка #3
Благодарю)
А какую сортировку можно применить, что бы проверок было не больше N, а перестановок не больше n/2. Можно сортировкой Шелла добиться этого?
alkagolik
Заблокирован
04.10.2011, 04:52     Сортировка #4
xexew, в моем коде реализована встроенная в Си шиные библиотеки сортировка Хоара. Это самый быстрый метод. Смотрите FAQ, там описаны несколько алгоритмов.
Thinker
Эксперт C++
4223 / 2197 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
04.10.2011, 08:36     Сортировка #5
Цитата Сообщение от xexew Посмотреть сообщение
Благодарю)
А какую сортировку можно применить, что бы проверок было не больше N, а перестановок не больше n/2. Можно сортировкой Шелла добиться этого?
Можно вашу задачу решить всего за одно прохождение по массиву. Он не будет весь упорядочен, но задача будет выполнена:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void Exchange(double *a, const int n, const int index)
{
    int i = 0, j = n - 1, buf;
    while (i < j)
    {
        while (i < j && a[i] < a[index])  
            i++;
        while (i < j && a[j] >= a[index]) 
            j--;
        if (i < j) 
        {
            buf = a[i];
            a[i] = a[j];
            a[j] = buf;
            i++;
            j--;
        }
    }
}
xexew
0 / 0 / 0
Регистрация: 22.02.2011
Сообщений: 76
07.10.2011, 21:32  [ТС]     Сортировка #6
Цитата Сообщение от Thinker Посмотреть сообщение
Можно вашу задачу решить всего за одно прохождение по массиву. Он не будет весь упорядочен, но задача будет выполнена:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void Exchange(double *a, const int n, const int index)
{
    int i = 0, j = n - 1, buf;
    while (i < j)
    {
        while (i < j && a[i] < a[index])  
            i++;
        while (i < j && a[j] >= a[index]) 
            j--;
        if (i < j) 
        {
            buf = a[i];
            a[i] = a[j];
            a[j] = buf;
            i++;
            j--;
        }
    }
}
А вы проверяли свой код? А то когда я проверяю работает не правильно, он не сортирует а просто выводит тот же массив
Thinker
Эксперт C++
4223 / 2197 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
07.10.2011, 21:36     Сортировка #7
Цитата Сообщение от xexew Посмотреть сообщение
А вы проверяли свой код? А то когда я проверяю работает не правильно, он не сортирует а просто выводит тот же массив
А кто вам сказал, что это сортировка. Алгоритм преобразует элементы так, что сначала следуют элементы, меньшие элемента a[index], а затем все остальные элементы. Для решения вашей задачи остается прменить смекалку и доделать данный алгоритм. И никаких сортировок не надо!!!
xexew
0 / 0 / 0
Регистрация: 22.02.2011
Сообщений: 76
07.10.2011, 21:44  [ТС]     Сортировка #8
я под сортировкой имел ввиду, что элементы меньше будут слева,а которые больше справа.

при входных данных: 5 4 3 2 1 10 9 8 7
и индексе 1
по идее должно быть 1 2 3 4 5 10 9 8 7
но выводится массив при входе

Добавлено через 2 минуты
Вы читайте внимательней, я же написал, что он выводит тот же массив, а вы обратили внимание на неправильно написанную мысль.

Я решал эту задачу подобным алгоритмом, т.е. вы дали мне убедиться что он правильный, а он все равно не работает
Thinker
Эксперт C++
4223 / 2197 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
07.10.2011, 22:07     Сортировка #9
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
void Exchange(double *a, const int n, const int index)
{
    int i = 0, j = n - 1, buf;
    while (i < j)
    {
        while (i < j && a[i] < a[index])
            i++;
        while (i < j && a[j] >= a[index])
            j--;
        if (i < j) 
        {
            buf = a[i];
            a[i] = a[j];
            a[j] = buf;
            i++;
            j--;
        }
    }
}
 
int main()
{
   double a[9] = {5, 4, 3, 2, 1, 10, 9, 8, 7};
   int i;
   Exchange(a, 9, 1);
   for(i = 0; i < 9; i++)
      printf("%.0f ", a[i]);
   getchar();
}
Выводит:
1 2 3 4 5 10 9 8 7

Добавлено через 2 минуты
Цитата Сообщение от xexew Посмотреть сообщение
Вы читайте внимательней, я же написал, что он выводит тот же массив, а вы обратили внимание на неправильно написанную мысль.
А вы проверяйте внимательнее, выводит нужный массив. Только баламутите тут...

Добавлено через 6 минут
Но я бы немного функцию переделал вот так, так надежнее:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void Exchange(double *a, const int n, const int index)
{
    int i = 0, j = n - 1, buf;
    double x = a[index];
    while (i < j)
    {
        while (i < j && a[i] < x)
            i++;
        while (i < j && a[j] >= x)
            j--;
        if (i < j)
        {
            buf = a[i];
            a[i] = a[j];
            a[j] = buf;
            i++;
            j--;
        }
    }
}
Повторю, что она одну часть задачи решает, ее чуточку доделать надо, чтобы большие и равные элементы в правой части не вперемешку были, но это уже банально просто, думаю, что сами это в состоянии, но если, что, помогу.
xexew
0 / 0 / 0
Регистрация: 22.02.2011
Сообщений: 76
07.10.2011, 23:03  [ТС]     Сортировка #10
Спасибо большое, у меня один вопрос: почему с функцией работает, а без нее нет?)

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
#include "stdafx.h"
#include <iostream>
 
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
setlocale(0,"");
const int n=10;
int i=0,j=n-1,tmp,index;
int a[n];
 
cout<<"Введите массив из "<<n<<" чисел\n";
 
for(i=0;i<n;i++)
    cin>>a[i];
 
cout<<"\nИндекc:";
cin>>index;
 
while (i < j)
    {
        while (i < j && a[i] < a[index])
            i++;
        while (i < j && a[j] >= a[index])
            j--;
        if (i < j) 
        {
            tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
            i++;
            j--;
        }
    }
 
cout<<"Сортированный массив:\n";
for(i=0;i<n;i++)
cout<<a[i]<<" ";
    return 0;
}
Вопрос бредовый, но это так, может я что-то не то делаю?)
Thinker
Эксперт C++
4223 / 2197 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
07.10.2011, 23:06     Сортировка #11
Цитата Сообщение от xexew Посмотреть сообщение
может я что-то не то делаю?)
Не хватает до цикла while инициализаций
C++
1
i = 0, j = n - 1
j можно не трогать, а вот i у вас в цикле for изменилось
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.10.2011, 23:20     Сортировка
Еще ссылки по теме:

Быстрая сортировка, ситуация, при которой сортировка работает не корректно - Turbo Pascal
Procedure sort(m, l: Integer); Var i, j, x, w: Integer; Begin i := m; j := l; x := ar; Repeat While...

Сортировка слиянием. В каком куске кода происходит сортировка и каким именно образом? - C++
Помогите, пожалуйста, разобраться. Подскажите в каком куске кода происходит сортировка и каким именно образом? #include &lt;iostream&gt; ...

Быстрая сортировка(сортировка Хоара). Отсортировать фрагмент массива - C++
Мне нужно отсортировать фрагмент массива, расположенный между первым и последним отрицательным элементом. Немогу понять как устоновить...

Сортировка векторов методами: пузырька, Хоара, Шейкерная сортировка - C (СИ)
Сортировка векторов методами: пузырька, Хоараб, Шейкерная сортировка Каждый отдельный алгоритм должен быть оформлен в виде функции,...


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

Или воспользуйтесь поиском по форуму:
xexew
0 / 0 / 0
Регистрация: 22.02.2011
Сообщений: 76
07.10.2011, 23:20  [ТС]     Сортировка #12
Цитата Сообщение от Thinker Посмотреть сообщение
Не хватает до цикла while инициализаций
C++
1
i = 0, j = n - 1
j можно не трогать, а вот i у вас в цикле for изменилось
все ясно, спасибо
Yandex
Объявления
07.10.2011, 23:20     Сортировка
Ответ Создать тему
Опции темы

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