VPF::Сортировка "пузырьком". - Форум программистов

.talisman

Дата 20.2.2005, 15:25 (ссылка)

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

Загрузка ...

Новичок

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

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

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

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

Код


#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();
}

Это сообщение отредактировал(а) .talisman - 21.2.2005, 17:20

chaos

Дата 21.2.2005, 14:27 (ссылка)

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

Загрузка ...

Серийный программист

Профиль
Группа: Завсегдатай
Сообщений: 2979
Регистрация: 7.7.2004
Где: Екатеринбург

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

Цитата

int a[size];

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

Akina

Дата 21.2.2005, 14:43 (ссылка)

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

Загрузка ...

Советчик

Профиль
Группа: Модератор
Сообщений: 20581
Регистрация: 8.4.2004
Где: Зеленоград

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

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

Код


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

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

О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума.

maxim1000

Дата 21.2.2005, 14:56 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Участник
Сообщений: 3334
Регистрация: 11.1.2003
Где: Киев

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

Цитата

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], что не есть хорошо...

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

qqq

.talisman

Дата 21.2.2005, 16:44 (ссылка)

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

Загрузка ...

Новичок

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

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

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

chaos

Дата 21.2.2005, 16:49 (ссылка)

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

Загрузка ...

Серийный программист

Профиль
Группа: Завсегдатай
Сообщений: 2979
Регистрация: 7.7.2004
Где: Екатеринбург

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

Цитата

верно

не усмотрел

.talisman

Дата 21.2.2005, 17:00 (ссылка)

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

Загрузка ...

Новичок

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

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

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

Doc_d0s

Дата 21.2.2005, 21:35 (ссылка)

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

Загрузка ...

Бывалый

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

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

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

Код


#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;
}

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

Админ- это вождь Apache'й :)

kostyantmb

Дата 28.2.2005, 16:25 (ссылка)

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

Загрузка ...

Шустрый

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

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

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

Код


#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 (ссылка)

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

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 67
Регистрация: 23.2.2005
Где: Израиль

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

Цитата(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 (ссылка)

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

Загрузка ...

Шустрый

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

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

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

Enya

Дата 15.10.2005, 13:52 (ссылка)

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

Загрузка ...

Опытный

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

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

Код


#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;
                                        }    
                                    }    
                                }
                            }

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

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

Утсанвлен Денвер
1. PHP Version 5.1.6
2. MySQL 5.0.18-max
3. phpMyAdmin 2.6.1

_hunter

Дата 17.10.2005, 11:32 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Участник Клуба
Сообщений: 8564
Регистрация: 24.6.2003
Где: Europe::Ukraine:: Kiev

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

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

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

Tempora mutantur, et nos mutamur in illis...

Enya

Дата 17.10.2005, 18:13 (ссылка)

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

Загрузка ...

Опытный

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

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

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

Код


#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.

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

Утсанвлен Денвер
1. PHP Version 5.1.6
2. MySQL 5.0.18-max
3. phpMyAdmin 2.6.1

Enya

Дата 18.10.2005, 21:03 (ссылка)

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

Загрузка ...

Опытный

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

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

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

Код


#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);
}

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

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

Утсанвлен Денвер
1. PHP Version 5.1.6
2. MySQL 5.0.18-max
3. phpMyAdmin 2.6.1

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