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

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

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

Автор: THandle 13.3.2008, 12:44

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

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

Берутся два рядом стоящих элемента массива, и если элемент с меньшим
индексом больше элемента с большим индексом, то они меняются местами.
Эти действия происхдят до тех пор, пока массив не будет отсортирован.
Алгоритм проходит по массиву от начала до конца. В процессе работы алгоритма
находится элемент с максимальным значением, который помещается в конец массива,
поэтому каждый раз количество просматриваемых сортировкой элементов массива
уменьшается на 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

Авторы:

http://vingrad.ru/@THandle - идея, теория, пример на Pascal, пример на С++.
http://vingrad.ru/@Rrader - пример на С++, пример на VB.

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

Автор: JackYF 13.3.2008, 20:58

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

Код


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

Автор: THandle 13.3.2008, 21:06

JackYF, спасибо. +1.

Автор: inside_pointer 19.3.2008, 09:19

С инета

Код


/*   сортировка   пузырьковым   методом           */
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);
         }

Автор: Rrader 7.5.2008, 14:27

Ещё мой вариант на 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();    
        }
        
    }

Автор: THandle 8.5.2008, 09:37

Rrader, smile

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

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

на:

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

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

Автор: Ripper 8.5.2008, 17:30

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

Автор: Stqs 6.7.2008, 16:44

вот 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]);
        }
    }
}

Автор: Hades 10.8.2008, 12:12

Мой вариант исходника на 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(когда массив уже отсортирован).

Автор: iff 5.11.2010, 20:28

Компилятор 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:59

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

Автор: igorrr37 21.12.2010, 03:44

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

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

Автор: feodorv 28.2.2014, 17:32

Цитата(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)

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

Автор: futamator 6.2.2017, 23:20

Благодарю за такую статейку. Весьма полезно для новичков и не только)

Автор: jangogo 5.9.2017, 11:27

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

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