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

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

Восстановить пароль Регистрация
 
xexew
0 / 0 / 0
Регистрация: 22.02.2011
Сообщений: 76
04.10.2011, 04:03     Сортировка #1
Дан массив из 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++ Сортировка.
C++ Сортировка
С++ сортировка C++
Сортировка C++
Сортировка C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
alkagolik
 Аватар для alkagolik
1510 / 616 / 79
Регистрация: 15.07.2011
Сообщений: 3,552
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
 Аватар для alkagolik
1510 / 616 / 79
Регистрация: 15.07.2011
Сообщений: 3,552
04.10.2011, 04:52     Сортировка #4
xexew, в моем коде реализована встроенная в Си шиные библиотеки сортировка Хоара. Это самый быстрый метод. Смотрите FAQ, там описаны несколько алгоритмов.
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 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++
 Аватар для Thinker
4215 / 2189 / 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++
 Аватар для Thinker
4215 / 2189 / 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++
 Аватар для Thinker
4215 / 2189 / 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     Сортировка
Еще ссылки по теме:

Сортировка C++
сортировка 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     Сортировка
Ответ Создать тему
Опции темы

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