PDA

Просмотр полной версии : помогите с кодом на С++ или С



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

Albor
21.05.2009, 13: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
21.05.2009, 14: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++;
}
}