Selection Sort

netaji gandi Saturday, April 30, 2022

Edit

Selection Sort

The Selection sort algorithm is based on the idea of finding the minimum or maximum element in an unsorted array and then putting it in its correct position in a sorted array.

In every iteration of selection sort, the minimum element (considering ascending order) from the unsorted subarray is picked and moved to the sorted subarray.

It is repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at the beginning.
The algorithm maintains two subarrays in a given array.

1) The subarray which is already sorted.
2) Remaining subarray which is unsorted.

Example:

0 1 2 3 //Index

7 4 5 2 // Values

Step 1: set i, min=0 location and j=1st location

min / i= 0 j= 1 2 3

7 4 5 2

Step 2: for i in N: set min=i ie min=0

Step 3: for j in N:

compare arr[ j ]< arr[ min ] ie arr[ 1 ]< arr[0] 4<7

If yes, min=j min=1

Step 4: repeat to step 3

compare arr[ j ]< arr[ min ] ie arr[ 2 ]< arr[1] 5<4

If yes, min=j

compare arr[ j ]<arr[min] arr[3] < arr[1] 2<4

If yes, min =j min=3

Step 5: Swap the elements arr[i], arr[min] = arr[min], arr[i] i= 0 j=1 2 min= 3

2 4 5 7

Step 6: Repeat step 2 and 3 from min=i

sorted i/ min = 1 j=2 3

2 4 5 7

compare arr[ j ]< arr[ min ] ie arr[2]< arr[1] 5<4

If yes, k=min k=1

compare arr[ j ]<arr[min] arr[3] < arr[1] 7<4

If yes, k =min

sorted i/ min = 1 2 j= 3

2 4 5 7

Worst Case Complexity: O(n2)
If we want to sort in ascending order and the array is in descending order

then, the worst case occurs.

Best Case Complexity: O(n2)
It occurs when the array is already sorted

Average Case Complexity: O(n2)
It occurs when the elements of the array are in jumbled order (neither

ascending nor descending)

Selection Sort

netaji gandi Saturday, April 30, 2022

Insertion Sort

netaji gandi

Edit

Insertion Sort

Insertion sort is based on the idea that one element from the input elements is consumed in each iteration to find its correct position i.e, the position to which it belongs in a sorted array.

The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in the sorted part.

This is done by shifting all the elements, which are larger than the current element, in the sorted array to one position ahead

Algorithm:

To sort an array of size n in ascending order:

1: Iterate from arr[1] to arr[n] over the array.

2: Compare the current element (key) to its predecessor.

3: 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.

Example:

Time Complexities:

Worst Case Complexity: O(n2)
If we want to sort in ascending order and the array is in descending order then, the worst case occurs.
Best Case Complexity: O(n)
It occurs when the array is already sorted
Average Case Complexity: O(n2)
It occurs when the elements of the array are in jumbled order (neither ascending nor descending)

Insertion Sort

netaji gandi

Bubble Sort

netaji gandi Thursday, April 28, 2022

Edit

Bubble Sort

Bubble sort is an algorithm that compares the adjacent elements and swaps their positions if they are not in the intended order.
A list with n elements requires n-1 passes for sorting
The order can be ascending or descending.
It is known as bubble sort, because with every complete iteration the largest element in the given array, bubbles up towards the last place or the highest index, just like a water bubble rises up to the water surface.

Algorithm: Following are the steps involved in bubble sort(for sorting a given array in ascending order):

Starting with the first element(index = 0), compare the current element with the next element of the array.
If the current element is greater than the next element of the array, swap them.
If the current element is less than the next element, move to the next element. Repeat Step 1.

How it works:
Bubble sort starts with very first two elements, comparing them to check which one is greater.

In this case, value 33 is greater than 14, so it is already in sorted locations. Next, we compare 33 with 27.

We find that 27 is smaller than 33 and these two values must be swapped.

The new array should look like this −

Next we compare 33 and 35. We find that both are in already sorted positions.

Then we move to the next two values, 35 and 10.

We know then that 10 is smaller 35. Hence they are not sorted.

We swap these values. We find that we have reached the end of the array. After one iteration (pass), the array should look like this − (This is what the list looks like after the first pass.)

To be precise, we are now showing how an array should look like after each iteration. After the second iteration, it should look like this −

Notice that after each iteration, at least one value moves at the end.

And when there's no swap required, bubble sorts learns that an array is completely sorted.

Advantages:

Easy to understand.
Easy to implement.
In-place, no external memory is needed.
Performs greatly when the array is almost sorted.

Disadvantages

Very expensive, O(n2)in worst case and average case.
The main disadvantage of the bubble sort is the fact that it does not deal well with a list containing a huge number of items.

Bubble Sort

netaji gandi Thursday, April 28, 2022

What is sorting? Types of Sortings

netaji gandi

Edit

What is sorting? Types of Sorting's

Sorting Algorithms are methods of reorganizing a large number of items into some specific order such as highest to lowest, or vice-versa, or even in some alphabetical order.

These algorithms take an input list/array, processes it (i.e, performs some operations on it) and produce the sorted list.

Sorting arranges data in a sequence which makes searching easier.
The most common example we experience every day is

Telephone Directory
Dictionary
sorting clothes or
other items on an e-commerce website either by lowest-price to highest, or list by popularity,
or some other order.

There are two different categories in sorting:

Internal sorting: If the input data is such that it can be adjusted in the main memory at once, it is called internal sorting.
External sorting: If the input data is such that it cannot be adjusted in the memory entirely at once, it needs to be stored in a hard disk, floppy disk, or any other storage device. This is called external sorting.

The two main criteria to judge which algorithm is better than the other have been:

Time taken to sort the given data.
Memory Space required to do so

Stability of Sorting Algorithms

Stability is mainly important when we have key value pairs with duplicate keys possible (like people names as keys and their details as values). And we wish to sort these objects by keys

Def.:

A sorting algorithm is said to be stable if two objects with equal keys appear in the same order in sorted output as they appear in the input array to be sorted.