Sorting

Bubble Sort

Bubble Sort is the simplest of the sorting techniques.

In the bubble sort technique, each of the elements in the list is compared to its adjacent element. Thus if there are n elements in list A, then A[0] is compared to A[1], A[1] is compared to A[2] and so on.

After comparing if the first element is greater than the second, the two elements are swapped then.

Bubble Sort Technique

Using the bubble sort technique, sorting is done in passes or iteration. Thus at the end of each iteration, the heaviest element is placed at its proper place in the list. In other words, the largest element in the list bubbles up.

We have given a general algorithm of bubble sort technique below.

General Algorithm

Step 1: For i = 0 to N-1 repeat Step 2

Step 2: For J = i + 1 to N – I repeat

Step 3: if A[J] > A[i]

Swap A[J] and A[i]

[End of Inner for loop]

[End if Outer for loop]

Step 4: Exit

Here is a pseudo-code for bubble sort algorithm, where we traverse the list using two iterative loops.

In the first loop, we start from the 0th element and in the next loop, we start from an adjacent element. In the inner loop body, we compare each of the adjacent elements and swap them if they are not in order. At the end of each iteration of the outer loop, the heaviest element bubbles up at the end.

Pseudocode

Procedure bubble_sort (array , N)
array – list of items to be sorted
N – size of array
begin
swapped = false
repeat
for I = 1 to N-1
if array[i-1] > array[i] then
swap array[i-1] and array[i]
swapped = true
end if
end for
until not swapped
end procedure

Array entirely sorted.

The above illustration can be summarized in a tabular form as shown below:

As shown in the illustration, with every pass, the largest element bubbles up to the last thereby sorting the list with every pass. As mentioned in the introduction, each element is compared to its adjacent element and swapped with one another if they are not in order.

Thus as shown in the illustration above, at the end of the first pass, if the array is to be sorted in ascending order, the largest element is placed at the end of the list. For the second pass, the second largest element is placed at the second last position in the list and so on.

When we reach N-1 (where N is a total number of elements in the list) passes, we will have the entire list sorted.

SELECTION SORT

The selection sort technique first selects the smallest element in the array and swaps it with the first element in the array.

Next, it swaps the second smallest element in the array with the second element and so on. Thus for every pass, the smallest element in the array is selected and put in its proper position until the entire array is sorted.

Selection sort is quite a straightforward sorting technique as the technique only involves finding the smallest element in every pass and placing it in the correct position.

Selection sort works efficiently when the list to be sorted is of small size but its performance is affected badly as the list to be sorted grows in size.

Hence we can say that selection sort is not advisable for larger lists of data.

General Algorithm

The General Algorithm for selection sort is given below:

Selection Sort (A, N)

Step 1: Repeat Steps 2 and 3 for K = 1 to N-1

Step 2: Call routine smallest(A, K, N,POS)

Step 3: Swap A[K] with A [POS]

[End of loop]

Step 4: EXIT

Routine smallest (A, K, N, POS)

• Step 1: [initialize] set smallestElem = A[K]
• Step 2: [initialize] set POS = K
• Step 3: for J = K+1 to N -1,repeat
if smallestElem > A [J]
set smallestElem = A [J]
set POS = J
[if end]
[End of loop]
• Step 4: return POS

Pseudocode For Selection Sort

Procedure selection_sort(array,N)

array – array of items to be sorted

N – size of array

begin

for I = 1 to N-1

begin

set min  = i

for j = i+1 to N

begin

if array[j] < array[min] then

min = j;

end if

end for

//swap the minimum element with current element

if minIndex != I then

swap array[min[] and array[i]

end if

end for

end procedure

An example to illustrate this selection sort algorithm is shown below.

Illustration

From the illustration, we see that with every pass the next smallest element is put in its correct position in the sorted array. From the above illustration, we see that in order to sort an array of 5 elements, four passes were required. This means in general, to sort an array of N elements, we need N-1 passes in total.

Insertion Sort

Insertion sort is a sorting technique which can be viewed in a way which we play cards at hand. The way we insert any card in a deck or remove it, insertion sorts works in a similar way.

Insertion sort algorithm technique is more efficient than the Bubble sort and Selection sort techniques but is less efficient than the other techniques like Quicksort and Merge sort.

In the insertion sort technique, we start from the second element and compare it with the first element and put it in a proper place. Then we perform this process for the subsequent elements.

We compare each element with all its previous elements and put or insert the element in its proper position. Insertion sort technique is more feasible for arrays with a smaller number of elements. It is also useful for sorting linked lists.

Linked lists have a pointer to the next element (in case of a singly linked list) and a pointer to the previous element as well (in case of a doubly linked list). Hence it becomes easier to implement insertion sort for a linked list.

Let us explore all about Insertion sort in this tutorial.

General Algorithm

Step 1: Repeat Steps 2 to 5 for K = 1 to N-1

Step 2: set temp = A[K]

Step 3: set J = K – 1

Step 4: Repeat while temp <=A[J]

set A[J + 1] = A[J]

set J = J – 1

[end of inner loop]

Step 5: set A[J + 1] = temp

[end of loop]

Step 6: exit

Thus, in the insertion sort technique, we start from the second element as we assume that the first element is always sorted. Then from the second element to the last element, we compare each element to all of its previous elements and the put that element in the proper position.

Pseudocode

The pseudo code for insertion sort is given below.

procedure insertionSort(array,N )

array – array to be sorted

N- number of elements

begin

int freePosition

int insert_val

for i = 1 to N -1 do:

insert_val = array[i]

freePosition = i

//locate free position to insert the element

whilefreePosition> 0 and array[freePosition -1] >insert_val  do:

array [freePosition] = array [freePosition -1]

freePosition = freePosition -1

end while

//insert the number at free position

array [freePosition] = insert_val

end for

end procedure

Given above is the pseudo code for Insertion sort, next, we will illustrate this technique in the following example.

Illustration

The array to be sorted is as follows:

Now for each pass, we compare the current element to all its previous elements. So in the first pass, we start with the second element.

Thus we require N number of passes to completely sort an array containing N number of elements.

The above illustration can be summarized in a tabular form:

As shown in the above illustration, we begin with the 2nd element as we assume that the first element is always sorted. So we begin with comparing the second element with the first one and swap the position if the second element is less than the first.

This comparison and swapping process positions two elements in their proper places. Next, we compare the third element to its previous (first and second) elements and perform the same procedure to place the third element in the proper place.

In this manner, for each pass, we place one element in its place. For the first pass, we place the second element in its place. Thus in general, to place N elements in their proper place, we need N-1 passes.

Shell Sort

Shell sort is often termed as an improvement over insertion sort. In insertion sort, we take increments by 1 to compare elements and put them in their proper position.

In shell sort, the list is sorted by breaking it down into a number of smaller sublists. It’s not necessary that the lists need to be with contiguous elements. Instead, shell sort technique uses increment i, which is also called “gap” and uses it to create a list of elements that are “i” elements apart.

The general algorithm for shell sort is given below.

shell_sort (A, N)

where A – list to be sorted; N – gap_size

set gap_size = N, flag = 1

while gap_size > 1 or flag = 1, repeat

begin

set flag = 0

set gap_size = (gap_size + 1)/2

end

for i = 0 to i< (N-gap_size) repeat

begin

if A[i + gap_size] > A[i]

swap A[i + gap_size], A[i]

set flag = 0

end

end

Thus in the above algorithm, we first set N which is the gap for sorting the array A using shell sort. In the next step, we divide the array into sub-arrays by using the gap. Then in the next step, we sort each of the sub-arrays so that at the end of the loop we will get a sorted array.

Next, let us consider a detailed example to better understand the shell sort using a pictorial representation.

Illustration

Let us illustrate the Shell sort with an Example.

Consider the following array of 10 elements.

If we provide a gap of 3, then we will have the following sub-lists with each element that is 3 elements apart. We then sort these three sublists.

The sorted sub-lists and the resultant list that we obtain after combining the three sorted sublists are shown below.

The above array that we have obtained after merging the sorted subarrays is nearly sorted. Now we can perform insertion sort on this list and sort the entire array. This final step is shown below for your reference.

As seen above, after performing shell sort and merging the sorted sublists, we only required three moves to completely sort the list. Thus we can see that we can significantly reduce the number of steps required to sort the array.

SHELL SORT

Shell sort is often termed as an improvement over insertion sort. In insertion sort, we take increments by 1 to compare elements and put them in their proper position.

In shell sort, the list is sorted by breaking it down into a number of smaller sublists. It’s not necessary that the lists need to be with contiguous elements. Instead, shell sort technique uses increment i, which is also called “gap” and uses it to create a list of elements that are “i” elements apart.

The general algorithm for shell sort is given below.

shell_sort (A, N)

where A – list to be sorted; N – gap_size

set gap_size = N, flag = 1

while gap_size > 1 or flag = 1, repeat

begin

set flag = 0

set gap_size = (gap_size + 1)/2

end

for i = 0 to i< (N-gap_size) repeat

begin

if A[i + gap_size] > A[i]

swap A[i + gap_size], A[i]

set flag = 0

end

End

Thus in the above algorithm, we first set N which is the gap for sorting the array A using shell sort. In the next step, we divide the array into sub-arrays by using the gap. Then in the next step, we sort each of the sub-arrays so that at the end of the loop we will get a sorted array.

Next, let us consider a detailed example to better understand the shell sort using a pictorial representation.

Illustration

Let us illustrate the Shell sort with an Example.

Consider the following array of 10 elements.

If we provide a gap of 3, then we will have the following sub-lists with each element that is 3 elements apart. We then sort these three sublists.

The sorted sub-lists and the resultant list that we obtain after combining the three sorted sublists are shown below.

The above array that we have obtained after merging the sorted subarrays is nearly sorted. Now we can perform insertion sort on this list and sort the entire array. This final step is shown below for your reference.

As seen above, after performing shell sort and merging the sorted sublists, we only required three moves to completely sort the list. Thus we can see that we can significantly reduce the number of steps required to sort the array.

The choice of increment to create sub-lists is a unique feature of shell sort.