Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Центр помощи > [C] Сортировка "пузырьком"

Автор: Fant87 11.2.2010, 23:58

Здравствуйте. Такие темы уже были много раз, но не одна из которых я просмотрел мне не подходит.
Задание: Отсортировать многомерный массив (хотя бы 5x5) с помощью метода пузырька. Но отсортировать необходимо весь массив, а не построчно.
Например:
Дано:
397
185
462
После сортировки:
123
456
789
И еще необходимо использовать не просто ''пузырек", а усовершенствованный по двум условиям:
1. Если на очередном проходе не произошло не одного обмена, то это значит, что масиив отсортирован и нету смысла далее сортировать.
2. Если запоминать не только факт самого обмена, но и индекс последнего обмена например в переменную n. То следующие проходы нужно выполнять до n.
В коллекции алгоритмов дана только сортировка: Shaker sort, в ней получаются лишние действия.
Помогите пожалуйста реализовать эту задачу. Или хотя бы реализовать все 2-а улучшения пузырька. Просто обшарив интернет, я почему-то не смог найти ничего, что я мог бы использовать как наглядный пример,который смог бы понять.

Автор: Luyan 12.2.2010, 17:34

Цитата(Fant87 @ 11.2.2010, 23:58

)

И еще необходимо использовать не просто ''пузырек", а усовершенствованный по двум условиям:
1. Если на очередном проходе не произошло не одного обмена, то это значит, что масиив отсортирован и нету смысла далее сортировать.
2. Если запоминать не только факт самого обмена, но и индекс последнего обмена например в переменную n. То следующие проходы нужно выполнять до n.

Код


#include <stdio.h>
#include <conio.h>

void bsort(int* first, int* last)
{
    int* i, *j;
    int tmp, flag = 0;
    for(i = last - 1; !flag && i >= first; i--)
    {
        flag = 1;
        for(j = first; j != i; j++)
        {
            if(*j > *(j + 1))
            {
                tmp = *j;
                *j = *(j + 1);
                *(j + 1) = tmp;
                flag = 0;
            }
        }
    }
}

int main()
{
    int const N = 3;

    int Mass[3][3] = { { 3, 9, 7 },
                       { 1, 8, 5 },
                       { 4, 6, 2 } };
    int i, j;

    bsort(*Mass, *(Mass + N));

    for(i = 0; i < N; i++)
    {
        for(j = 0; j < N; j++)
            printf("%i ", Mass[i][j]);
        printf("\n");
    }

    _getch();
    return 0;
}

Автор: Dov 13.2.2010, 00:01

ещё вариант:

Код

#define N 5

void bubbleSort(int * arr, int size)
{
    int   n;
    int   t;
    int   tmp;
    int   k = 0;
    
    while(1)
    {
        t = 0;
        n = k;         // ограничиваем проход по массиву индексом последнего обмена

        for(int i = size - 1; i > n; i--)
        {
            if(arr[i - 1] > arr[i])
            {
                tmp        = arr[i - 1]; 
                arr[i - 1] = arr[i];
                arr[i]     = tmp;

                t = 1; // обмен произошёл, сортируем дальше
                k = i; // запоминаем индекс последнего обмена
            }
        }

        if(!t)
            break;     // массив отсортирован, выходим из цикла
    }
}

int main()
{    
    int matr[][N] = {
        13,  9,  7,  4, 20,
         1, 18, 23,  3, 12,
        14, 16, 22, 25, 19,
        11,  2,  8, 10, 24,
         5, 17,  6, 21, 15 
    };
    
    bubbleSort((int *)matr, N * N);
    
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < N; j++)
            printf("%3d", matr[i][j]);

        puts("");
    }
    
    return 0;
}

Автор: Fant87 13.2.2010, 19:22

Огромнейшее спасибо за помощь!!!

Автор: Ruslan19900200 16.2.2010, 22:59

Если очень интересно то зайди и видео посмотри там с объяснениями!
http://www.youtube.com/watch?v=JVNwRPD0grc&feature=related

Автор: Dov 17.2.2010, 01:04

Цитата(Ruslan19900200 @ 16.2.2010, 21:59

)

Если очень интересно то зайди и видео посмотри там с объяснениями!

Ruslan19900200, ты не туда запостил. smile

Это в ЮМОР нужно... smile