7. Чизиқли жараёнларни дастурлаш

Бинар қидирувдан фойдаланиш
Жойлаштиришга тўғри жойни топиш учун бинар қидирувдан фойдаланиш маъқул. Ўринлаштиришнинг бу усули бинар ўринлаштириш дейилади. Жойлаштириш учун позиция топилгандан кейин, алгоритм суради ва элементни жойлаштиради. Бу усулда паст сонли саралаш мавжуд, лекин умуман O(n²) оддий мураккаблик сақланади. Кўринишнинг амалий қисмидан бу муҳит жуда ҳам муҳим эмас, чунки ўрнига қўйиб саралаш бироз кичик маълумот гуруҳлари билан ишлайди.
Мураккаблиги
Ўрнига қўйишнинг умумий мураккаблиги O(n²) одатий стандартда, ўрнига қўйиш методига қарамасдан. O(n) гача ўрнига қўйиш қўлланилиб, деярли сараланган массивда ўрнига қўйиш яхшироқ бажарилиш намойиш этади. Ўринлаштиришлар сони O(n²) одатда, лекин таққослашлар сони, ўринлаштириш алгоритмига боғлиқ фарқ қилиши мумкин. Ўринлаштиришлар сони ўрин алмаштириш (swap) ёки суриш (shift) ишлатилганда O(n²) та, бинар ўринлаштириш (binary insertion) ишлатилганда O(n log n) та бўлади.
Ўрнига қўйиш саралаш алгоритмининг хусусиятлари

• 
  Мослашувчан (дастлабки элементлар сафига мос бажарилади);
  
• 
  Bарқарор (бирхил элементларни нисбий жойини сақлаб қолади);
  
• 
  Ички жойда (қўшимча бош жойни ўзгармас қийматини талаб қилади);
  
• 
  Алоқавий боғлиқлик (online) (янги элементлар саралаш давомида ҳам қўшилиши мумкин);
  

void insertionSort(int arr[], int length)
{
int i, j, tmp;
for (i = 1; i < length; i++) {
j = i;
while (j > 0 && arr[j - 1] > arr[j])
{
tmp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = tmp;
j--;
}
}
}
15.5. Танлаб саралаш алгоритми
Танлаб саралаш катта ҳажмли қийматларни саралашда кам унум бўлган О(n²) саралаш алгоритмларининг бири. Танлаб саралаш ўзининг дастурий соддалиги билан аҳамиятли ва у айрим ҳолатдаги бошқа саралашларни ҳам бажара олади.
Алгортимнинг ғояси анча оддий. Массив ҳаёлда иккига бўлинади саралангани ва сараланмагани. Дастлаб, сараланган қисми бўш бўлади, сараланмаган қисми эса тўлиқ массивни ўз ичига олади. Сараланмаган қисми бўш бўлиб қолганда алгоритм тўхтайди.
Алгоритм массивни саралаётганда, сараланмаган қисмнинг биринчи элемти билан минимал элементни ўрнини алмаштиради ва бу сараланган қисмга киритилади. Танлаш алгоритми бу бажаруви барқарор эмас. Боғланган лист сараланган ҳолатда ва ўрин алмаштиришдан кўра, минимал элемент сараланмаган қисмга боғланганда танлаш алгоритми барқарор бўларди.
Мисол:
{5, 1, 12, -5, 16, 2, 12, 14} ни танлаб саралашдан фойдаланиб сараланг.

Агар сараланмаган қисм бўш бўлса, танлаб саралаш тўхтатилади. Билганимиздек, ҳар бир қадамда сараланмаган қисмнинг элементлари 1 га камаяди. Шунинг учун танлаб саралаш ташқи ҳалқадан, тўхташдан олдин n та (n-массив элементлари сони) қадам бажаради. Ташқи ҳалқанинг ҳар – бир қадами сараланмаган қисмдан минимумини топишни талаб қилади. n + (n - 1) + (n - 2) + ... + 1, ни ҳисоблаш О(n²) натижани, таққослашлар сонини беради. Ўрин алмашишлар сони нолдан (сараланган массивда) n-1 гача (массив тескари сафда сараланган ҳолатда) ўзгаради. Умумий алгоритмнинг мураккаблиги О(n²) ни ташкил этади.
Танлаб саралаш кўпи билан n-1 та ўрин алмаштиришларни талаб қилиши шундайки, бу уни ёзиш операцияси ўқиш операциясидан анча қимматлироқ бўлган ҳолларда уни самарали қилади.
void selectionSort(int arr[], int n)
{
int i, j, minIndex, tmp;
for (i = 0; i < n - 1; i++)
{
minIndex = i;
for (j = i + 1; j < n; j++)
if (arr[j] < arr[minIndex])
minIndex = j;
if (minIndex != i)
{
tmp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = tmp;
}
}
}