Сортировка

@xexew · Регистрация: 22.02.2011

Author24 — интернет-сервис помощи студентам

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

C++

#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 не присваивает значения массива а?

@~~alkagolik~~ · 04.10.2011, 04:35

в принципе условие некорректно. например дан массив

C

1	arr[] = {7, 6, 5, 4, 3, 2, 1}

и индекс 2. понятно что 4 элемента разместить "слева" от индекса мы не сможем - места нету в массиве, следовательно придется сдвигать заданный элемент, а это сводит задачу к банальной сортировке. вот код

C

#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 · 04.10.2011, 04:45 **[ТС]**

Благодарю)
А какую сортировку можно применить, что бы проверок было не больше N, а перестановок не больше n/2. Можно сортировкой Шелла добиться этого?

@~~alkagolik~~ · 04.10.2011, 04:52

xexew, в моем коде реализована встроенная в Си шиные библиотеки сортировка Хоара. Это самый быстрый метод. Смотрите FAQ, там описаны несколько алгоритмов.

@Thinker · 04.10.2011, 08:36

Сообщение от xexew

Благодарю)
А какую сортировку можно применить, что бы проверок было не больше N, а перестановок не больше n/2. Можно сортировкой Шелла добиться этого?

Можно вашу задачу решить всего за одно прохождение по массиву. Он не будет весь упорядочен, но задача будет выполнена:

C++

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 · 07.10.2011, 21:32 **[ТС]**

Сообщение от Thinker

Можно вашу задачу решить всего за одно прохождение по массиву. Он не будет весь упорядочен, но задача будет выполнена:

C++

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 · 07.10.2011, 21:36

Сообщение от xexew

А вы проверяли свой код? А то когда я проверяю работает не правильно, он не сортирует а просто выводит тот же массив

А кто вам сказал, что это сортировка. Алгоритм преобразует элементы так, что сначала следуют элементы, меньшие элемента a[index], а затем все остальные элементы. Для решения вашей задачи остается прменить смекалку и доделать данный алгоритм. И никаких сортировок не надо!!!

@xexew · 07.10.2011, 21:44 **[ТС]**

я под сортировкой имел ввиду, что элементы меньше будут слева,а которые больше справа.

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

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

Я решал эту задачу подобным алгоритмом, т.е. вы дали мне убедиться что он правильный, а он все равно не работает

@Thinker · 07.10.2011, 22:07

C

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++

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 · 07.10.2011, 23:03 **[ТС]**

Спасибо большое, у меня один вопрос: почему с функцией работает, а без нее нет?)

C++

#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 · 07.10.2011, 23:06

Сообщение от xexew

может я что-то не то делаю?)

Не хватает до цикла while инициализаций

C++

1	i = 0, j = n - 1

j можно не трогать, а вот i у вас в цикле for изменилось

@xexew · 07.10.2011, 23:20 **[ТС]**

Сообщение от Thinker

Не хватает до цикла while инициализаций

C++

1	i = 0, j = n - 1

j можно не трогать, а вот i у вас в цикле for изменилось

все ясно, спасибо

@xexew 0 / 0 / 2 Регистрация: 22.02.2011 Сообщений: 76
	04.10.2011, 04:45 [ТС]	3
	Благодарю) А какую сортировку можно применить, что бы проверок было не больше N, а перестановок не больше n/2. Можно сортировкой Шелла добиться этого? 0

@~~alkagolik~~ Заблокирован
	04.10.2011, 04:52	4
	xexew, в моем коде реализована встроенная в Си шиные библиотеки сортировка Хоара. Это самый быстрый метод. Смотрите FAQ, там описаны несколько алгоритмов. 0

@Thinker 4267 / 2241 / 203 Регистрация: 26.08.2011 Сообщений: 3,802 Записей в блоге: 5
	07.10.2011, 21:36	7
	Сообщение от xexew А вы проверяли свой код? А то когда я проверяю работает не правильно, он не сортирует а просто выводит тот же массив А кто вам сказал, что это сортировка. Алгоритм преобразует элементы так, что сначала следуют элементы, меньшие элемента a[index], а затем все остальные элементы. Для решения вашей задачи остается прменить смекалку и доделать данный алгоритм. И никаких сортировок не надо!!! 0

@xexew 0 / 0 / 2 Регистрация: 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 минуты Вы читайте внимательней, я же написал, что он выводит тот же массив, а вы обратили внимание на неправильно написанную мысль. Я решал эту задачу подобным алгоритмом, т.е. вы дали мне убедиться что он правильный, а он все равно не работает 0