Sorting in data structure with types and algorithms in detail

Lets us see the Sorting technique in the data structure, with there type and algorithm.

Table of Contents

Introduction to Sorting

Sorting is a process arranging the elements of a list either in ascending or in descending order. The operation of sorting is most often performed in business data processing applications.

However, sorting is important to process in every application. In the process of sorting almost all the elements move from one place to another place and arranged either in ascending or in descending order.

Lets us see the different type of sorting techniques in the data structure;

Bubble Sorting in data structure

In this method of sorting each element is compared with the succeeding element and if the preceding element is found greater then the succeeding element than interchanging of this two-element is done.

In this way, the largest element is a sink at the end of the array, and the smallest element bubble up at the start of the array so this process is called bubble sort.

For example:

Suppose we have a list of numbers A[0],A[1],A[2], . . . . . , 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]<A[1]. Then compare A[1] and A[2] and arrange them so that A[1]<A[2]. Then compare A[2]and A[3] and arrange them so that A[2]<A[3]. Continue this procedure until you compare A[N-2] and A[N-1] and arrange them so that A[N-2]<A[N-1]. After Pass-1 the largest element occupies its place in at location [N-1].

Step2: Repeat Step 1 with one less comparison i.e, now we stop after compare and possibly arrange A[N-2]<A[N-1]. After step- 2 second largest element takes its place at location [N-2].

Step 3: Repeat step 1 with two fewer comparisons i.e, we stop after we compare and possibly rearrange A[N-3]<A[N-2]. After step- 3 third largest element takes its place at location [N-3].

……………………………………………

Step N-1: Compare A[0] and A[1] and arrange them so that A[0]<A[1]. After step N-1 shortest element takes its place at location [0].

After step N-1 the list will be sorted in ascending order. The process of sequentially traversing through all or part of a list is frequently called a PASS, so each of the above steps is called a pass. Accordingly, the bubble sort algorithm requires N-1 passes, where N is the no of input items.

ALGORITHM OF BUBBLE SORT

BUBBLE_SORT [ I, j, n, a, Temp]

For the below algorithm a is a linear array with n elements. Temp is a temporary variable that is being used for swapping of two adjacent elements.

Initialize i=0 [ i will keep the track of passes].
Repeat steps 3,4,7 while i < n – 1. otherwise move to step 8.
Initialize j=0 [ j will keep the track of no. of comparison].
Repeat steps 5,6 while j<(n-1)-i otherwise move to step 7.
IF a[j]>a[j+1] THEN
1. Temp=a[j] [Assign a[j] to Temp]
2. a[j]=a[j+1] [Assign a[j+1] to A[j]]
3. a[j+1]=temp [Assign Temp to a[j+1]]
j=j+1 [ Increment j by one so that next comparison could be done]
i=i+1 [ Increment i by one for moving to the next pass]
STOP

Insertion sorting in data structure

Suppose an array A with n elements A[0], A[1], A[2], . . . . . , A[n-1] is in memory. The insertion sort algorithm scans A from A[1] to A[n-1], Inserting each element into its proper position.

For the implementation of insertion sort, we assume that the first element of an array is already sorted. And follow the following steps:

Pass 1 A[1] is inserted either before or after A[0] so that A[1], A[0] is sorted. In this pass we get two elements sorted ie A[0], A[1].

Pass 2 A[2] is inserted into its proper place in the sorted list ie A[0], A[1]. In this pass we get the first three elements sorted ie A[0], A[1], A[2].

Pass 3 A[3] is inserted into its proper place

………………………………………………………………..

…………………………………………………………………

………………………………………………………………..

And at the end

Pass N-1 A[n-1]is inserted into its proper place in the sorted list ie A[0], A[1], A[2]……A[n-2] So that A[0],A[1],A[2]…….to A[n-1] all the element will be sorted.

ALGORITHM OF INSERTION SORT

INSERTION_SORT [ i, j, n, a, Temp]

In the below algorithm a is an array with n elements. i keeps the track of passes, j keeps the track of those locations of elements with whom temp is to be compared. Temp holds the element that is to be inserted in its proper place.

Initialize i=1.
Repeat steps 3 ,4 ,5,8,9 while i<=n-1 otherwise move to step 10
Set: j=i-1.
temp=a[i]. [Assign value of a[i] to temp]
Repeat steps 6,7 while j>=0 and temp < a[j].
a[j+1]=a[j] [Assign a[j] to a[j+1] ]
j=j-1 [decrement j by one]
i=i+1 [increment i by one ]
a[j+1]=temp [Assign temp to a[j+1] (This is insertion of selected element to its proper place) ]
STOP

Selection sorting in data structure

In selection At first shortest element is selected and then inserted to the selected location 0. Then the next shortest element is selected and inserted to selected location 1. And so on…….

The following steps will be taken for this purpose.

Pass 1 Select location 0, Scan array from A[0] to A[N-1], find out the shortest element and insert it to selected location 0. At the end of pass 1, you will get the shortest element at location 0

Pass 2 Select location 1, Scan array from A[1] to A[N-1], find out the next shortest element and insert it to selected location 1. At the end of pass 2, you will get the second shortest element at location 1.

Pass 3 Select location 2, Scan array from A[2] to A[N-1], find out the next shortest element and insert it to selected location 2.

……………………………..

And at the end

Pass N-1 Select location N-2, Scan array from A[N-2] to A[N-1], find out the next shortest element and insert it to selected location N-1

ALGORITHM OF SELECTION SORT

SELECTION_SORT [ i, j, n, a, Temp]

In the below algorithm i will keep the track of a number of passes or it indicates a selected location where the selected shortest element will be inserted. j is a variable that will keep the track of a number of comparisons in each pass. n is the number of elements in an array and a is an array of n elements. Temp is a temporary variable that will be used for swapping.

Initialize i=0.
Repeat steps 3,4,7 while i<n-1 otherwise move to step 8
j=i+1
Repeat steps 5,6 while (j<=n-1 ) otherwise move to step 7.
IF a[i]>a[j] then [swap the elements of a[i] and a[j] by following three steps.]
1. Temp=a[i]
2. a[i]=a[j]
3. a[j]=temp
j=j+1
i=i+1
STOP

Comment you like or not our article on Sorting in the data structure, or for visit our other article click here.