დალაგება წრფივ დროში C++

ამ ალგორითმს სხვანაირად ეძახიან სორტირებას დათვლით (counting sort). მისი გამოყენება შესაძლებელია, თუ დასალაგებელი მიმდევრობის თითოეული წევრი n მოცემულ  დიაპაზონს (რომელიც არ აჭარბებს წინასწარ ცნობილ  k-ს). ამ ალგორითმის დროითი სირთულეა O(n).

ამ ალგორითმის იდეა კი მდგომარეობს შემდეგში:  ყოველი x ელემენტისათვის წინასწარ დავითვალოთ, რამდენჯერ შედის ეს ელემენტი ამ მიმდევრობაში, შემდეგ   კი დავითვალოთ რამდენი ელემენტია ამ მიმდევრობაში x-ზე ნაკლები, ვთქვათ არის 17 ელემენტი, მაშინ ჩვენ მე-18 ადგილზე შეგვიძლია ჩავწეროთ x ელემენტი. ამ იდეას მცირე კორექტირება დასჭირდება თუ მიმდევრობაში გვაქვს ერთნაირი ელემენტები.

#include <iostream>

using namespace std;

const int INPUT_SIZE = 20;

const int BUCKET_K = 10;

void print(int *input)

{

for ( int i = 0; i < INPUT_SIZE; i++ )

cout << input[i] << " ";

cout << endl;

}

void countingsort(int* input)

{

int CountArr[BUCKET_K] = { 0 };

for (int i=0;i<INPUT_SIZE;i++)

{

CountArr[input[i]]++; }

int outputindex=0;

for (int j=0;j<BUCKET_K;j++)

{

while (CountArr[j]--)

input[outputindex++] = j;

}

}

int main()

{

int input[INPUT_SIZE] = { 2, 4, 6, 4, 7, 1, 4, 9, 5, 3, 7, 2, 2, 6, 9, 3, 7, 3, 4, 4 };

cout << "Input: ";

print(input);

countingsort(input);

cout << "Output: ";

print(input);

system("pause");

return 0;

}


პრეზენტაციის ლინკი: https://www.dropbox.com/s/od89n1b9atykhzr/106733%20%281%29.pptx?dl=0