Write a program to sort given array in ascending order

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.

Time Complexity of InsertionSort

Best Case : O(n) #Means array is already sorted.

Average Case : O(n²) #Means array with random numbers.

Worst Case : O(n²) #Means array with descending order.

Example:

Let us sort the following numbers using Insertion sort mechanism,
12, 11, 13, 5, 15

Let us loop for i = 1 (second element of the array) to 4 (last element of the array)

i = 1. Since 11 is smaller than 12, move 12 and insert 11 before 12
11, 12, 13, 5, 15

i = 2. 13 will remain at its position as all elements in A[0..I-1] are smaller than 13
11, 12, 13, 5, 15

i = 3. 5 will move to the beginning and all other elements from 11 to 13 will move one position ahead of their current position.
5, 11, 12, 13, 15

i = 4. 15 will be at position 5 as all the elements are smaller than 15.
5, 11, 12, 13,15

Arranging the elements in ascending order or in descending order is called Sorting. Sorting techniques are broadly categorized into two.

1. Internal Sorting and
2. External Sorting.

1. Internal Sorting : All the records that are to be sorted are in main memory.

2. External Sorting: Some sorts that cannot be performed in main memory and must be done on disk or tape. This type of sorting is known as External Sorting.

Efficiency: One of the major issues in the sorting algorithms is its efficiency. If we can efficiently sort the records then that adds value to the sorting algorithm. We usually denote the efficiency of sorting algorithm in terms of time complexity. The time complexities are given in terms of big-oh notation.

Commonly there are O(n2) and O(n log n ) time complexities for various algorithms. Quick sort is the fastest algorithm and bubble sort is the slowest one.

Sorting Method — — — — — — — — — — — — — - Efficiency

Bubble sort/Selection sort/Insertion sort — — — — 0(n2)

Quick / Merge — — — — — — — — — — — — — — — 0(n log n)

One of the best sorting technique. If n value is large, it follows divide and conquer approach.

Like Quicksort, Merge Sort is a Divide and conquer algorithm. It divides input array in two halves, calls itself for the two halves and then merges the two sorted halves. The merge() function is used for merging two halves.

Time Complexity :

Best Case : O(nlogn) #Means array is already sorted.

Average Case : O(nlogn) #Means array with random numbers.

Worst Case : O(nlogn) #Means array with descending order.

Quick Sort Algorithm:

This is the best sort Technique. QuickSort is a Divide and Conquer algorithm. It picks an element as pivot and partitions the given array around the picked pivot. There are many different versions of quickSort that pick pivot in different ways.

1. Always pick first element as pivot.
2. Always pick last element as pivot
3. Pick a random element as pivot.
4. Pick median as pivot.

Time Complexity :

Best Case : O(nlogn) #Means array is already sorted.

Average Case : O(nlogn) #Means array with random numbers.

Worst Case : O(n^2) #Means array with descending order.

Algorithm:

1. First element is considered as pivot in the implemented code below.
2. Then we should move all the elements which are less than pivot to one side and greater than pivot to other side.
3. We divide the array into two arrays in such a way that elements > pivot and elements < pivot.

•  Program:

#include<stdio.h>
#include<conio.h>

int main()
{
    int a[10],i,j,n,min,temp;
    printf("Enter number you want: ");
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        printf("Enter value at position [%d] :",i+1); 
        scanf("%d",&a[i]); 
    }
    for(i=0;i<n-1;i++)
    {
        min=a[i];      
        for(j=i+1;j<n;j++)
        {
            if(a[j]<a[i])
            {
                min=j;
                temp=a[i];
                a[i]=a[j];
                a[j]=temp;
            }
        }   
        printf("%d ->",a[i]);
    }
    printf("%d ->",a[i]);
    getch();
    return 0;
}

•  Visit :