C tutorial - Sorting techniques

Programming languages or concepts
0

Sorting techniques 


in this tutorial we can learn about sorting techniques using Array in ascending order:-

Sorted List:-
    It is the ordered list in which the elements are arranged in particular order by some criteria. The general orders are ascending order and descending order.

Passes:-
   The number of passes indicates the number of times the list is scanned to sort the list.

Exchanges :-
     The number of exchange indicates the number of elements swapped or exchanged till the list is sorted in order.

Types of Sorting techniques:-
1). Bubble Sort
2). Insertion Sort
3). Selection Sort
4).merge sort
5). quick sort
6). Heap sort


The Different sorting techniques / methods are described below:-

1). Bubble Sort Method:-
     In bubble sort method the list is rearranged by exchanging the two adjacent elements they are not in order. ( Order may be ascending or descending). Starting with first element at index = 0, each element A[ index] as compared with it's next adjacent element A[ index + 1] and exchanged if A[ index ] >A[ index + 1 ]. Initially the length of list used is N - 1 elements, and it is decremented by one after each pass. The largest element from current list will be placed at its final position at N-1, N-2, N-3,......2 respectively. In a pass, if the number of exchanges is zero, then list sorted and no further passes are required.

Pictorial representation:-
Input list (unsorted) for N =7
          27,4,40,32,15,48,50.

Pass 1: Go through N-1 element ( index = 0 to N-2)


Total Exchanges in pass 1 are 03             
Number of Comparisons are ( N-1 ) = 06

Pass 2 : Go through N-2 element ( index = 0 to N-3 )
   
TotalExchanges in pass 2 = 01 
  Number of comparisons ( N-2 ) = 05
Pass 3 : Go through N-3 element ( index = 0 to N-4 )


Total Exchanges in pass 3 = 01
Number of Comparisons = 04

Pass 4 : Go through N-4 element ( index= 0 to N-5)


Total Exchanges in pass 4 = 0
Number of comparisons = 03
As there are no exchanges in pass 4, it is not necessary to go for any further passes. Thus bubble sort make complete before maximum N-1 passes.
Total number of passes for N=7 required for 4.
Total number of Exchanges required is 5
Total number of comparison required is 18.

Sorted array is:- 4,15,27,32,40,48,50.


Bubble sort program

#include <stdio.h>

  int main()

{
  int array[100], n, i, j, swap;


  printf("Enter number of elements\n");
  scanf("%d", &n);


  printf("Enter %d integers\n", n);


  for (i = 0; i < n; i++)
    scanf("%d", &array[c]);


  for (i= 0 ; i < n - 1; i++)
  {
    for (j = 0 ; j < n - c - 1; j++)
    {
      if (array[j] > array[j+1]) 
      {
        swap       = array[j];
        array[j]   = array[j+1];
        array[j+1] = swap;
      }
    }
  }


  printf("Sorted list in ascending order:\n");


  for (i = 0; i < n; i++)
     printf("%d\n", array[i]);


  return 0;
}

 For more details



Post a Comment

0Comments

Post a Comment (0)
close