CODEWITHSUNDEEP
arraysalgorithmdynamic-programmingpartitioning
FunnyBuzer
FunnyBuzer

Reputation: 313

Arrange all elements of a n-sized array so that the output array has all negative elements first, then zeros and the the positive ones without sorting

Given an array of size n, I would like to arrange the elements so that the output will return that array having first all negative elements, then zeros and finally all positive elements, without sorting the array. That is, I would like to partition the array into 3 part, getting a complexity O(n) and without using additional arrays.

The code below is an attempt, but it sorts the array and this is not what I want, since even optimising it I can only achieve a time complexity O(nlogn).

using System;

public class sort
{
public static void Main(string[] args)
{
    int n, k, t;
    Console.WriteLine("Enter the size of array");
    n = Convert.ToInt32(Console.ReadLine());
    int[] arr = new int[n];
    for (k = 0; k < n; k++)
    {
        Console.Write("\nEnter your number:\t");
        arr[k] = Convert.ToInt32(Console.ReadLine());
    }

    for (int j = 0; j <= n- 2; j++)
    {
        for (int i = 0; i <= n - 2; i++)
        {
            if (arr[i] > arr[i + 1])
            {
                t = arr[i + 1];
                arr[i + 1] = arr[i];
                arr[i] = t;
            }
        }
    }
    Console.WriteLine("The output array :");
    foreach (int aray in arr)
        Console.Write(aray + " ");
        Console.ReadLine();
}
}

Thanks in advance for your suggestions.

Upvotes: 2

Views: 158

Answers (2)

FunnyBuzer
FunnyBuzer

Reputation: 313

Thanks to m69 for his suggestion. This is the correct code in C# that implements Dijkstra's 3-partitioning:

using System;
using System.Diagnostics;

public class Program
{
    public static void Main()
    {
        int[] array1 = {1, -3, 5, 7, -9, 0, 2, -4, 6, 8, 0}; 
        printArray(partitioning(array1, 0));
    }

    public static int[] partitioning(int[] array, int mid)
    {
        int i = 0, j = 0, n = array.Length;
        Trace.Assert(n > 0);
        while (j < n)
        {
            if (array[j] < mid)
            {
                swap(ref array[i], ref array[j]);
                i += 1;
                j += 1;
            }
            else if (array[j] > mid)
            {
                swap(ref array[j], ref array[n-1]);
                n -= 1;
            }
            else 
                j += 1;
        }

        //Time complexity: O(n)
        return array;
    }

    public static void printArray(int[] array)
    {
        for(int i=0; i<array.Length; ++i) {
            Console.Write("" + array[i] + " ");
        }
        Console.WriteLine("");
    }

    public static void swap(ref int a, ref int b)
    {
        int temp = a;
        a = b;
        b = temp;
    }
}

Upvotes: 2

Rounak
Rounak

Reputation: 796

It can be done by taking another array. Let another array be b.
First, we iterate over the initial array and store the negative numbers in the array b. Then, we again iterate over the initial array and store the zeroes in the array b. This way, the zeroes come after the negative numbers in array b, since the index of the last number in array b is being maintained in another variable j. Now, we again iterate over the initial array and store the positive numbers in the array b. This way, if we output the elements of array b, we will get first all negative elements, then zeros and finally all positive elements.

The below code does exactly that: 

using System;

public class sort
{
public static void Main(string[] args)
{
    int n, k, i, t, j=0;
    Console.WriteLine("Enter the size of array");
    n = Convert.ToInt32(Console.ReadLine());
    int[] arr = new int[n];
    int[] b = new int[n];
    for (k = 0; k < n; k++)
    {
        Console.Write("\nEnter your number:\t");
        arr[k] = Convert.ToInt32(Console.ReadLine());
    }
    for(i = 0; i < n; i++){
       if(arr[i] < 0)
         {b[j] = arr[i]; j++;}
       }
    for(i = 0; i < n; i++){
       if(arr[i] == 0)
         {b[j] = arr[i]; j++;}
       }
    for(i = 0; i < n; i++){
       if(arr[i] > 0)
         {b[j] = arr[i]; j++;}
       }

    Console.WriteLine("The output array :");
    foreach (int aray in b)
        Console.Write(aray + " ");
        Console.ReadLine();
}
}

The three loops each have a time complexity of O(n)

Upvotes: 0

Related Questions