Sorting

The process of sorting refers to the operation of rearranging the elements (numerical or alphabetical) of data so they are in increasing or decreasing order, i..e., in case of ascending order.

DATA[1] < DATA[2] < DATA[3] <×××××< DATA[N]

8.1 Bubble Sort:

Suppose the list of numbers A[0], A[1]…A[N-1] is in memory. The bubble sort algorithm works as follows:

Step1. compare A[0] and A[1] and arrange them in the desired order, so that A[0]

During step 1, the largest element is “ bubbled up” to the (n-1)th position or “sinks” to the (n-1)th position. When Step 1 is completed, A[N-1] will contain the largest element.

Step2. Repeat Step 1 with one less comparison; that is, now we stop after we compare and possibly rearrange A[N-3] and A[N-2]. When Step 2 is completed, the second largest element will occupy A[N-2].

Step3. Repeat Step1 with two fewer comparisons; that is, we stop after we compare and possibly rearrange A[N-4] and A[N-3].

Step N-1. Compare A[0] with A[1] and arrange them so that A[0]

After N-1 steps, the list will be sorted in increasing order.