|
// Optimized implementation of Bubble sort
#include
void swap(int *xp, int *yp)
{
int temp = *xp;
*xp = *yp;
*yp = temp;
}
// An optimized version of Bubble Sort
void bubbleSort(int arr[], 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 (arr[j] > arr[j+1])
{
swap(&arr[j], &arr[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 arr[], int size)
{
int i;
for (i=0; i < size; i++)
printf("%d ", arr[i]);
printf("n");
}
// Driver program to test above functions
int main()
{
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr)/sizeof(arr[0]);
bubbleSort(arr, n);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
}
Output:
Sorted array:
11 12 22 25 34 64 90
Bubble Sort
#include
using namespace std;
int main ()
{
int i, j,temp;
int a[5] = {10,2,0,43,12};
cout <<"Input list ...\n";
for(i = 0; i<5; i++) {
cout <}
cout<for(i = 0; i<5; i++) {
for(j = i+1; j<5; j++)
{
if(a[j] < a[i]) {
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
}
cout <<"Sorted Element List ...\n";
for(i = 0; i<5; i++) {
cout <}
return 0;
}
|
Output:
Input list …
10 2 0 43 12
Sorted Element List …
0 2 10 12 43
Let’s implement the Insertion Sort technique using C++.
#include
using namespace std;
int main ()
{
int myarray[5] = { 12,4,3,1,15};
cout<<"\nInput list is \n";
for(int i=0;i<5;i++)
{
cout <}
for(int k=1; k<5; k++)
{
int temp = myarray[k];
int j= k-1;
while(j>=0 && temp <= myarray[j])
{
myarray[j+1] = myarray[j];
j = j-1;
}
myarray[j+1] = temp;
}
cout<<"\nSorted list is \n";
for(int i=0;i<5;i++)
{
cout <}
}
|
Output:
Input list is
12 4 3 1 15
Sorted list is
1 3 4 12 15
Let us implement the Quick Sort technique using C++.
#include
using namespace std;
// Swap two elements - Utility function
void swap(int* a, int* b)
{
int t = *a;
*a = *b;
*b = t;
}
// partition the array using last element as pivot
int partition (int arr[], int low, int high)
{
int i = (low - 1);
for (int j = low; j <= high- 1; j++)
{
//if current element is smaller than pivot, increment the low element
//swap elements at i and j
if (arr[j] <= pivot)
{
i++; // increment index of smaller element
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
//quicksort algorithm
void quickSort(int arr[], int low, int high)
{
if (low < high)
{
//partition the array
int pivot = partition(arr, low, high);
//sort the sub arrays independently
quickSort(arr, low, pivot - 1);
quickSort(arr, pivot + 1, high);
}
}
void displayArray(int arr[], int size)
{
int i;
for (i=0; i < size; i++)
cout<}
int main()
{
int arr[] = {12,23,3,43,51};
int n = sizeof(arr)/sizeof(arr[0]);
cout<<"Input array"<displayArray(arr,n);
cout<quickSort(arr, 0, n-1);
cout<<"Array sorted with quick sort"<displayArray(arr,n);
return 0;
}
|
Output:
Input array
12 23 3 43 51
Array sorted with Quicksort
3 12 23 43 51
Xulosa
Xulosa qilib, saralash algoritmlarining samaradorligi va qiyosiy taxlili to’g’risida shuni aytishimiz mumkinki, turli xil ish jarayonlari uchun o’ziga mos va bog’liq bo’lgan saralash algoritmlari va mashina tiliga o’girish jarayonlarining qulay usullari ko’zdan kechiriladi. Ushbu usullar aynan o’zining natijasini namoyon etishda eng qulay va shunga bog’liq eng tezkor ekanligi aniqlangandan so’ng qo’llaniladi va shunga mos saralangan xolatdagi ro’yxatlar, o’bektlar va boshqa tuzilmalar natijasi o’laroq yuzaga chiquvchi yangi ro’yxat korinishidagi jadvallar namoyon bo’ladi. Biz esa shunday usullar tarkibiga kiruvchi saralash usullarining bir necha o’ziga xos turlari bilan tanishib chiqdik. Bular : Tanlashorqalisaralashalgoritmi, Pufaksimonsaralashalgoritmi , Quiksort – tezsaralashalgoritmi, va boshqalardir.
Ma`lumotlarni kompyuterda qayta ishlashda elementning informatsion maydonivauning mashina xotirasida joylashishini bilish zarur hisoblanadi. Shumaqsadda ma`lumotlarni saralash amalga oshiriladi. Hamda ma`lumotlarni qaytaishlashda qidiruv asosiy amallardan biri hisoblanadi. Uning vazifasi berilganargument bo`yicha massiv ma`lumotlari ichidan mazkur argumentga mos
ma`lumotlarni topish yoki bunday ma`lumot yo‟qligini aniqlashdan iborat.
Budan tashqari ma`lmotlarni o`zgartirish, ularni o`chirish kabi amallarningbarchasima`lumotlar ustidan qayta ishlash amallari hisoblanar ekan.
Foydalanilgan adabiyotlar
1. Thomas H. Cormen va b. Intruduction to algorithms. M assachusetts Institute of Technology. London 2009.
2. Robert Sedgewick and Kevin Wayne. Algorithms. FOURTH EDITION. Princeton University. Firstprinting, March 2011.
3. В.Д.Колдаев. Основы алгоритмизации и программирования. Учебное пособие, Москва ИД “Форум”- ИНФРА-М 2006 г.
4. А.Р. Есаyaн и др. Информатика. М.:Просвещение,1991.201-212 с.
Internetsaytlar
1. http://structur.h1.ru/hash.htm
2. https://www.softwaretestinghelp.com/sorting-techniques-in-cpp/
3. www.ziyonet.uz
4. www.arxiv.uz
5. www.aim.uz
Do'stlaringiz bilan baham: |
