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

Вот тот, который все любят пузырьковую сортировку. Пузырьковая сортировка - один из самых простых алгоритмов сортировки.

Здесь сортировка означает, как правило, расположение элементов в порядке возрастания, но вы также можете расположить элементы в порядке убывания.

Сортировка пузырьков - это алгоритм INPLACE, то есть не требует дополнительной памяти.

Это также СТАБИЛЬНЫЙ алгоритм, то есть он изменяет порядок необходимых элементов и сохраняет исходный порядок, если они находятся в правильном порядке.

Пузырьковая сортировка работает следующим образом:

Сортировка пузырьков начинается с начального элемента (первого) массива или списка и сравнивается со следующим элементом (вторым). Если элементы расположены в правильном порядке, то есть Первый_элемент ‹Второй_элемент, мы оставим элементы в том же порядке. Если элементы не в правильном порядке, мы меняем местами элементы, чтобы расположить их в правильном порядке. Сортировка пузырьков - это алгоритм INPLACE, то есть он выполняет замену и каждую операцию с одним и тем же входным массивом. Никакой дополнительной памяти он не использует.

Пример:

Пузырьковая сортировка - это просто итеративный алгоритм сортировки, который меняет местами два элемента за раз, когда они находятся в неправильном порядке. В каждом наборе итераций он помещает наивысшее значение массива в его правильную позицию, когда вы выполняете сортировку в порядке возрастания.

Предположим, что если вы даете отсортированный массив в качестве входных данных, то, интуитивно говоря, нет необходимости менять местами элементы, и к концу первого набора из n-1 итераций все элементы массива будут отсортированы. Когда все элементы сортируются в первом наборе из n-1 итераций, тогда зачем нам запускать код для набора из n-1 итераций?

Поэтому, чтобы избежать этого ненужного зацикливания, мы используем переменную FLAG. Первоначально мы установим флаг в ноль, а когда будет своп, мы установим флаг = 1.

Если для определенного набора итераций флаг все еще равен нулю, это означает, что свопов не было.

Если свопов не произошло, это означает, что все значения отсортированы. Если все значения отсортированы, мы можем выйти из цикла.

Код C:

//Bubble Sort
//Time complexity----n^2(linear)
//space complexity---constant memory usage
#include<stdio.h>
#include<conio.h>
int main()
{
	int i,j,k,n,a[n],flag;
	flag=0;
	printf("\n Enter the number of elements in teh array\n");
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		printf("\n Enter the elements in the array\n");
		scanf("%d",&a[i]);
	}
	for(i=0;i<n;i++)
	{
                flag=0;
                for(j=0;j<n-1;j++)
		{
			if(a[j]>a[j+1])
			{
				k=a[j];
				a[j]=a[j+1];
				a[j+1]=k;
				flag=1;
			}
		}
		if(flag==0)
		{
			break;
		}
	}
	for(i=0;i<n;i++)
	{
		printf("\n");
		printf("%d",a[i]);		
	}
}