VPF::[C++] В одномерном массиве отсортировать

Martochka

Дата 20.12.2006, 00:13 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 10
Регистрация: 16.12.2006

Репутация: нет
Всего: нет

Прошу помочь решить задачку!!!!!!!!! smile

В одномерном массиве отсортировать все четные элементы.

Заранее выражаю благодарность за время которое вы мне уделили. smile

V.A.KeRneL

Дата 20.12.2006, 01:50 (ссылка)

(нет голосов)

Загрузка ...

Vadim A. Kazantsev

Профиль
Группа: Участник
Сообщений: 291
Регистрация: 3.12.2006
Где: Moscow, Russia

Репутация: 7
Всего: 14

Martochka, из задания я понял, что эффективность реализации, в принципе, не критична. В таком случае можно использовать самую простую пузырьковую сортировку, немного её модифицировав.

Тут, на самом деле, всё зависит от того как ты индексируешь массив: с нуля или с единицы.
Если с нуля (как в Си), то тебе, действительно, нужен `bubble_sort_even()', а если с единицы (как в Паскале, и в быту smile

), то `bubble_sort_odd()'.

Код


#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

/* ==============================   Macros   ============================== */

#define SWAP(a, b) { \
    (a) = (a) + (b); \
    (b) = (a) - (b); \
    (a) = (a) - (b); \
}

/* ========================   Sorting of arrays   ========================= */
void 
bubble_sort(int * a, int n) 
{ 
    int i, j;  /* counters, indexes */
    
    //~ for (i = n - 1; i > 0; --i) 
        //~ for (j = 0; j < i; ++j) 
            //~ if (a[j] > a[j + 1]) 
                //~ SWAP(a[j], a[j + 1]);
    
    for (i = 0; i < n - 1; ++i) 
        for (j = 0; j < n - 1 - i; ++j) 
            if (a[j] > a[j + 1]) 
                SWAP(a[j], a[j + 1]);
}

void 
bubble_sort_even(int * a, int n) 
{ 
    int i, j;  /* counters, indexes */
    
    for (i = 0; i < n - 1; i += 2) 
        for (j = 0; j < n - 1 - i; j += 2) 
            if (a[j] > a[j + 2]) 
                SWAP(a[j], a[j + 2]);
}

void 
bubble_sort_odd(int * a, int n) 
{ 
    int i, j;  /* counters, indexes */
    
    for (i = 1; i < n - 1; i += 2) 
        for (j = 1; j < n - 1 - i; j += 2) 
            if (a[j] > a[j + 2]) 
                SWAP(a[j], a[j + 2]);
}

/* ========================   Printing of arrays   ======================== */

void 
print_array(int * a, int n) 
{ 
    int i;  /* counter, index */
    
    putchar('[');
    for (i = 0; i < n - 1; ++i) 
        printf("%d, ", a[i]);
    if (n > 0) 
        printf("%d", a[n - 1]);
    putchar(']');
}

void 
puts_array(int * a, int n) 
{ 
    print_array(a, n);
    putchar('\n');
}

/* ========================   Copying of arrays   ========================= */

void 
arr_copy(int * dest, const int * src, int n) 
{ 
    int i;  /* counter, index */
    
    for (i = 0; i < n; ++i) 
        dest[i] = src[i];
}

/* ======================================================================== */
/* ===============================   Main   =============================== */
/* ======================================================================== */

int 
main(int argc, char ** argv) 
{ 
    int * arr1;  /* our array of integers */
    int * arr2;  /* copy of our array */
    int size;    /* size of our array */
    int idx;     /* counter, index */
    
    size = argc - 1;
    arr1 = (int *) malloc(size*sizeof(int));
    arr2 = (int *) malloc(size*sizeof(int));
    
    for (idx = 0; idx < size; ++idx) 
        /* Fill `arr1' with integers from arguments from command line.  
           Skip name of program (argv[0]).  */
        arr1[idx] = atoi(argv[idx + 1]);
    
    printf("Array before sorting: \n");
    puts_array(arr1, size);
    
    arr_copy(arr2, arr1, size);
    bubble_sort(arr2, size);
    printf("\nArray after sorting with `bubble_sort()': \n");
    puts_array(arr2, size);
    
    arr_copy(arr2, arr1, size);
    bubble_sort_even(arr2, size);
    printf("\nArray after sorting with `bubble_sort_even()': \n");
    puts_array(arr2, size);
    
    arr_copy(arr2, arr1, size);
    bubble_sort_odd(arr2, size);
    printf("\nArray after sorting with `bubble_sort_odd()': \n");
    puts_array(arr2, size);
    
    free(arr1);
    free(arr2);
    
    return (0);
}

Далее компилируем...
Массив можно задать с помощью аргументов командной строки.
А если запустить программу без аргументов, то она сама предложит ввести сначала размер массива, а затем последовательно его елементы. (Это удобно для ввода больших массивов.)

Примеры использования моей проги:

Код


(E:\__tmp__\c)
[[email protected]]$ gcc even_sort.c

(E:\__tmp__\c)
[[email protected]]$ a.exe 3 2 1 4 5 0 7 6
Array before sorting:
[3, 2, 1, 4, 5, 0, 7, 6]

Array after sorting with `bubble_sort()':
[0, 1, 2, 3, 4, 5, 6, 7]

Array after sorting with `bubble_sort_even()':
[1, 2, 3, 4, 5, 0, 7, 6]

Array after sorting with `bubble_sort_odd()':
[3, 0, 1, 2, 5, 4, 7, 6]

(E:\__tmp__\c)
[[email protected]]$ a.exe
size := 12
array[0] := 12
array[1] := 11
array[2] := 10
array[3] := 9
array[4] := 8
array[5] := 7
array[6] := 6
array[7] := 5
array[8] := 4
array[9] := 3
array[10] := 2
array[11] := 1
Array before sorting:
[12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

Array after sorting with `bubble_sort()':
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

Array after sorting with `bubble_sort_even()':
[2, 11, 4, 9, 6, 7, 8, 5, 10, 3, 12, 1]

Array after sorting with `bubble_sort_odd()':
[12, 1, 10, 3, 8, 5, 6, 7, 4, 9, 2, 11]

Это сообщение отредактировал(а) V_A_KeRneL - 20.12.2006, 02:06

--------------------

«C'est un pense-creux d'ici. C'est le meilleur et le plus irascible homme du monde...» © Ф.М. Достоевский, «Бесы»
---/)/)---(\.../)---(\(\
--(':'=)---(=';'=)---(=':')
(")(")..)-(").--.(")-(..(")(")

Martochka

Дата 22.12.2006, 01:15 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 10
Регистрация: 16.12.2006

Репутация: нет
Всего: нет

Извините я не совсем понимаю решение, может есть более простое решение?

Martochka

Дата 22.12.2006, 03:31 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 10
Регистрация: 16.12.2006

Репутация: нет
Всего: нет

Я немного решила задачу ,но к сожалению,не выводятся четные элементы массива.
Очень прошу помощи.

Код


#include <stdio.h>
#define n 5
void main()
{
    int i,a[n],f;
    printf("Vvedite massiv a[%d]:\n",n);
    for(i=0;i<n;i++)
    scanf("%d",&a[i]);
        if (i%2==0)
            {i+=2;
            for(i=0;i<n;i++)
            {if (a[i-2]>a[i])
            {    f=a[i-2];
                a[i-2]=a[i];
                a[i]=f;
            }
        }
        }
    for(i=0;i<n;i++)
    
        printf("\n %d\n",a[i]);
}

Это сообщение отредактировал(а) Martochka - 22.12.2006, 03:34

V.A.KeRneL

Дата 29.12.2006, 18:36 (ссылка)

(нет голосов)

Загрузка ...

Vadim A. Kazantsev

Профиль
Группа: Участник
Сообщений: 291
Регистрация: 3.12.2006
Где: Moscow, Russia

Репутация: 7
Всего: 14

Martochka, умоляю, научись грамртно форматировать текст, хотябы как я, если нет лучшего примера для подражания! Тогда и самой будет очевиднее логика программы, вложенность операторов и т.д., и тем, кто смотрит (и, тем более, разбирает) твой код, не придётся самостоятельно его форматировать «перед употреблением».

==========================================================================================

Цитата(Martochka @ 22.12.2006, 03:31

)

Я немного решила задачу...

Нет, не решила!.. smile

При нечётном количестве элементов в массиве она вообще ничего не делает! А при чётных работает некорректно, очевидно «вылезая» за границы массива.

Цитата(Martochka @ 22.12.2006, 03:31

)

... ,но к сожалению, ...

Тогда уж не «немного», а «частично» решила. Или, ещё лучше, пыталась решить, но не решила.

Цитата(Martochka @ 22.12.2006, 03:31

)

не выводятся четные элементы массива.

Я скомпилировал твою прогу... У меня не то чтобы не выводятся чётные элементы, как ты говоришь. Все элементы выводятся, слава богу, благодаря

Код


    for (i = 0; i < N; ++i) 
        printf("\n %d\n", a[i]);

Самое главное программа ничего не делает для нечётных `N', из-за проверки:

Код


        if ((i%2) == 0) {

Имхо она (особенно там, где ты её прсобачила) ни к селу, ни к городу!
А далее счётчик `i' у тебя только увеличивается:

Код


            i += 2;
            for (i = 0; i < N; ++i) {

И он уже точно вылезает за пределы массива!..

==========================================================================================

Исправил твой код. Может так будет понятнее...

Код


#include <stdio.h>

#define N   5

//~ #define SWAP(a, b) { \
    //~ int t;           \
    //~ (t) = (a);       \
    //~ (a) = (b);       \
    //~ (b) = (t);       \
//~ }

int 
main(void) 
{ 
    int a[N];
    int i, j, tmp;
    
    printf("Vvedite massiv a[%d]: \n", N);
    
    /* Считываем элементы в массив...  */
    for (i = 0; i < N; ++i) //{ 
        scanf("%d", &a[i]);
        
        //printf("i = %d\n", i);  // === Печатаем `i' для отладки. ===
                                // По секрету, если эта строка выполняется не 
                                // в цикле ``for (i = 0; i < N; ++i)'', а 
                                // после него, то i == N.
    //}
    
    /* Сортируем...  */
    for (i = 0; i < N - 1; i += 2) 
        for (j = 0; j < N - 1 - i; j += 2) 
            if (a[j] > a[j + 2]) { 
                /* Обмениваем (swap) элементы a[j] и a[j + 2] местами.  */
                /*SWAP(a[j], a[j + 2]);*/
                tmp      = a[j + 2];
                a[j + 2] = a[j];
                a[j]     = tmp;
            }
    
    /* Выводим элементы отсортированного нужным образом массива на 
       экран...  */
    for (i = 0; i < N; ++i) 
        printf("\n %d\n", a[i]);
    
    /* Сообщаем системе, что программа завершилась без ошибок.  */
    return (0);
}

==========================================================================================

З.Ы. Всегда следуйте правилам форма! В частности:
Если вопрос решён, то воспользуйтесь ссылкой "Пометить как решённый", которая находится под кнопками создания темы или флажком при ответе smile

==========================================================================================

Это сообщение отредактировал(а) V.A.KeRneL - 26.1.2007, 07:09

--------------------

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »