помогите с кодом на С++ или С

Ответить
Ramon
Сообщения: 11
Зарегистрирован: 13 окт 2008, 16:44

помогите с кодом на С++ или С

Сообщение Ramon » 20 май 2009, 23:41

задача состоит в сортировке массива методои пузырька.
написать прогу сортировки произвольно заполненного массива по возрастанию.
p.s. я знаю что в инете много подобных алгаритмов но просьба дать ссылку или написать с коментариями чтобы было понятно даже новечку прост мне надо будет объяснить решение а я не очень то и рублю в с++
p.s.s заранее большое спасибо всем откликнувшимся)

Albor
Сообщения: 482
Зарегистрирован: 06 сен 2004, 12:34
Откуда: Днепропетровск

Re: помогите с кодом на С++ или С

Сообщение Albor » 21 май 2009, 12:09

Код: Выделить всё

#include <iostream.h>

void swap(int & a, int & b)
{//Функция меняет местами 2 переменные
//параметры передаются по ссылке, чтобы 
//ф-ция работала с оригиналами переменных,
//а не их копиями
    int c=a;//сохраняем а
    a=b;//копируем b в а
    b=c;//копируем в b с
}
int bubble_sort(int * const pFirst, int * const pLast, int & iter)
{
    //входные указатели константные, чтобы наша ф-ция их не изменила
    int perest(0);//посчитаем перестановки, чтобы оценить,
    // что данный способ сортировки годится только как учебный пример
    // переменная iter посчитает к-во итераций цикла, для тех-же целей
    // эта переменная внешняя - для получения результата
    bool b(false);// флаг, чтобы знать, были ли перестановки за весь проход по массиву
    //если их небыло, то цикл завершим
    int * p=pFirst;// p нам нужно для перемещения по массиву
    while(true)//работаем "от сюда и до обеда"
    {
        ++iter;//увеличим счётчик итераций
        if(*p>*(p+1))// сравним содержимое массива по адресу p и следующему за ним p+1
        {
            swap(*p,*(p+1));//переставим значения, раз уж первое больше второго
            ++perest;//увеличим счётчик перестановок
            b|=!b;// установим флаг в true
        }
        ++p;//переходим к следующей ячейке массива
        if(p==pLast-1) // если дошли до конца
        {
            if(b)//проверим флаг. если установлен, то
            {
                p=pFirst;//возвращаемся в начало массива
                b^=b;// сбрасываем флаг
            }
            else // иначе, выходим из цикла, так как ни одной перестановки небыло
                break;
        }
        
    }
    
    return perest;//вернём подсчёты
}
void main()
{
    int iter(0);// здесь будет к-во итераций после сортировки
    const int N(10);//размер массива
    int A[N]={9,8,7,6,5,4,3,2,1,0};//подопытный кролик
    int cnt=bubble_sort(A,A+N,iter);
    for (int i =0;i<N;i++) // покажем что получилось
        cout<<*(A+i)<<" ";
    cout<<endl<<"k-vo perestanovok "<<cnt<<endl;
    cout<<"k-vo iteraciy "<<iter<<endl;
 
}
Наверное достаточно подробно :) ! Переменные счётчиков можно и опустить, но тогда не будет ощущения того, что данным методом лучше не пользоваться. Ну и, конечно, для сравнения нужно написать более серьёзную сортировку, если есть желание учиться.

Rycharg
Сообщения: 28
Зарегистрирован: 15 апр 2009, 13:23
Откуда: SPb

Re: помогите с кодом на С++ или С

Сообщение Rycharg » 21 май 2009, 13:22

Если пример исключительно учебный, то можно и лаконичней.

Код: Выделить всё

void BubbleSort(int *arr, int size){
   int tmp;
   for(int i = size - 1; i > 0; --i){ // Работаем не до обеда, а полный рабочий день :)
      for(int x = 0; x < i; ++x){
         if( arr[ x ] > arr[ x + 1 ] ){ // Переставляем на месте.
            tmp          = arr[ x ];
            arr[ x ]     = arr[ x + 1 ];
            arr[ x + 1 ] = tmp;
         }
      }
   }
}

--------------------------------------------------------------------------------
Добавлено сообщение
--------------------------------------------------------------------------------
Или так.

Код: Выделить всё

void BubbleSort(int *arr, int size){
   int *s = arr, *f = s++;
   int tmp;
   for(int i = --size; i > 0; --i){
      for(int x = i; x > 0; --x){
         if( *f > *s ){
            tmp = *f;
            *f  = *s;
            *s  = tmp;
         }
         f = s++;
      }
      s = arr;
      f = s++;
   }
}

Ответить