|
Muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti 1-mustaqil ishi
|
| bet | 4/4 | | Sana | 27.12.2023 | | Hajmi | 4.76 Mb. | | #128651 |
Bog'liq 1701257360 (1) 000000, 19Algoritm murakkabligi
• xohlagan holatda O(n2 )
Dastur kodi
#include
using namespace std;
int findSmallestPosition(int list[], int startPosition, int listLength)
{
int smallestPosition = startPosition;
for(int i = startPosition; i < listLength; i++)
{
if(list[i] < list[smallestPosition])
smallestPosition = i;
}
return smallestPosition;
}
void selectionSort(int list[], int listLength)
{
for(int i = 0; i < listLength; i++)
{
int smallestPosition = findSmallestPosition(list, i,
listLength);
swap(list[i], list[smallestPosition]);
}
return;
}
int main ()
{
int list[5] = {12, 5, 48, 0, 4};
cout << "Input array ..." << endl;
for(int i = 0; i < 5; i++)
cout << list[i] << " ";
cout << endl;
selectionSort(list, 5);
cout << "Sorted array ..." << endl;
for(int i = 0; i < 5; i++)
cout << list[i] << " ";
cout << endl;
}
Natija:
3. O’rniga qo’yish orqali saralash (Insertion sort)
Bu usul ikkinchi elementda boshlanadi. Elementdan oldingi qo’shni elementlar solishtirib chiqiladi.
Algoritm murakkabligi
• eng yaxshi holatda O(n)
• eng yomon holatda O(n2)
Dastur kodi
#include
using namespace std;
void insertionSort(int list[], int listLength)
{
for(int i = 1; i < listLength; i++)
{
int j = i - 1;
while(j >= 0 && list[j] > list[j + 1])
{
swap(list[j], list[j + 1]);
j--;
}
}
}
int main()
{
int list[5]={12,5,48,0,4};
cout<<"Input array ...\n";
for (int i = 0; i < 5; i++)
{
cout<}
cout<insertionSort(list, 5);
cout<<"\n\nSorted array ... \n";
for (int i = 0; i < 5; i++)
{
cout<}
cout<return 0;
}
Natija:
|
| |
