Ma’lumotlar tuzilmasi Data structures

Sheyker usulida saralash algoritmi (C++ da)

• void Sort(int col)
• { int trash=0; bool f=true;
• for (int i=1; (i<=col) && (f=true) ; i++)
• { f=false; // chapdan o’ngga o’tish
• for (int j=i; j<=col-i; j++)
• { if (array [j]>array [j+1])
• { trash=array[j]; array [j]=array [j+1];
• array [j+1]=trash; f=true; } }
• // o’ngdan chapga o’tish
• for (int j=col-i-1; j>i ; j--) {
• if (array [j]
• array [j-1]=trash; f=true; } } } }

Sheyker usulida saralash algoritmi(С++)

#include

using namespace std;

//yacheyka qiymatlarini almashtirish f-yasi

void swapEl(int *arr, int i)

{ int buff;

buff = arr[i];

arr[i] = arr[i - 1];

arr[i - 1] = buff;

} //Sheyker sarlash f-yasi

void myShakerSort(int *arr, int size)

{ int leftMark = 1;

int rightMark = size - 1;

while (leftMark <= rightMark)

{ for (int i = rightMark; i >= leftMark; i--)

if (arr[i - 1] > arr[i]) swapEl(arr, i);

leftMark++;

for (int i = leftMark; i <= rightMark; i++)

if (arr[i - 1] > arr[i]) swapEl(arr, i);

rightMark--;

• cout << "\nItiratsiya: " << leftMark - 1; // iteratsiyalar sonini ko'rish
• } }
• int main(){
• setlocale(LC_ALL, "rus");
• int size = 0;
• cout << "Massiv ulchovi: ";
• cin >> size;
• int *A = new int[size];
• for (int k = 0; k < size; k++)
• {
• A[k] = size - k; // qiymatlarni kamayish tartibida yozish

• cout << A[k] << " | ";
• }
• myShakerSort(A, size); // saralash
• cout << "\nSaralashdan keingi massiv:\n";
• for (int k = 0; k < size; k++)
• {
• cout << A[k] << " | ";
• }
• cout << endl;
• return 0;
• }

Tez saralash algoritmi

• Bu algoritm – bo’laklash usuli deb yuritiladi. 1962-yilda Charlz Xoar tomonidan taklif etilgan.
• Bu usul “bo’laklarga bo’l va hukmronlik qil” g’oyasiga asoslangan.
• Bu algoritmning asosiy g’oyasi almashtirish (pufak) usulidagi saralash algoritmiga mos keladi, ya’ni tanlab olingan kalitli elementga nisbatan kichik yoki teng elementlar ikki tomonga ajratib olinadi.

Algoritmning umumiy sxemasi

• Tuzilmadan aniq qiymatga ega biror p element tanlab olish;
• Ushbu elementga nisbatan chap tomonga “kichik yoki teng”, o’ng tomonga esa “katta yoki teng” elementlarni ajratib olish;
• Natijada ikkita “kichiklar” va “kattalar” qismto’plami hosil bo’ladi;
• Agar hosil qilingan qism to’plamlar 2 tadan ortiq elementlarga ega bo’lsa, u holda ushbu jarayon har bir qism to’plam uchun takrorlanadi.

Тез саралаш алгоритми (С++)

#include

#include

int array[100000];

void tezsaralash (long h,long l)

{ long i,j; int p, temp;

i=l; j=h;

p=array[(l+h)/2];

do

{

while (array[i]

while (array[j]>p) j--;

if (i<=j)

{ temp=array[i];

array[i]=array[j];

array[j]=temp;

i++; j--;

} }

while (i<=j);
if(j>l) tezsaralash(j,l);
if(h>i) tezsaralash(h,i);
}
main()
{
int size; int i;
cin>>size;
for (i=0; icin>>array[i];
tezsaralash(size-1,0);
for(i=0; icout<getch();
return 0;
}

Aralashtirib saralash usuli

Bu saralash usulining asosiy g’oyasi, ikkita alohida saralangan massiv yordamida, ularni aralashtirib yuborish orqali yangi saralangan massiv hosil qilishdan iborat.

Bu algoritm quyidagi prinsip asosida ishlaydi: