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

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

Форум программистов > C/C++: Общие вопросы > Сортировка "пузырьком".

Автор: .talisman 20.2.2005, 15:25

Написал на Си сортировку пузырьком. Знаю, что очень медленно работает -- скорость прямопропорционально зависит от количества элементов массива. Писал из-за того, что недавно проходили её в шараге, она самая простая для понимания и её нам нужно постоянно использовать.

Собственно далее привожу код программы, может кому-то и пригодится.

Код


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

void sort(int *a, const size)
{
   int i, j;  	//counts
   int tmp, flag;  //tmp box for change elements and flag for sort over

   for(i=0; i<size-1; i++)	//first-last buble up
   {
    flag=0;
    for(j=0; j<size; j++)	//cycle comparison of numbers
      {
      	if(a[j]>a[j+1])	// for sorted desc, change '>' to '<'
         {
         tmp=a[j];
         a[j]=a[j+1];
         a[j+1]=tmp;
         flag=1;
         }
  }
      if(flag!=1)
      {
       break;
      }
   }
}

void main()
{
   int size=10;    	//array size
   int *a; a=new int[size];	//array
   int i;      	//count

   for(i=0; i<size; i++)	//enter elements in array
   {
      printf("enter element in a[%d]: ", i);
    scanf("%i", &a[i]);
   }

   sort(a, size);

   printf("\n\nsorted array: \n");  //print elements
	for(i=0; i<size; i++)
      {
    	printf("%i ", a[i]);
      }
   getch();
}

Автор: chaos 21.2.2005, 14:27

Цитата

int a[size];

вот эту строку я бы заменил int *a = new int[size]; я думаю так более правельно

Автор: Akina 21.2.2005, 14:43

Вообще-то классическая сортировка пузырем ака камнем - это

Код


for(i=0; i<size-1; i++)
  {
  for(j=i+1; j<size; j++) 
    {

Автор: maxim1000 21.2.2005, 14:56

Цитата

for(j=0; j<size; j++) //cycle comparison of numbers
{
if(a[j]>a[j+1]) // for sorted desc, change '>' to '<'

когда j будет равен size-1, j+1 будет равен size
а значит, будет попытка обратиться к a[size], что не есть хорошо...

Автор: .talisman 21.2.2005, 16:44

chaos как я понимаю это уже динамический массив.
можно и так, для большей гибкости. тогда нужно будет изменить "const size" на "int size" smile

Автор: chaos 21.2.2005, 16:49

Цитата

верно

не усмотрел

Автор: .talisman 21.2.2005, 17:00

Akina
maxim1000
согласен, исправим-с =)

Автор: Doc_d0s 21.2.2005, 21:35

Вот мой вариант:

Код


#include <conio.H>
#include <stdio.h>
int main()
{
	FILE*qi;
	const n=10;
	int a[n],i,x,j,n1,t=0;
	
	qi=fopen("C:\\in2.txt","r");
	for(i=0;i<n;i++)
  fscanf(qi,"%d",&a[i]);
	fclose(qi);
	
	printf("\nPervohachalniy massiv:\n");
	for(i=0;i<n;i++)
	{
  printf(" %d ",a[i]);
	}
	printf("\n");
	n1=n;
	do
	
	{
  
	for (j=0; j<=n1-1; j++)
	{
  if (a[j]>a[j+1])
  	{
    x=a[j];
    a[j]=a[j+1];
    a[j+1]=x;
    t=j;
  	}
	}
	n1=t;
}
while (t!=0);

printf("\nPervohachalniy massiv:\n");
	for(i=0;i<n;i++)
	{
  printf(" %d ",a[i]);
	}
	printf("\n");
	getch();
	return 0;
}

Автор: kostyantmb 28.2.2005, 16:25

Попробуй это:

Код


#include <iostream>
using namespace std;
//========================================================
int array[100];
//========================================================
void Sort(int col)
{
    int trash=0;
    bool f=true;
    for (int i=1;  (i<=col) && (f=true) ;  i++)
      {
         f=false;
         for (int j=1;  j<=col-i;  j++)
            {
               if (array [j]>array [j+1])
                 {
                    trash=array[j];
                    array [j]=array [j+1];
                    array [j+1]=trash;
                    f=true;
                 }
            }
      }
}
//========================================================
void Out(int col)
{
   for (int i=1;  i<=col;  i++)
     cout << array [i] <<" ";
   cout << endl;
}
//========================================================
int main()
{
   int col_el;
   
   cout << "  Enter length of array"<< endl;
   cin >> col_el;         
       for (int n=1; n<=col_el; n++)       
   cin >> array[n];
   Sort(col_el);	
   cout << "Result is :"<<endl;        	
   Out(col_el);          	
   cin >> col_el;          
   return 0;
}
<##############################################################################>

Используется дополнительная булевская переменная F.
При каждом заходе в первый цикл ей присваивается значение false и если в процессе выполнения
один из элементов будет не отсортирован, то значение этой переменной меняется на true
и первый цикл продолжается дальше. Если значение не поменялось, то это значит, что уже нечего
сортировать.

Данная сортировка выполняет n*(n-1)*(n-2)*...*(2)*(1) операций в худшем случае.

Автор: Goryachev 28.2.2005, 23:04

Цитата(kostyantmb @ 28.2.2005, 16:25)

Данная сортировка выполняет n*(n-1)*(n-2)*...*(2)*(1) операций в худшем случае.

Ты имел ввиду n+(n-1)+(n-2)+...+(2)+(1)

Автор: kostyantmb 2.3.2005, 11:59

Да, именно так!

Автор: Enya 15.10.2005, 13:52

Код


#include <string.h>
#include <stdio.h>
#include <stdlib.h>
          
void bubble(char *items, int count);
        int main(void){
            
            char s[255];
            
            printf("Insert string:");
            gets(s);
            bubble(s, strlen(s));
            printf("Sorting string: %s.\n", s);
            
            return 0;
        }    
void bubble(char *items, int count){
                register int a, b;
                register char t;
                
                                for(a=1;a<count; ++a){
                                    for(b=count-1; b>=a; --b){
                                        if(items[b-1]>items[b]){
                                            t=items[b-1];
                                            items[b-1]=items[b];
                                            items[b]=t;
                                        }    
                                    }    
                                }
                            }

Как сделать пошаговый вывод цикла? Ну, чтоб наглядно увидеть всю сортировку?

Автор: _hunter 17.10.2005, 11:32

после перестановки элементов ( а именно if(items[b-1]>items[b]){ ) выводи циклом весь массив

Автор: Enya 17.10.2005, 18:13

Предлагаю ещё вариант сортировки методом "пузырька".
Сортрует не числа, а строчку. Мне кажется так не много проще.

Код


#include <string.h>
#include <stdio.h>
#include <stdlib.h>
          
void bubble(char *items, int count);
        int main(void){
            
            char s[255];
            
            printf("Insert string:");
            gets(s);
            bubble(s, strlen(s));
            printf("Sorting string: %s.\n", s);
            
            return 0;
        }    
void bubble(char *items, int count){
                register int a, b, i;
                register int t;
                
                                for(a=1;a<count; ++a){
                                    for(b=count-1; b>=a; --b){
                                        if(items[b-1]>items[b]){
                                            printf("-->%s\n",items);                                            
                                            t=items[b-1];
                                            items[b-1]=items[b];
                                            items[b]=t;
                                        }    
                                    }    
                                }
                            }

Если есть ошибки в коде, прошу репортировать мне в PM.

Автор: Enya 18.10.2005, 21:03

Если после меня никто не постил, значит скорее всего код правильный, мот предлагаю модифицированную сортировку методом "пузырька"

Код


#include <string.h>
#include <stdio.h>
#include <stdlib.h>
          
void shaker(char *items, int count);
        int main(void){
            
            char s[255];
            
            printf("Insert string:");
            gets(s);
            shaker(s, strlen(s));
            printf("Sorting string: %s.\n", s);
            
            return 0;
        }    
void shaker(char *items, int count){
    register int a;
    int exchange;
    char t;
        do{
            exchange=0;
                        for(a=count-1;a>0;--a){
                            if(items[a-1]>items[a]){
                                t = items[a-1];
                                items[a-1]=items[a];
                                items[a]=t;
                                exchange=1;
                            }    
                        }    
                        for(a=1;a<count; ++a){
                            if(items[a-1]>items[a]){
                                t = items[a-1];
                                items[a-1]=items[a];
                                items[a]=t;
                                exchange=1;
                            }
                       }
                       printf("-->%s\n",items);      
        }    while(exchange);
}

Прошу, коментируем, предлагаем...