Рубрики

Сортировка по нечетным четным транспорте

Odd-Even Transposition Sort — это алгоритм параллельной сортировки . Он основан на методе Bubble Sort , которая сравнивает каждые 2 последовательных числа в массиве и меняет их местами, если первое больше второго, чтобы получить массив в порядке возрастания. Он состоит из 2 фаз — нечетной фазы и четной фазы:

  • Нечетная фаза: каждый нечетный индексированный элемент сравнивается со следующим четным индексированным элементом (с учетом индексации на основе 1).
  • Четная фаза: каждый четный индексированный элемент сравнивается со следующим нечетным индексированным элементом.

В этой статье используется концепция многопоточности , в частности, pthread . В каждой итерации каждая пара из 2 последовательных элементов сравнивается с использованием отдельных потоков, выполняющихся параллельно, как показано ниже.

Примеры:

Input: { 2, 1, 4, 9, 5, 3, 6, 10 }
Output: 1, 2, 3, 4, 5, 6, 9, 10

Input: { 11, 19, 4, 20, 1, 22, 25, 8}
Output: 1, 4, 8, 11, 19, 20, 22, 25

Примечание. Скомпилируйте программу, используя следующую команду в вашей системе на базе Linux.

g++ program_name.cpp -pthread

Ниже приведена реализация вышеуказанной темы:

// Программа CPP для сортировки нечетно-четных
// используя pthreads

  
#include <bits/stdc++.h>
#include <pthread.h>

  

using namespace std;

  
// размер массива
#define n 8

  
// максимальное количество потоков

int max_threads = (n + 1) / 2;

  

int a[] = { 2, 1, 4, 9, 5, 3, 6, 10 };

int tmp;

  
// Функция для сравнения и обмена
// последовательные элементы массива

void* compare(void* arg)

{

  

    // Каждый поток сравнивает

    // два последовательных элемента массива

    int index = tmp;

    tmp = tmp + 2;

  

    if ((a[index] > a[index + 1]) && (index + 1 < n)) {

        swap(a[index], a[index + 1]);

    }

}

  

void oddEven(pthread_t threads[])

{

    int i, j;

  

    for (i = 1; i <= n; i++) {

        // Нечетный шаг

        if (i % 2 == 1) {

            tmp = 0;

  

            // Создание потоков

            for (j = 0; j < max_threads; j++)

                pthread_create(&threads[j], NULL, compare, NULL);

  

            // присоединение к потокам, т.е. ожидание

            // для завершения всех потоков

            for (j = 0; j < max_threads; j++)

                pthread_join(threads[j], NULL);

        }

  

        // Четный шаг

        else {

            tmp = 1;

  

            // Создание потоков

            for (j = 0; j < max_threads - 1; j++)

                pthread_create(&threads[j], NULL, compare, NULL);

  

            // присоединение к потокам, т.е. ожидание

            // для завершения всех потоков

            for (j = 0; j < max_threads - 1; j++)

                pthread_join(threads[j], NULL);

        }

    }

}

  
// Функция для печати массива

void printArray()

{

    int i;

    for (i = 0; i < n; i++)

        cout << a[i] << " ";

    cout << endl;

}

  
// Код драйвера

int main()

{

  

    pthread_t threads[max_threads];

  

    cout << "Given array is: ";

    printArray();

  

    oddEven(threads);

  

    cout << "\nSorted array is: ";

    printArray();

  

    return 0;

}

Выход:

Given array is:  2 1 4 9 5 3 6 10
Sorted array is: 1 2 3 4 5 6 9 10

Сложность по времени : сложность по времени уменьшается до O (N) из-за параллельных вычислений с использованием потоков.
Сложность работы : Сложность работы этой программы составляет O (N), так как N / 2 количество потоков (ресурсов) используется для сортировки массива. Таким образом, трудоемкость программы составляет O (N ^ 2).

Рекомендуемые посты:

Сортировка по нечетным четным транспорте

0.00 (0%) 0 votes