Модераторы: Poseidon
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> [FAQ][Pascal|C++|VB|C#] Сортировка массива методом "пузырька" 
:(
    Опции темы
THandle
Дата 13.3.2008, 12:44 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Хранитель Клуба
Group Icon
Награды: 1



Профиль
Группа: Админ
Сообщений: 3639
Регистрация: 31.7.2007
Где: Moscow, Dubai

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



Сортировка массива методом пузырька.

Алгоритм сортировки такой: 

  Берутся два рядом стоящих элемента массива, и если элемент с меньшим
индексом больше элемента с большим индексом, то они меняются местами.
Эти действия происхдят до тех пор, пока массив не будет отсортирован.
Алгоритм проходит по массиву от начала до конца. В процессе работы алгоритма
находится элемент с максимальным значением, который помещается в конец массива,
поэтому каждый раз количество просматриваемых сортировкой элементов массива
уменьшается на 1. Каждый раз на своё место становится хотя бы один элемент массива,
поэтому количество проходов по нему равно количеству элементов в массиве.
Алгоритм называется пузырьковым, так как максимальный элемент массива как бы 
всплывает наверх.



Пример на Паскале:


Код

program BSort;

const
  MAX = 5;

type
  TArray = array [1..MAX] of integer;

procedure PrintArray(iArray : TArray);
var
  i : integer;
begin
  for i := 1 to MAX do
    WriteLn(iArray[i]);
end;


procedure Swap(var iArray : TArray; iPos1, iPos2 : integer);
var
  tmp : integer;
begin
  tmp := iArray[iPos1];
  iArray[iPos1] := iArray[iPos2];
  iArray[iPos2] := tmp;
end;

procedure BubbleSort(var iArray : TArray);
var
  i, j : integer;
begin
  for i := 1 to MAX - 1 do
    for j := 1 to MAX - i do
      if iArray[j] > iArray[j+1] then
         swap(iArray, j, j + 1);
end;

var
  IArray : TArray;
  i : integer;
begin
  for i := 1 to MAX do
    begin
      write('Enter element: ');
      readln(iArray[i]);
    end;
  PrintArray(IArray);
  BubbleSort(IArray);
  writeln('After sort: ');
  PrintArray(IArray);
  readln;
end.



Пример на С++:

Код

#include <iostream>

using namespace std;

const
  MAX = 5;
  
void Swap(int arr[], int pos1, int pos2)
{
  int tmp;
  tmp = arr[pos1];
  arr[pos1] = arr[pos2];
  arr[pos2] = tmp;
}

void PrintArray(int arr[])
{
  for(int i = 0; i < MAX;  ++i)
    cout << arr[i] << endl;
}

void BubbleSort(int arr[])
{
  int i, j;
  for(i = 0; i < MAX - 1; ++i)
    for(j = 0; j < MAX - i; ++j)
      if (arr[j] > arr[j + 1])
        Swap(arr, j , j + 1);
}

int main()
{
  int arr[MAX];
  int i;
  for (i = 0; i < MAX; ++i)
    {
      cout << "Enter element: " << endl;
      cin >> arr[i];
    }
  PrintArray(arr);
  BubbleSort(arr);
  cout << "After sort: " << endl;
  PrintArray(arr);
  char r;
  cin >> r;
  return 0;
}



Пример на Visual Basic:

Код

Option Base 0

  Sub BubbleSort(ByRef M() As Long)
  Dim I, J, Tmp, N As Long
    N = UBound(M)
    For I = 0 To N
      For J = 0 To N - 1
        If M(J) > M(J + 1) Then
          Tmp = M(J)
          M(J) = M(J + 1)
          M(J + 1) = Tmp
        End If
      Next J
    Next I
End Sub

Private Sub Command1_Click()
  'Пример использования
  Dim A(0 To 5) As Long
  A(0) = 7
  A(1) = 1
  A(2) = 5
  A(3) = 4
  A(4) = 2
  A(5) = 15
  Call BubbleSort(A)
  'Массив отсортирован и готов к использованию!
End Sub



Авторы:

THandle - идея, теория, пример на Pascal, пример на С++.
Rrader - пример на С++, пример на VB.


Пример сортировки на С# смотрите в конце темы.

Это сообщение отредактировал(а) THandle - 7.5.2008, 19:58
PM   Вверх
JackYF
Дата 13.3.2008, 20:58 (ссылка) |    (голосов:3) Загрузка ... Загрузка ... Быстрая цитата Цитата


полуавантюрист
****


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

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



Мой вариант исходника на С++:
Код

#include <iostream>
#include <algorithm>

using std::cout;
using std::cin;
using std::endl;
using std::swap;

const size_t MAX = 5;

void printArray(int arr[])
{
    for(size_t i = 0; i < MAX; ++i)
    {   
        cout << arr[i] << endl;
    }   
}

void bubbleSort(int arr[])
{
    size_t i, j;
    for(i = 1; i < MAX; ++i)
        for(j = 0; j < MAX - i; ++j)
            if (arr[j] > arr[j+1])
            {
                swap(arr[j], arr[j+1]);
            }
}

int main()
{
    int arr[MAX];
    for (size_t i = 0; i < MAX; ++i)
    {   
        cout << "Enter element: " << endl;
        cin >> arr[i];
    }   
    printArray(arr);
    bubbleSort(arr);
    cout << "After sort: " << endl;
    printArray(arr);
    return 0;
}



--------------------
Пожаловаться на меня как модератора можно здесь.
PM MAIL Jabber   Вверх
THandle
Дата 13.3.2008, 21:06 (ссылка) |    (голосов:3) Загрузка ... Загрузка ... Быстрая цитата Цитата


Хранитель Клуба
Group Icon
Награды: 1



Профиль
Группа: Админ
Сообщений: 3639
Регистрация: 31.7.2007
Где: Moscow, Dubai

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



JackYF, спасибо. +1.
PM   Вверх
inside_pointer
Дата 19.3.2008, 09:19 (ссылка)    | (голосов:5) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


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

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



С инета

Код

/*   сортировка   пузырьковым   методом           */
float * bubble(float * a, int m, int n)
         {
          char is = 1;
          int i;
          float c;
          
          while(is)
           {
            is = 0;
            for (i = m + 1; i <= n; i++)
             if ( a[i] < a[i-1] ) { c = a[i]; a[i] = a[i-1]; a[i-1] = c; is = 1; }
           }
          
          return(a);
         }

PM MAIL   Вверх
Rrader
  Дата 7.5.2008, 14:27 (ссылка) |    (голосов:2) Загрузка ... Загрузка ... Быстрая цитата Цитата


Inspired =)
***


Профиль
Группа: Экс. модератор
Сообщений: 1535
Регистрация: 7.5.2005

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



Ещё мой вариант на C#:
Код

using System;

    class BubbleSortClass
    {    
     public const int Max = 5;
     
     int[] Array = new int[Max];
     
     public void GetArray()
     {
         for (int i = 0; i < Max; ++i)
         {
             Console.Write("Enter element: ");
             string S = Console.ReadLine();
             int Value = int.Parse(S);
             Array[i] = Value;
         }
             
     }
     
     private void Swap(int FElem, int SecElem)
     {
         int tmp;
            tmp = Array[FElem];
            Array[FElem] = Array[SecElem];
            Array[SecElem] = tmp;
     }
     
     public void PrintArray()
     {
         for (int i = 0; i < Max; ++i)
             Console.WriteLine(Array[i]);
     }
     
     public void BubbleSort()
     {  
         int i, j;
         
         for (i = 1; i < Max; ++i)         
             for (j = 0; j < Max - i; ++j)
                 if (Array[j] > Array[j + 1])
                 {
                      Swap(j, j + 1);
                 }
             
         
     }
    }

    class BubbleSortApp
    {
        public static void Main(string[] args)
        {
            BubbleSortClass BCS = new BubbleSortClass();
            BCS.GetArray();
            Console.WriteLine("Before sort:");
            BCS.PrintArray();
            BCS.BubbleSort();
            Console.WriteLine("After sort:");
            BCS.PrintArray();       
            Console.ReadLine();    
        }
        
    }


Это сообщение отредактировал(а) Rrader - 7.5.2008, 19:39


--------------------
Let's do this quickly!
Rest in peace, Vit!
PM MAIL Skype   Вверх
THandle
Дата 8.5.2008, 09:37 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Хранитель Клуба
Group Icon
Награды: 1



Профиль
Группа: Админ
Сообщений: 3639
Регистрация: 31.7.2007
Где: Moscow, Dubai

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



Rrader,  smile 

Название темы поменял с:

[FAQ][Pascal|C++|VB] Сортировка массива методом "пузырька"

на:

[FAQ][Pascal|C++|VB|C#] Сортировка массива методом "пузырька"

Давайте еще киньте кто-нибудь на Яве. На ассемблере может быть напишу smile 
PM   Вверх
Ripper
Дата 8.5.2008, 17:30 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Lonely soul...
**


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

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



В википедии там на многих языках написано уже все %)


--------------------
"Он знает: надо смеяться над тем, что тебя мучит, иначе не сохранишь равновесия, иначе мир сведет тебя с ума" - Над кукушкиным гнездом
PM MAIL ICQ   Вверх
Stqs
Дата 6.7.2008, 16:44 (ссылка) |    (голосов:2) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



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

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



вот Java
Код

public class Bubble {
    public static void main(String[] args){
        int[] array = new int[10];
        System.out.println("Заполняем случайными числами и выводим массив");
        for (int i=0; i<10; i++){
            array[i] = (int)Math.floor(Math.random()*1000);
            System.out.println(i+"-й: "+array[i]);
        }
        //сортируем массив
        int tmp;
        for (int j=0;j<9;j++){
            for (int k=0;k<j;k++){
                if (array[k]>array[k+1]){
                    tmp = array[k];
                    array[k] = array[k+1];
                    array[k+1] = tmp;
                }
            }
        }        
        System.out.println("Выводим отсортированный массив");
        for (int i=0; i<9; i++){
            System.out.println(i+"-й: "+array[i]);
        }
    }
}


Это сообщение отредактировал(а) Stqs - 6.7.2008, 16:50
PM MAIL ICQ Skype   Вверх
Hades
Дата 10.8.2008, 12:12 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


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

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



Мой вариант исходника на Java:
Код

public class Sort {
    
    // сортирует 'length' элементов массива 'array', начиная с индекса 'index' 
    public static void bubbleSort(int array[], int index, int length) {
        boolean changes;
        int i = 1;

        do {
            changes = false;

            for (int j = index; j < length - i; ++j)
                if (array[j] > array[j+1]) {
                    int temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                    
                    changes = true;
                }

            ++i;

        } while(changes); // если нет изменений выходим из цикла
    }
    
}

Код

public class SortApp {

    public static void main(String[] args) {
        int array[] = createArray(10);
        System.out.println("Before sort:");
        printArray(array);
        Sort.bubbleSort(array, 0, array.length); // сортируем весь массив
        System.out.println("\nAfter sort:");
        printArray(array);
        
        System.out.println("\n");
        
        array = createArray(10);
        System.out.println("Before sort:");
        printArray(array);
        // от элемента с индексом 2, сортируем (array.length - 2) элементов
        Sort.bubbleSort(array, 2, array.length - 2);
        System.out.println("\nAfter sort:");
        printArray(array);
    }
    
    public static int[] createArray(int length) {
        int array[] = new int[length];
        
        // заполняем массив случайными числами, от 0(нуля) до 100 
        for (int i = 0; i < length; ++i)
            array[i] = (int)(Math.random() * 100); 
        
        return array;
    }
    
    public static void printArray(int array[]) {
        for (int i = 0; i < array.length; ++i)
            System.out.print(array[i] + "  ");
    }

}



Цитата(JackYF @  13.3.2008, 20:58 Найти цитируемый пост)

Код

void bubbleSort(int arr[])
{    
    size_t i, j;    

    for(i = 1; i < MAX; ++i)        
        for(j = 0; j < MAX - i; ++j)           
            if (arr[j] > arr[j+1])            
            {                
                swap(arr[j], arr[j+1]);            
            }
}


Этот вариант всегда сравнивает элементы (1+2+3+...+Max-1) раз,
когда Max = 5, количество сравнений элементов - 10(1+2+3+4) всегда.

в моём варианте количества сравнений элементов, при Max = 5, 
только в худшем случаи будет 10, а в лучшем 4(когда массив уже отсортирован).


Это сообщение отредактировал(а) Hades - 10.8.2008, 12:18
PM MAIL   Вверх
iff
Дата 5.11.2010, 20:28 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Администратор
**


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

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



Компилятор TASM, для DOS, для Intel8086+. Сортировка массива однобайтных знаковых чисел по возрастанию.
Код


          ...

Arr     DB      120,9,5,-10
ArrLen  DW      $ - OFFSET Arr

          ...

        MOV     CX,ArrLen
        DEC     CX
        MOV     SI,1
S10:    PUSH    CX
        MOV     CX,ArrLen
        SUB     CX,SI
        LEA     DI,Arr
S20:    MOV     AL,[DI]
        CMP     AL,[DI+1]
        JL      S30
        XCHG    AL,[DI+1]
        MOV     [DI],AL
S30:    INC     DI
        LOOP    S20
        INC     SI
        POP     CX
        LOOP    S10

          ...


Обратите внимание на инструкцию в строке 17. При использовании других инструкций условного перехода можно изменить принцип сортировки:
JA - беззнаковые числа по убыванию
JB - беззнаковые числа по возрастанию
JG - знаковые числа по убыванию
JL - знаковые числа по возрастанию

Это сообщение отредактировал(а) iff - 5.11.2010, 20:53


--------------------
DOS... Синей пеленой экран заполнил чистый DOS 
Мышь... Стала вдруг квадратной, потеряла форму мышь... 
Я разбил окно, девяностопятое мастдайное окно, 
И поставил DOS, и тогда увидел: Это счастье, — вот оно.  
PM MAIL WWW   Вверх
iff
Дата 5.11.2010, 20:59 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Администратор
**


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

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



При сортировки масиива слов (длина элементов - 2 байта). Следует изменить строки:
в 4-ой - заменить $ - OFFSET Arr на ($ - OFFSET Arr) / 2
в 16-ой и в 18-ой - заменить [DI+1] на [DI+2]
в 20-ой - добавить ещё одну инструкцию INC DI


--------------------
DOS... Синей пеленой экран заполнил чистый DOS 
Мышь... Стала вдруг квадратной, потеряла форму мышь... 
Я разбил окно, девяностопятое мастдайное окно, 
И поставил DOS, и тогда увидел: Это счастье, — вот оно.  
PM MAIL WWW   Вверх
igorrr37
Дата 21.12.2010, 03:44 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



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

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



>поэтому количество проходов по нему равно количеству элементов в массиве.

Если в массиве два элемента, по нему достаточно пройти один раз, если три-два раза, т.е. число проходов на единицу меньше числа элементов.
PM MAIL   Вверх
feodorv
Дата 28.2.2014, 17:32 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Комодератор
Сообщений: 2214
Регистрация: 30.7.2011

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



Цитата(THandle @  13.3.2008,  13:44 Найти цитируемый пост)
void BubbleSort(int arr[])
{
  int i, j;
  for(i = 0; i < MAX - 1; ++i)
    for(j = 0; j < MAX - i; ++j)
      if (arr[j] > arr[j + 1])
        Swap(arr, j , j + 1);
}

Здесь присутствует выход за пределы массива: когда i есть 0, а j становится MAX-1, имеем arr[MAX].
Цитата(JackYF @  13.3.2008,  21:58 Найти цитируемый пост)
    for(i = 1; i < MAX; ++i)
        for(j = 0; j < MAX - i; ++j)

А вот здесь выхода за пределы массива нет)))


--------------------
Напильник, велосипед, грабли и костыли - основные инструменты программиста...
PM MAIL   Вверх
futamator
Дата 6.2.2017, 23:20 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



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

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



Благодарю за такую статейку. Весьма полезно для новичков и не только) 
PM MAIL   Вверх
jangogo
Дата 5.9.2017, 11:27 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



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

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



Спасибо, ребята! Большое дело делаете!)

Добавлено через 1 минуту и 45 секунд
Спасибо, ребята! Большое дело делаете!)
PM MAIL   Вверх
  
Ответ в темуСоздание новой темы Создание опроса
Правила форума "Центр помощи"

ВНИМАНИЕ! Прежде чем создавать темы, или писать сообщения в данный раздел, ознакомьтесь, пожалуйста, с Правилами форума и конкретно этого раздела.
Несоблюдение правил может повлечь за собой самые строгие меры от закрытия/удаления темы до бана пользователя!


  • Название темы должно отражать её суть! (Не следует добавлять туда слова "помогите", "срочно" и т.п.)
  • При создании темы, первым делом в квадратных скобках укажите область, из которой исходит вопрос (язык, дисциплина, диплом). Пример: [C++].
  • В названии темы не нужно указывать происхождение задачи (например "школьная задача", "задача из учебника" и т.п.), не нужно указывать ее сложность ("простая задача", "легкий вопрос" и т.п.). Все это можно писать в тексте самой задачи.
  • Если Вы ошиблись при вводе названия темы, отправьте письмо любому из модераторов раздела (через личные сообщения или report).
  • Для подсветки кода пользуйтесь тегами [code][/code] (выделяйте код и нажимаете на кнопку "Код"). Не забывайте выбирать при этом соответствующий язык.
  • Помните: один топик - один вопрос!
  • В данном разделе запрещено поднимать темы, т.е. при отсутствии ответов на Ваш вопрос добавлять новые ответы к теме, тем самым поднимая тему на верх списка.
  • Если вы хотите, чтобы вашу проблему решили при помощи определенного алгоритма, то не забудьте описать его!
  • Если вопрос решён, то воспользуйтесь ссылкой "Пометить как решённый", которая находится под кнопками создания темы или специальным флажком при ответе.

Более подробно с правилами данного раздела Вы можете ознакомится в этой теме.

Если Вам помогли и атмосфера форума Вам понравилась, то заходите к нам чаще! С уважением, Poseidon, Rodman

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


 




[ Время генерации скрипта: 0.2164 ]   [ Использовано запросов: 23 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.