JavaRush/Курсы/Harvard CS50/Алгоритмы сортировки. Пузырьковая сортировка

Алгоритмы сортировки. Пузырьковая сортировка

Открыта

Внимание! Практически весь материал этой лекции был в видеолекции.

Если вы всё хорошо усвоили, просто пробегитесь глазами и переходите дальше.

Алгоритм у пузырьковой сортировки — один из простейших.

Идем вдоль всего массива и сравниваем 2 соседних элемента. Если они в неправильном порядке, меняем их местами. При первом проходе в конце окажется («всплывет») самый маленький элемент (если мы сортируем в порядке убывания).

Повторять первый шаг, если хотя бы один обмен на предыдущем шаге был совершен.

Давайте отсортируем массив.

Алгоритмы сортировки. Пузырьковая сортировка - 1

Шаг 1: идем по массиву. Алгоритм начинает работу с первых двух элементов, 8 и 6 и проверяет, находятся ли они в правильном порядке. 8 > 6, поэтому меняем их местами. Далее мы смотрим на второй и третий элементы, теперь это 8 и 4. Из тех же соображений меняем их местами. В третий раз сравниваем 8 и 2. Итого, мы делаем три обмена (8, 6), (8, 4), (8, 2). Значение 8 «всплыло» в конец списка на правильную позицию.

Алгоритмы сортировки. Пузырьковая сортировка - 2

Шаг 2: меняем местами (6,4) и (6,2). 6 теперь на предпоследней позиции, и её можно не сравнивать с уже отсортированным «хвостом» списка.

Алгоритмы сортировки. Пузырьковая сортировка - 3

Шаг 3: меняем местами 4 и 2. Четверка «всплывает» на свое законное место.

Алгоритмы сортировки. Пузырьковая сортировка - 4

Шаг 4: проходимся по массиву, но менять нам уже нечего. Это сигнализирует о том, что массив полностью отсортирован.

Алгоритмы сортировки. Пузырьковая сортировка - 5

А это — код алгоритма. Попробуйте реализовать его на Си!

Алгоритмы сортировки. Пузырьковая сортировка - 6

Пузырьковая сортировка проходит за время O(n²) в худшем случае (все числа стоят неправильно), поскольку нам нужно сделать n шагов на каждой итерации, которых тоже n. На самом деле, как и в случае с алгоритма сортировки выбором, время будет несколько меньше (n²/2 – n/2), но этим можно пренебречь.

В лучшем случае (если все элементы уже стоят на своем месте), мы справимся за n шагов, т.е. Ω(n), поскольку нам нужно будет просто пробежаться по массиву один раз и убедиться, что все элементы стоят на своих местах (т.е. даже n-1 элементов).

ПредыдущаяПредыдущая лекция

СледующаяСледующая лекция

Комментарии (25)

популярные
новые
старые

Для того, чтобы оставить комментарий Вы должны авторизоваться

Anonymous #3598185

Уровень 2

7 июля, 15:25

#include <stdio.h>
#include <string.h>


int main(void) {
    int array[8] = {6, 4, 1, 8, 3, 34, 23, 10};
    int changes;
    do
    {
        changes = 0;
        for (int i = 0; i < 8 - 1; i++) {
            if (array[i] > array[i+1]) {
                int q = array[i];
                array[i] = array[i+1];
                array[i+1] = q;
                changes++;
            }
        }
    }while(changes != 0);

    for (int i = 0; i < sizeof(array)/sizeof(array[0]); i++) {
        printf("%i ", array[i]);
    }

}

Iwan_Halliday

Уровень 1

6 ноября 2024, 09:37

>При первом проходе в конце окажется («всплывет») самый маленький элемент (если мы сортируем в порядке убывания). Возрастания же, да? Или в какую сторону мы считаем?)

FeatHonnar

Уровень 16

22 сентября 2022, 09:07

#include <cs50.h>
#include <stdio.h>
#include <string.h>

int main()
{
    string num = get_string("Ваше число:\n");
    int counter, n = strlen(num);

    do {
        counter = 0;
        for (int i = 0; i < n - 1; i++) {
            int j = i + 1;
            if (num[i] > num[j]) {
                int a = num[i];
                num[i] = num[j];
                num[j] = a;
                counter++;
            }
        }
    }
    while (counter > 0);
    printf("%s", num);
}

Прошлый метод пытался понять и сделать весь день, этот сложился за 15 минут, вот так да

Temirlan ZhuamgulovEnterprise Java Developer в Яндекс

2 марта 2022, 13:01

Как можно оптимизировать данный код или сделать его более читабельнее?

package com.myCompany.sortingAlgorithms;

import java.util.Arrays;
import java.util.Scanner;

public class MergeSort{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int[] arr = new int[N];
        for(int i = 0; i < N; i++){
            arr[i] = in.nextInt();
        }
        int[] results = mergeSort(arr);
        for(int elem: results){
            System.out.print(elem + " ");
        }
    }
    public static int[] mergeSort(int[] arr) {
        if (arr.length < 2) {
            return arr;
        } else {
            int[] a = mergeSort(Arrays.copyOfRange(arr, 0, arr.length / 2));
            int[] b = mergeSort(Arrays.copyOfRange(arr, arr.length / 2, arr.length));
            int[] c = new int[a.length + b.length];
            int index1 = 0, index2 = 0, indexResult = 0;
            while (index1 < a.length && index2 < b.length){
                if(a[index1] < b[index2]){
                    c[indexResult] = a[index1];
                    index1++;
                }
                else{
                    c[indexResult] = b[index2];
                    index2++;
                }
                indexResult++;
            }
            if (index1 < a.length){
                System.arraycopy(a,index1,c,indexResult,(a.length - index1));
            }
            if (index2 < b.length){
                System.arraycopy(b,index2,c,indexResult,(b.length - index2));
            }
            return c;
        }
    }
}

Astrum8

Уровень 3

Expert

6 октября 2022, 04:39

Я проявлю недостаток воспитания и поправлю вас: "более читабельным", т.к. в слове более уже есть сравнение; что касается кода, предлагаю заменить названия переменных "a, b, c" на более понятные в стиле snake или camel case. Не благодарите :3

Plumbum

Уровень 2

7 августа 2021, 22:09

#include <cs50.h>
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>


//Пузырьковая сортировка

int main (int argc, string agrv[])
{
    int m = argc -1;
    int box[m];
    int counter;

    for (int i=0; i<m; i++)
    {
        box[i] = atoi(agrv[i+1]);
    }
    do
    {
        counter = 0;
        int mem = 0;

        for (int i=0; i<m-1; i++)
        {
            if (box[i] > box[i+1])
            {
                mem = box[i];
                box[i]=box[i+1];
                box[i+1]=mem;
                counter++;
            }
        }
    }
    while (counter>0);
    for (int i=0; i<m; i++)
        {
            printf("%i ",box[i]);
        }
        printf("\n");
}

Anonymous #2532889

Уровень 35

25 февраля 2021, 14:01

Почему в конце цикла counter будет равен нулю?

MCit

Уровень 3

17 июля 2021, 23:17

counter будет равен нулю в случае, если не было никаких изменений. Это необходимо для того, чтобы выйти из цикла. По той же причине в начале каждой итерации мы его обнуляем.

Эдик Марруго

Уровень 0

16 ноября 2020, 11:54

#include <stdio.h> #include <stdlib.h> #define SIZE 20 void fillMas(int* mas, int size); void sortMas(int* mas, int size); void printMas(int* mas, int size); int checkIfSorted(int* mas, int size); int main(void) { int mas[SIZE]; fillMas(mas, SIZE); printMas(mas, SIZE); sortMas(mas, SIZE); printMas(mas, SIZE); checkIfSorted(mas, SIZE); } void fillMas(int* mas, int size) { for (int i = 0; i < size; i++) { mas[i] = (rand() % 100); } } void sortMas(int* mas, int size) { int counter; do { int temp = 0; int n = 0; counter = 0; for (int i = 1; i < size; i++) { if (mas[n] > mas[n + 1]) { temp = mas[n]; mas[n] = mas[n + 1]; mas[n + 1] = temp; counter = 1; } n++; } } while (counter > 0); } void printMas(int* mas, int size) { for (int i = 0; i < size; i++) { printf("%i\n", mas[i]); } printf("\n"); } int checkIfSorted(int* mas, int size) { for (int i = 0; i < size; i++) { if (mas[i] > mas[i+1]) { printf("array not sorted"); return 0; } else { printf("array sorted"); return 1; } } }

Ихтияр Кадыров

Уровень 1

1 ноября 2020, 22:55

/**
 * Производит сортировку в массиве
 * haystack согласно алгоритму
 * пузырьковой сортировки.
 *
 * @param haystack [Сортируемый массив]
 * @param size     [Длина массива]
 */
void bubble_sort (int haystack[], const size_t size)
{

	bool permuntation;
	size_t high = size - 1;

	do
	{
		permuntation = false;

		for (int i = 0; i < high; i++)
		{
			if (haystack[i] > haystack[i+1])
			{
				int_swap(&haystack[i], &haystack[i+1]);
				permuntation = true;
			}
		}

		high--;
	}
	while (permuntation != false);

}

/**
 * Производит обмен двух
 * целочисленных переменных.
 *
 * @param left  [левое значение]
 * @param right [правое значение]
 */
void int_swap (int *left, int *right)
{
	if (*left == *right)
	{
		return;
	}

	*left = *left + *right;
	*right = *left - *right;
	*left = *left - *right;
}

Серега Android Developer

29 августа 2020, 11:40

https://www.youtube.com/playlist?list=PLyApprAtr5yjywFgRkxhfGfesgYoIhU8U

Михаил

Уровень 1

30 июля 2020, 14:27

/*Прогрмамма для сортировки пузырьком*/
#include <stdio.h>
#include <cs50.h>    //get_string
#include <string.h>  //strlen
int main(void)
{
    int i, n, j, temp;
    string s = get_string("Введите ряд позитивных чисел:\n");
    do
    {
        j = 0;     //наш счетчик для цикла
        for(i = 0, n = strlen(s); i < n-1; i++)
        {
            if(s[i] > s[i + 1])     //если i-ый символ больше следующего, то ...
            {
                temp = s[i];        //...поменять их местами...
                s[i] = s[i + 1];
                s[i + 1] = temp;
                j++;                //...и увеличить счетчик на 1 для выполнения цикла while
            }
        }
    }
    while (j > 0);   //так как цикл do while, первая итерация происходит в любом случае, как только массив закончится j будеn = 0 и мы выйдем из цикла
    printf("%s",s);
    printf("\n");
    return 0;
}