Tez saralash (Quicksort) Bu usul ingliz informatigi Charlz Xoar (Чарльз Хоар) tomonidan 1960

Tez saralash (Quicksort)

Bu usul ingliz informatigi Charlz Xoar (Чарльз Хоар) tomonidan 1960 yilda Moskva universitetida kompiyterda electron tarjima qilish bo’yicha o’qiyotganida, rus-ingliz so’zlashgichini ishlab chiqayotganida taklif etilgan.

• 
  Bu usul almashtirish usulining modifikatsiyasi bo‘lib, uning asosini kalitlarni tanlangan kalitga(tayanch kalit) nisbatan almashtirish tashkil qiladi. Tanlash-ixtiyoriy ravishda, masalan, o’rtasini.
  
• 
  Algoritm g’oyasi: 1) tayanch element tanlanadi;
  
• 
  2) elementlarni tayanch elementdan kichik elementlar to’plami va katta yoki teng elementlar to’plamiga bo’lamiz;
  
• 
  3) bu 2 to’plamga nisbatan yuqoridagi 1-2 punktni qo’llaymiz ( bo’sh yoki 1ta elementli to’plamga qo’llanilmaydi)
  

#include
using namespace std;
void swap(int* a, int* b) // 2ta elementni almashtirish uchun funksiya
{
int t = *a;
*a = *b;
*b = t;
}

int partition (int arr[], int l, int h)
{
int pivot = arr[h];
int i = (l - 1); // kichikroq element indeksi va shu jarayongacha topilgan pivotning to`g`ri pozitsiyasini ko`rsatadi
for (int k = l; k <= h - 1; k++)
{

if (arr[k] < pivot)

i++; // kichik elementni o`sish tartibida joylashtirish
swap(&arr[i], &arr[k]);
}
}
swap(&arr[i + 1], &arr[h]);
return (i + 1);
}
//tezkor saralashni amalga oshiruvchi funksiya
void quickSort(int arr[], int l, int h)
{
if (l < h)
{
int pi = partition(arr, l, h);
quickSort(arr, l, pi - 1);
quickSort(arr, pi + 1, h);
}
}
/* massivni chiqarish funksiyasi*/
void print_array(int arr[], int size)
{
int i;
for (i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
int main()
{
int arr[] = {11, 13, 16, 1, 3, 5, 9};
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
cout << "Sorted array: \n";
for(int i=0; i
{
cout<
}
return 0;
}