Мијешајте 2н цијеле бројеве као а1-б1-а2-б2-а3-б3 - .. бн без употребе додатног простора


Ниво тешкоће Средњи
Често питани у адобе ДЕ Схав Екпедиа Фанатици Заиста ПаиУ
Ред Завади па владај Рекурзије

Изјава о проблему

Добија се поредак of интегерс. Проблем „Мешање 2н целих бројева као а1-б1-а2-б2-а3-б3 - .. бн без коришћења додатног простора“ тражи да се измешају сви бројеви у низу тако да бројеви који су слични (к0, к1, к2, к3, и0, и1, и2, и3) ће се на тај начин мешати као к0, и0, к1, и1, к2, и2, к3, и3 и тако даље.

Пример

arr[]={1, 3, 5, 7, 2, 4, 6, 8}
1, 2, 3, 4, 5, 6, 7, 8

Објашњење

Ако упоредимо од прва три броја биће као к0, к1, к2, а следећа три броја биће као и0, и1, и2, и биће распоређени у к0, и0, к1, и1, к2, и2.

Мијешајте 2н цијеле бројеве као а1-б1-а2-б2-а3-б3 - .. бн без употребе додатног простора

Алгоритам за мешање 2н целих бројева као а1-б1-а2-б2-а3-б3 - .. бн без коришћења додатног простора

1. Find out the middle index of the array.
2. While middleIndex greater than 0, set count and swappingIndex to middleIndex.
  1. While the count is greater than 0, do the following steps.
    1. Swap the values at swappingIndex and swappingIndex +1(value next to swappingIndex).
    2. Increase the value of swapping index by 1.
  2. Decrease the value of middleIndex by 1.
3. Print the array.

Објашњење

Дали смо поредак of цео број.  Тада се од нас тражи да премешамо све целобројне вредности на, посебно дат начин. Прећи ћемо само половину низа. И заменом свих вредности које долазе према алгоритму. Прво ћемо проверити да низ не сме бити нулл. Такође, дужина низа треба да буде парна. Због тога проверавамо услов да дужина низова не буде чудна. Ако је било који од горе наведених услова нетачан, тада неће произвести излаз.

Пронаћи ћемо средњи индекс низа, а затим проверити вредност тог индекса и његову следећу вредност индекса и једноставно то заменити. За то ћемо користити угнежђено док петља у првој вхиле петљи. Тада ћемо га прећи са тог тренутног индекса на 0 и наставити смањивати вредност средњег индекса. Унутар унутрашњег док петља, сачуваћемо исту вредност као тренутни индекс у сваппингИндек, а затим ћемо узети вредност сваппингИндек и његову следећу вредност и заменити је. За другу замену, повећајте вредност сваппингИндек и извршите замену за тренутни сваппингИндек и вредност његовог следећег индекса.

За следећу прекретницу смањићемо вредност средњег индекса. Тако да може узети вредности са предње стране низа. Слично томе, цоунт и сваппингИндек биће исти као и вредност средње вредности Индекса коју смо смањили за прелазак ранијих вредности низа. Након све замене коју смо обавили, исписат ћемо тај низ и сви бројеви ће се премешати на задати начин.

код

Ц ++ код за мешање 2н целих бројева као а1-б1-а2-б2-а3-б3 - .. бн без коришћења додатног простора

#include<iostream>
using namespace std;

void shuffleInt(int arr[], int n)
{
    if (arr == NULL || n % 2 == 1)
        return;

    int middleIndex = (n - 1) / 2;

    while (middleIndex > 0)
    {
        int countIndex = middleIndex, swappingIndex = middleIndex;

        while (countIndex -- > 0)
        {
            int temp = arr[swappingIndex + 1];
            arr[swappingIndex + 1] = arr[swappingIndex];
            arr[swappingIndex] = temp;
            swappingIndex++;
        }
        middleIndex--;
    }
}
int main()
{
    int arr[] = {1, 9, 25, 4, 16, 36};
    int n = sizeof(arr) / sizeof(arr[0]);
    shuffleInt(arr, n);
    for (int i = 0; i < n; i++)
        cout << arr[i]<<" ";
}
1 4 9 16 25 36

Јава код за мешање 2н целих бројева као а1-б1-а2-б2-а3-б3 - .. бн без коришћења додатног простора

class Shuffle2nIntegers
{
    public static void shuffleInt(int[] arr)
    {

        if (arr == null || arr.length % 2 == 1)
            return;

        int middleIndex = (arr.length - 1) / 2;


        while (middleIndex > 0)
        {
            int countIndex = middleIndex, swappingIndex = middleIndex;

            while (countIndex -- > 0)
            {
                int temp = arr[swappingIndex + 1];
                arr[swappingIndex + 1] = arr[swappingIndex];
                arr[swappingIndex] = temp;
                swappingIndex++;
            }
            middleIndex--;
        }
    }

    public static void main(String[] args)
    {
        int arr[] = {1, 9, 25, 4, 16, 36};
        shuffleInt(arr);
        for (int i = 0; i < arr.length; i++)
            System.out.print( arr[i]+" ");
        System.out.println();
    }
}
1 4 9 16 25 36

Анализа сложености

Сложеност времена

О (н ^ 2) где „Н“ је број елемената у низу. Као и сваки пут када средњи индекс смањујемо за један. Али унутрашња петља се покреће за миддлеИндек неколико пута. Можете га сматрати једноставним две угнежђене петље у којима спољна петља ради од и = 0 до н, а унутрашња петља од и + 1 до. Стога је временска сложеност полиномна.

Сложеност простора

О (1), јер је алгоритам алгоритам на месту. То је све радње које се раде заменом почетних елемената низа '. И ниједан од нових низова није направљен.