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

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

Harvard CS50

3 уровень , 9 лекция

Открыта

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

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

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

Идем вдоль всего массива и сравниваем 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 элементов).

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

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

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

ЧТОБЫ ПОСМОТРЕТЬ ВСЕ КОММЕНТАРИИ ИЛИ ОСТАВИТЬ КОММЕНТАРИЙ,
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ

FeatHonnar Уровень 16

22 сентября 2022


#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 Zhuamgulov Уровень 8

2 марта 2022

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


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

Plumbum Уровень 2

7 августа 2021


#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

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

Эдик Марруго Уровень 0

16 ноября 2020

#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


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

Серега Уровень 20

29 августа 2020

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

Михаил Уровень 1

30 июля 2020


/*Прогрмамма для сортировки пузырьком*/
#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;
}

Daniel Ches Уровень 0

13 июля 2020


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

int main()
{
    string n = get_string("");
    int i;
    do
    {
        i = 0;
        for (int j=0, c; j<strlen(n)-1; j++)
        {
            if( n[j]> n[j+1])
            {
                c = n[j];
                n[j] = n[j+1];
                n[j+1] = c;
                i++;
            }

        }
    }
    while (i > 0);
    printf("%s", n);
}

xacker Уровень 5

15 июня 2020

Стандартные библиотеки, обмен значений - XOR.


//Sort Bubble
#include <stdio.h>
#include <stdlib.h>

#define MAX_AMOUNT 50

int main(int argc, char* argv[])
{
	if(argc < 2)
	{
		fprintf(stderr, "Not enough arguments\n");
		return 1;
	}
	if(argc > 2)
	{
		fprintf(stderr, "Too many arguments\n");
		return 1;
	}

	int amount = atoi(argv[1]);
	int array[MAX_AMOUNT] = {0};

	for (int i = 0; i < amount; ++i)
	{
		scanf("%d", &array[i]);
	}

	int flag = 1;

	do
	{
		flag = 0;
		for (int i = 0; i < amount - 1; ++i)
		{
			if (array[i] > array[i + 1])
			{
				array[i] = array[i] ^ array [i + 1];
				array[i + 1] = array[i] ^ array [i + 1];
				array[i] = array[i] ^ array [i + 1];
				flag = 1;
			}
		}
	}
	while (flag != 0);

	printf("Sorted array: ");
	
	for (int i = 0; i < amount; ++i)
	{
		printf("%d ", array[i]);
	}
	printf("\n");
	return 0;
}