Introduction To Sorting

Sorting is the process of arranging the elements either in ascending order or descending one. In real world problems we need to sort the data in the form of number, string or any form into the proper order. Hence Sorting algorithms are important. 

Basically there are two type of  sorting:

1.Internal sort

Internal sorting algorithms are designed to sort data that can fit entirely into memory.

They work by rearranging the data within the same memory space. example of internal sort algo are insertion sort,selection sort,bubble sort,quick sort,merge sort, heap sort,shell sort e.t.c

2.External sort

It is the technique used to sort data that is too large to fit entirely into memory. it works by dividing the data into smaller pieces that can be soted separtely,and then morging the sorted pieces together. external sorting is used in applications such as database management and external storage devices. The most common external sorting algorithms are External Merge Sort and Distribution Sort.

 

Effiency of sorting algorithms

The efficiency of sorting algo are typically measured in terms of it's time complexity and space complexity.

Time Complexity:

=> Measured amount of time taken to run based on input size.

=> Can have different worst,best,average time complexity

=> Usually expressed in Big O notation

Space Complexity:

=> Measured amount of memory required to run based on input size.

=> Can sort in place or required additional memory

=> Usually expressed in Big O notation

 

Stability:

A sorting algorithms is stable if it maintains the relative order of equal elements in the input data. Stable algorithms are useful in applications where the original order of equal elements is important such as sorting by multiple criteria.

 

There are many sorting algorithms choice depends on data size,desired time/space complexity such as

1.Insertion sort           O(n^2) O(1)

Application : small data sets, partially sorted data

it is the simple sorting algorithms that works by sorting one element at a time, and inserting each element into its proper place in a sorted sub list.

2.Selection sort           O(n^2) O(1)

Application : small data sets, data with duplicate value

selection sort works by finding the smallest element in the list and swapping it with the first element. it then finds the second smallest element and swaos it with the second element and so on, until the entire list is sort.

3.Bubble sort               O(n^2) O(1)

Application : small data sets, education

Bubble sort works by comparing adjacent pairs of elements in the list and swapping them if they are in wrong order.it continues to make passes over the list until the lsit is sorted.

4.Quick sort                 O(n^2) O(logn)

Application : large data sets, randomly ordered data

Quick sort is a divide-and-conquer algorithms that works by selecting a pivot element,partitioning the list around the pivot, and then recursively sorting the resulting sub lists.

5.Merge sort                 O(nlogn) O(n)

Application : large data sets, partially sorted data

it works by dividing the lsi into two halves , sorting each half, and then merging the two sorted halves back together.

6.Heap sort                   O(nlogn) O(1)

Application : efficient, data with duplicate values

Heap sort is based on heap data structure, which is a binary tree where each node is greater than or equal to its children. the algo works by building a heap from the input data , and then repeately removing the largest element and inserting it into sorted portion of the list.

7.Shell sort                    O(n(logn)^2) O(1)

 Shell sort is based on insertion sort and works by comparing elements that are farther apart in a list first, and then moving closer together. this makes it more efficient than simple insertion sort for large datsets.

8.Redix sort

9.Counting sort

10.Cyclic sort