Insertion sort example program source code , SORTING in c++ language in hindi , Bubble sort :-
इससे पहले के article मे searching operation को discuss किया था अब इस article मे sorting oparation के लिए use किये जाने वाले algorithm को discuss किया है |
मुख्य c++ language मे sorting के लिए तीन algorithm को use किया जाता है | इसके लिए sorting operation को बहुत easy बना दिया गया है | यहा पर इन सभी sorting को अच्छी तरह से समज सकते है |
Bubble sort
Bubble sort बहुत सरल sorting algorithm है | Bubble sort मे तब तक swaaping operation perform होता है जब तक array के सभी element किसी विशेष arrangement नहीं आ जाता है | इसके निन्म उदाहरन को consider किया जाता है |
array : 64, 34, 25, 12, 22, 11, 90
पहले pass मे ,
सबसे पहले 64 और 34 मे compare होता है ओर 64 , 34 से बड़ी है तब दोद्नो array element interchange हो जाता है इसके लिए 34,64, 25, 12, 22, 11, 90 |
सबसे पहले 64 और 25 मे compare होता है ओर 64 , 25से बड़ी है तब दोनों array element interchange हो जाता है इसके लिए 34,25,64, 12, 22, 11, 90 |
सबसे पहले 64 और 12 मे compare होता है ओर 64 , 25से बड़ी है तब दोनों array element interchange हो जाता है इसके लिए 34,25,12 ,64, 22, 11, 90 |
सबसे पहले 64 और 22 मे compare होता है ओर 64 , 25से बड़ी है तब दोनों array element interchange हो जाता है इसके लिए 34,25,12, 22,65, 11, 90 |
सबसे पहले 64 और 11 मे compare होता है ओर 64 , 11 से बड़ी है तब दोनों array element interchange हो जाता है इसके लिए 34,25,12, 22, 11,64, 90 |
सबसे पहले 64 और 90 मे compare होता है ओर 64 , 90 से बड़ी नहीं है तब दोनों array element interchange नहीं होते है इसके लिए 34,25,12, 22, 11,64, 90 |
ये loop तब तक चलता है जब तक की सभी element array मे आपनी अपनी correct position मे set नहीं हो जाता है |
#include <iostream.h>
#include <conio.h>
void swap(int *a, int *b)
{
int temp = *a ;
*a= *b ;
*b = temp;
}
// An optimized version of Bubble Sort
void bubbleSort(int array[], int n)
{
int i, j;
bool swapped;
for (i = 0; i < n-1; i++)
{
swapped = false;
for (j = 0; j < n-i-1; j++)
{
if (array [j] > array [j+1])
{
swap(&array [j], &array [j+1]);
swapped = true;
}
}
// IF no two elements were swapped by inner loop, then break
if (swapped == false)
break;
}
}
/* Function to print an array */
void printArray(int array[], int size)
{
int i;
for (i=0; i < size; i++)
cout<<a[i];
cout<<n;
}
// Driver program to test above functions
void main()
{
int array[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(array )/sizeof(array [0]);
bubbleSort(array , n);
cout<<“sorted array ” <<endl;
printArray(array , n);
getch();
}
Insertion sort
insertion sort मे sorting operation को perform करने के लिए निन्म step को फॉलो किया जाता है |
पहले pass मे ,
array[] = {64, 34, 25, 12, 22, 11, 90}
इसमें सबसे पहले 34 का 64 compare किया जाता है अगर 34 की 64 से छोटी है तब 64 34 से replace हो जाती है | इसके लिए 34,65, 25, 12, 22, 11, 90
इसके बाद 34 का 45 का compare किया जाता है और 34 की value 25 से बड़ी है इसलिए दोनों मे reclacement हो जाता है इसके लिए 25,65, 34, 12, 22, 11, 90
इसके बाद 34 का 45 का compare किया जाता है और 34 की value 25 से बड़ी है इसलिए दोनों मे reclacement हो जाता है इसके लिए 25,65, 34, 12, 22, 11, 90
इसके बाद 25 का 12 का compare किया जाता है और 25 की value 12 से बड़ी है इसलिए दोनों मे reclacement हो जाता है इसके लिए 12,65, 34, 25, 22, 11, 90
इसके बाद 12 का 11 का compare किया जाता है और 12 की value 11 से बड़ी है इसलिए दोनों मे reclacement हो जाता है इसके लिए 11,65, 34, 22,25,12, 90
पहला pass ख़त्म हो गया इस pass के end मे पहले position के element secure हो गया है |
अब दुसरे pass मे second position के लिए उपयुत element को search किया जाता है |
इस तरह हर pass के end मे पत्येक position के लिए element को search किया जाता है |
source code :
// C program for insertion sort
#include <math.h>
#include <stdio.h>
/* Function to sort an array using insertion sort*/
void insertionSort(int array[], int n)
{
int i, key, j;
for (i = 1; i < n; i++) {
key = array[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 && array [j] > key) {
arr[j + 1] = array[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++)
printf(“%d “, arr[i]);
printf(“\n”);
}
/* Driver program to test insertion sort */
int main()
{
int arr[] = { 12, 11, 13, 5, 6 };
int n = sizeof(arr) / sizeof(arr[0]);
insertionSort(arr, n);
printArray(arr, n);
getch();
}
इस article मे insertion search और bubble search को अच्छी तरह से discuss किया था अब आगे के article मे quick sort को discuss करेगे |