undefined

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

Harvard CS50
3 уровень , 9 лекция
Доступна

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

class=»embed-responsive-item»



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

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

Идем вдоль всего массива и сравниваем 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(n2) в худшем случае (все числа стоят неправильно), поскольку нам нужно сделать n шагов на каждой итерации, которых тоже n. На самом деле, как и в случае с алгоритма сортировки выбором, время будет несколько меньше (n2/2 – n/2), но этим можно пренебречь. 

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

Комментарии (19)
TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION
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;
}
Серега Уровень 19 Кривой Рог Украина
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;
}
Danil Lomakin Уровень 2
24 октября 2019

#include <stdio.h>

void printArr(int array[], int n);
void sortArr(int array[], int n);

int main(void) {
    const int n = 10;
    int array[10] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};

    printArr(array, n);
    sortArr(array, n);
    printArr(array, n);
}

void printArr(int array[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%i ", array[i]);
    }
    printf("\n");
}

void sortArr(int array[], int n) {
    int temp, count = 0;

    for (int swaps = 1, i = 0; swaps > 0; i++) {
        swaps = 0;
        for (int j = 0; j < n - 1 - i; j++) {
            if (array[j] > array[j + 1]) {
                // swaps the values.
                temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
                // increases the count.
                swaps++;
            }
            // increases iterations.
            count++;
        }
    }
    printf("Iterations: %i\n", count);
}
АМ Уровень 2 Kubinka
22 октября 2019
#include <stdio.h> #include <cs50.h> #include <string.h> #include <stdlib.h> #include <ctype.h> int main(int argc, string argv[]){ if(argc < 2){ printf("Введите более двух аргументов!\n"); return 1; } int len = argc -1; int box[len]; for(int i = 1, n = argc; i < n; i++){ for(int j = 0, m = strlen(argv[i]); j < m; j++){ if(isdigit(argv[i][j]) == false){ printf("Массив должен состоять только из цифр!\n"); return 1; } } box[i] = atoi(argv[i]); } int swap; for(int i = 0; i < len; i++){ for(int j = i + 1; j<= len; j++){ if(box[i] > box[j]){ swap = box[j]; box[j] = box[i]; box[i] = swap; //printf("%i %i ", box[i], box[i + 1]); } } } for(int i = 1; i <= len; i++) printf("%i ", box[i]); printf("\n"); }
vinsler Уровень 35 Санкт-Петербург Россия Expert
25 апреля 2019
может кому будет интересно. Сортировка слиянием