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

Поиск:

Добавить материал
 

[FAQ][Pascal|C++|VB|C#] Сортировка массива методом "пузырька"
THandle
Репутация: 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


Комментарии посетителей:


Дата 13.3.2008, 20:58 (ссылка) |    (голосов:3) Загрузка ... Загрузка ... Быстрая цитата Цитата
JackYF ****   Репутация: 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   Вверх

Дата 13.3.2008, 21:06 (ссылка) |    (голосов:3) Загрузка ... Загрузка ... Быстрая цитата Цитата
THandle Group Icon   Репутация: 30  Всего: 372 
JackYF, спасибо. +1.
PM WWW   Вверх

Дата 19.3.2008, 09:19 (ссылка)    | (голосов:5) Загрузка ... Загрузка ... Быстрая цитата Цитата
inside_pointer **   Репутация: нет  Всего: 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   Вверх

  Дата 7.5.2008, 14:27 (ссылка) |    (голосов:2) Загрузка ... Загрузка ... Быстрая цитата Цитата
Rrader ***   Репутация: 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
PM MAIL   Вверх

Дата 8.5.2008, 09:37 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата
THandle Group Icon   Репутация: 30  Всего: 372 
Rrader,  smile 

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

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

на:

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

Давайте еще киньте кто-нибудь на Яве. На ассемблере может быть напишу smile 
PM WWW   Вверх

Дата 8.5.2008, 17:30 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата
Ripper **   Репутация: 6  Всего: 23 
В википедии там на многих языках написано уже все %)
PM MAIL ICQ   Вверх

Дата 6.7.2008, 16:44 (ссылка) |    (голосов:2) Загрузка ... Загрузка ... Быстрая цитата Цитата
Stqs   Репутация: 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   Вверх

Дата 10.8.2008, 12:12 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата
Hades *   Репутация: 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   Вверх

Дата 5.11.2010, 20:28 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата
iff **   Репутация: 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
PM MAIL WWW   Вверх

Дата 5.11.2010, 20:59 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата
iff **   Репутация: 3  Всего: 16 
При сортировки масиива слов (длина элементов - 2 байта). Следует изменить строки:
в 4-ой - заменить $ - OFFSET Arr на ($ - OFFSET Arr) / 2
в 16-ой и в 18-ой - заменить [DI+1] на [DI+2]
в 20-ой - добавить ещё одну инструкцию INC DI
PM MAIL WWW   Вверх

Дата 21.12.2010, 03:44 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата
igorrr37   Репутация: нет  Всего: нет 
>поэтому количество проходов по нему равно количеству элементов в массиве.

Если в массиве два элемента, по нему достаточно пройти один раз, если три-два раза, т.е. число проходов на единицу меньше числа элементов.
PM MAIL   Вверх

Дата 28.2.2014, 17:32 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата
feodorv ****   Репутация: нет  Всего: 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   Вверх

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

Дата 5.9.2017, 11:27 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата
jangogo   Репутация: нет  Всего: нет 
Спасибо, ребята! Большое дело делаете!)

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

  
 
Правила форума "Центр помощи"

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


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

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

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

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


 




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


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

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