Page 56 - DCAP407_DATA_STRUCTURE

Unit 3: Arrays

Write an algorithm to delete an element at a specific position from an array.

3.3.2 Sorting Operation
Sorting operation arranges the elements of a list in a certain order. Efficient sorting is important for
optimizing the use of other algorithms that require sorted lists to work correctly.
Sorting an array efficiently is quite complicated. There are different sorting algorithms to perform the
task of sorting, but here we will discuss only Bubble Sort.
Bubble Sort

Bubble sort is a simple sorting technique when compared to other sorting techniques. The bubble sort
algorithm starts from the very first element of the data set. In order to sort elements in the ascending
order, the algorithm compares the first two elements of the data set. If the first element is greater than
the second, then the numbers are swapped.
This process is carried out for each pair of adjacent elements to the end of the data set until no swaps
occur on the last pass. This algorithm's average and worst case performance is O (2n) as it is rarely used
to sort large, unordered data sets.
Bubble sort can always be used to sort a small number of items where efficiency is not a high priority.
Bubble sort may also be effectively used to sort a partially sorted list.

Even when one element is not in order, bubble sort takes 2n of time. If two
elements are not in order, bubble sort takes at most 3n time.
Algorithm for Sorting an Array

Let A be an array containing data with N elements. This algorithm sorts the elements in A as follows:
1. Start
2. Repeat Steps 3 and 4 for K= 1 to N-1
3. Set PTR :=1 [Initializes pass pointer PTR]
4. Repeat while PTR≤ N – K: [Executes pass]
If A[PTR] > A[PTR+1], then:

Interchange A[PTR] and A[PTR +1]
[End of If structure]
Set PTR := PTR+1
[End of inner loop]
[End of Step 2 outer loop]

5. Exit
In the algorithm, there is an inner loop, which is controlled by the variable PTR, and an index K
controls the outer loop. K is used as a counter and PTR is used as an index.
The below program illustrates the concept of sorting an array using bubble sort.

#include <stdio.h>
#include <conio.h>

int A[8] = {55, 22, 2, 43, 12, 8, 32, 15}; //Declaring the array with 8 elements
int N = 8; //Size of the array

LOVELY PROFESSIONAL UNIVERSITY 49