Sorting refers to rearrangement of a given array or list of elements according to a

comparison operator on the elements. The comparison operator is used to decide the
new order of elements in the respective data structure.
When we have a large amount of data, it can be difficult to deal with it, especially when
it is arranged randomly. When this happens, sorting that data becomes crucial. It is
necessary to sort data in order to make searching

Types of Sorting Techniques

There are various sorting algorithms are used in data structures. The following two
types of sorting algorithms can be broadly classified:
1. Comparison-based: We compare the elements in a comparison-based sorting
algorithm)
2. Non-comparison-based: We do not compare the elements in a non-
comparison-based sorting algorithm)
 Sorting algorithm

Why Sorting Algorithms are Important

The sorting algorithm is important in Computer Science because it reduces the
complexity of a problem. There is a wide range of applications for these algorithms,
including searching algorithms, database algorithms, divide and conquer methods, and
data structure algorithms.
In the following sections, we list some important scientific applications where sorting
algorithms are used
 When you have hundreds of datasets you want to print, you might want to
arrange them in some way.
 Sorting algorithm is used to arrange the elements of a list in a certain order
(either ascending or descending).
  Searching any element in a huge data set becomes easy. We can use Binary
search method for search if we have sorted data. So, Sorting become
important here.
 They can be used in software and in conceptual problems to solve more
advanced problems.
Some of the most common sorting algorithms are:
Below are some of the most common sorting algorithms:

1. Selection sort
Selection sort is another sorting technique in which we find the minimum element in
every iteration and place it in the array beginning from the first index. Thus, a selection
sort also gets divided into a sorted and unsorted subarray.

Working of Selection Sort algorithm:

Lets consider the following array as an example: arr[] = {64, 25, 12, 22, 11}
First pass:
For the first position in the sorted array, the whole array is traversed from index 0 to 4
sequentially. The first position where 64 is stored presently, after traversing whole
array it is clear that 11 is the lowest value.

64 25 12 22 11

Thus, replace 64 with 11. After one iteration 11, which happens to be the least value in
the array, tends to appear in the first position of the sorted list.

11 25 12 22 64

Second Pass:
For the second position, where 25 is present, again traverse the rest of the array in a
sequential manner.

11 25 12 22 64

After traversing, we found that 12 is the second lowest value in the array and it should
appear at the second place in the array, thus swap these values.

11 12 22 64
25

Third Pass:
Now, for third place, where 25 is present again traverse the rest of the array and find
the third least value present in the array.

11 12 25 22 64

While traversing, 22 came out to be the third least value and it should appear at the
third place in the array, thus swap 22 with element present at third position.

11 12 22 25 64

Fourth pass:
Similarly, for fourth position traverse the rest of the array and find the fourth least
element in the array
As 25 is the 4th lowest value hence, it will place at the fourth position.

11 12 22 25 64

Fifth Pass:
At last the largest value present in the array automatically get placed at the last
position in the array
The resulted array is the sorted array.

11 12 22 25 64

Bubble Sort Algorithm

Bubble sort works on the repeatedly swapping of adjacent elements until they are not in
the intended order. It is called bubble sort because the movement of array elements is
just like the movement of air bubbles in the water. Bubbles in water rise up to the
surface; similarly, the array elements in bubble sort move to the end in each iteration.

Although it is simple to use, it is primarily used as an educational tool because the

performance of bubble sort is poor in the real world. It is not suitable for large data sets.
The average and worst-case complexity of Bubble sort is O(n2), where n is a number of
items.

Bubble short is majorly used where -

o complexity does not matter

o simple and shortcode is preferred
 o

Algorithm
In the algorithm given below, suppose arr is an array of n elements. The
assumed swap function in the algorithm will swap the values of given array elements.

1. begin BubbleSort(arr)
2. for all array elements
3. if arr[i] > arr[i+1]
4. swap(arr[i], arr[i+1])
5. end if
6. end for
7. return arr
8. end BubbleSort

Working of Bubble sort Algorithm

Now, let's see the working of Bubble sort Algorithm.

To understand the working of bubble sort algorithm, let's take an unsorted array. We
are taking a short and accurate array, as we know the complexity of bubble sort is O(n2).

Let the elements of array are -

First Pass
Sorting will start from the initial two elements. Let compare them to check which is
greater.
Here, 32 is greater than 13 (32 > 13), so it is already sorted. Now, compare 32 with 26.

Here, 26 is smaller than 36. So, swapping is required. After swapping new array will look
like -

Now, compare 32 and 35.

Here, 35 is greater than 32. So, there is no swapping required as they are already sorted.

Now, the comparison will be in between 35 and 10.

Here, 10 is smaller than 35 that are not sorted. So, swapping is required. Now, we reach
at the end of the array. After first pass, the array will be -

Now, move to the second iteration.

Second Pass
The same process will be followed for second iteration.
Here, 10 is smaller than 32. So, swapping is required. After swapping, the array will be -

Now, move to the third iteration.

Third Pass
The same process will be followed for third iteration.

Here, 10 is smaller than 26. So, swapping is required. After swapping, the array will be -

Now, move to the fourth iteration.

Fourth pass
Similarly, after the fourth iteration, the array will be -

Hence, there is no swapping required, so the array is completely sorted.

Bubble sort complexity

Now, let's see the time complexity of bubble sort in the best case, average case, and
worst case. We will also see the space complexity of bubble sort.

1. Time Complexity

Case Time Complexity

Best Case O(n)

Average Case O(n2)

Worst Case O(n2)

o Best Case Complexity - It occurs when there is no sorting required, i.e. the array
is already sorted. The best-case time complexity of bubble sort is O(n).
o Average Case Complexity - It occurs when the array elements are in jumbled
order that is not properly ascending and not properly descending. The average
case time complexity of bubble sort is O(n2).
o Worst Case Complexity - It occurs when the array elements are required to be
sorted in reverse order. That means suppose you have to sort the array elements
in ascending order, but its elements are in descending order. The worst-case time
complexity of bubble sort is O(n2).

2. Space Complexity

Space Complexity O(1)

 Stable YES

o The space complexity of bubble sort is O(1). It is because, in bubble sort, an extra
variable is required for swapping.
o The space complexity of optimized bubble sort is O(2). It is because two extra
variables are required in optimized bubble sort.

To sort an array of size N in ascending order iterate over the array and compare the
current element (key) to its predecessor, if the key element is smaller than its
predecessor, compare it to the elements before. Move the greater elements one position
up to make space for the swapped element.

Working of Insertion Sort algorithm

Consider an example: arr[]: {12, 11, 13, 5, 6}
12 11 13 5 6

First Pass:
 Initially, the first two elements of the array are compared in insertion sort.

12 11 13 5 6

 Here, 12 is greater than 11 hence they are not in the ascending order and 12
is not at its correct position. Thus, swap 11 and 12.
 So, for now 11 is stored in a sorted sub-array.
11 12 13 5 6

Second Pass:
 Now, move to the next two elements and compare them
11 12 13 5 6

Here, 13 is greater than 12, thus both elements seems to be in ascending

order, hence, no swapping will occur. 12 also stored in a sorted sub-array
along with 11
Third Pass:
 Now, two elements are present in the sorted sub-array which are 11 and 12
 Moving forward to the next two elements which are 13 and 5

11 12 13 5 6
  Both 5 and 13 are not present at their correct place so swap them
11 12 5 13 6

 After swapping, elements 12 and 5 are not sorted, thus swap again
11 5 12 13 6

 Here, again 11 and 5 are not sorted, hence swap again

5 11 12 13 6

Here, 5 is at its correct position


Fourth Pass:
 Now, the elements which are present in the sorted sub-array are 5, 11 and 12
 Moving to the next two elements 13 and 6

5 11 12 13 6

 Clearly, they are not sorted, thus perform swap between both
5 11 12 6 13

 Now, 6 is smaller than 12, hence, swap again

5 11 6 12
13

 Here, also swapping makes 11 and 6 unsorted hence, swap again

5 11
6 12 13

 Finally, the array is completely sorted.

Illustrations:
Implementation of Insertion Sort Algorithm
Insertion Sort


// C++ program for insertion sort

#include <bits/stdc++.h>

using namespace std;

// Function to sort an array using

// insertion sort

void insertionSort(int arr[], int n)

int i, key, j;

for (i = 1; i < n; i++) {

key = arr[i];

j = i - 1;

// Move elements of arr[0..i-1],

// that are greater than key,

// to one position ahead of their

// current position

while (j >= 0 && arr[j] > key) {

arr[j + 1] = arr[j];

j = j - 1;

arr[j + 1] = key;

// A utility function to print an array

// of size n

void printArray(int arr[], int n)

int i;

for (i = 0; i < n; i++)

 cout << arr[i] << " ";

cout << endl;

// Driver code

int main()

int arr[] = { 12, 11, 13, 5, 6 };

int N = sizeof(arr) / sizeof(arr[0]);

insertionSort(arr, N);

printArray(arr, N);

return 0;

// This is code is contributed by rathbhupendra

Output
5 6 11 12 13
Time Complexity: O(N^2)
Auxiliary Space: O(1)
Complexity Analysis of Insertion Sort:
Time Complexity of Insertion Sort
 The worst-case time complexity of the Insertion sort is O(N^2)
 The average case time complexity of the Insertion sort is O(N^2)
 The time complexity of the best case is O(N).
Space Complexity of Insertion Sort
The auxiliary space complexity of Insertion Sort is O(1)
Characteristics of Insertion Sort
 This algorithm is one of the simplest algorithms with a simple
implementation
  Basically, Insertion sort is efficient for small data values
 Insertion sort is adaptive in nature, i.e. it is appropriate for data sets that are
already partially sorted.
Linear

 Linear search is also called as sequential search algorithm. It is the simplest

searching algorithm. In Linear search, we simply traverse the list completely and
match each element of the list with the item whose location is to be found. If the
match is found, then the location of the item is returned; otherwise, the algorithm
returns NULL.

 It is widely used to search an element from the unordered list, i.e., the list in
which items are not sorted. The worst-case time complexity of linear search
is O(n).