Bubble sort

c go java js lua py vbs rkt scm pro

The sort something is to arrange that something into some order.

sort laundry
sort out things
sort a list
sort an array representing a list

Why is sorting important?

Many algorithms are not practical in the sense that they must look at every possible permutation in order to determine an (optimum) result.

The number of permutations of 60 elements is about the number of seconds in 15 billion years.

Slow sort is to create and inspect every permutation of the items

In the case of sorting, however, implicit information can be retained during the sorting process to simplify work as the algorithm progresses. A general pseudo code algorithm that can be used to sort a list is as follows.

For completeness, we will briefly discuss bubble sort. The idea of bubble sort is that during each pass through the list, elements make their way, as bubbles do, to their proper place in the final sorted list.

Bubble sort is the worst possible (practical) sort one could do and is never used in practice (except at the hardware level where parallelism can improve the performance).

The pseudo code algorithm for bubble sort is as follows.

FOR EACH of n passes DO

FOR

EACH

DO

IF

THEN

ENDIF

ENDDO

Here is the C code.

#include <stdio.h>

int main() {
	const int DATAMAX1 = 16;
	int dataList1[DATAMAX1+1];
	int dataLen1;
	int dataPos1;
	// input
	scanf("%d",&dataList1[0]);
	printf("Input list: (unsorted)\n");
	printf("\n");
	dataLen1 = 0;
	while (dataList1[0] >= 0) {
		dataLen1 += 1;
		dataList1[dataLen1] = dataList1[0];
		printf("%d. %d\n",dataLen1,dataList1[dataLen1]);
		scanf("%d",&dataList1[0]);
		}
	// process - bubble sort
	printf("\n");
	printf("Process: (bubble sort)\n");
	for (int dataPos1=1; dataPos1 <= dataLen1; dataPos1++) {
		printf("\n");
		printf("\tPass %d:\n",dataPos1);
		printf("\n");
		for (int dataPos2=2; dataPos2 <= dataLen1; dataPos2++) {
			printf("\t\t#%d=%d and #%d=%d",dataPos2-1,dataList1[dataPos2-1],dataPos2,dataList1[dataPos2]);
			if (dataList1[dataPos2-1] > dataList1[dataPos2]) {
				dataList1[0] = dataList1[dataPos2-1];
				dataList1[dataPos2-1] = dataList1[dataPos2];
				dataList1[dataPos2] = dataList1[0];
				printf(" (swap)");
				}
			printf("\n");
			}
		}
	// output
	printf("\n");
	printf("Output list: (sorted)\n");
	printf("\n");
	for (int dataPos1=1; dataPos1 <= dataLen1; dataPos1++) {
		printf("%d. %d\n",dataPos1,dataList1[dataPos1]);
		}
	return 0;
	}

Here are some examples of input and output for the above program code.

Here is an example input.

For the above example input, here is the expected output.

Input list: (unsorted)

1. 56
2. 78
3. 34
4. 12

Process: (bubble sort)

	Pass 1:

		#1=56 and #2=78
		#2=78 and #3=34 (swap)
		#3=78 and #4=12 (swap)

	Pass 2:

		#1=56 and #2=34 (swap)
		#2=56 and #3=12 (swap)
		#3=56 and #4=78

	Pass 3:

		#1=34 and #2=12 (swap)
		#2=34 and #3=56
		#3=56 and #4=78

	Pass 4:

		#1=12 and #2=34
		#2=34 and #3=56
		#3=56 and #4=78

Output list: (sorted)

1. 12
2. 34
3. 56
4. 78

4