CODEWITHSUNDEEP
c++c
raptor0102
raptor0102

Reputation: 309

sorted array with three different integers with only one pass

is there possible way to sort an array of three integers with only one pass on the array?

you get:

int array[]={1,2,2,2,3,1,1,2,2,1,3}

and you are told that there are only number 1,2,3

to get:

int array[]={1,1,1,1,2,2,2,2,2,3,3}

and no extra space allowed

Tnx!

Upvotes: 2

Views: 1472

Answers (5)

Blastfurnace
Blastfurnace

Reputation: 18652

This is the Dutch national flag problem with a simple linear solution described by E. W. Dijkstra in the early 70's. It's sometimes used as a partitioning method for quicksort.

#include <iostream>

template <typename BidIt, typename T>
void dnf_partition(BidIt first, BidIt last, const T &pivot)
{
    for (BidIt next = first; next != last;) {
        if (*next < pivot) {
            std::iter_swap(first++, next++);
        } else if (pivot < *next) {
            std::iter_swap(next, --last);
        } else {
            ++next;
        }
    }
}

int main()
{
    int array[] = { 1, 2, 2, 2, 3, 1, 1, 2, 2, 1, 3 };

    for (int n : array) std::cout << n << ' ';
    std::cout << '\n';

    dnf_partition(std::begin(array), std::end(array), 2);

    for (int n : array) std::cout << n << ' ';
    std::cout << '\n';
}

Live demo on ideone.com

Upvotes: 1

Vlad from Moscow
Vlad from Moscow

Reputation: 311038

Here is a straightforward approach (without testing)

#include <iostream>
#include <algorithm>
#include <iterator>

void sort( int *first, int *last )
{
    for ( int *current = first; current != last; )
    {
        if ( *current == 1 )
        {
            if ( current == first )
            {
                ++current;
            }
            else
            {
                std::swap( *current, *first );
            }
            ++first;
        }
        if ( *current == 3 )
        {
            --last;
            if ( *current != *last ) std::swap( *current, *last );
        }
        if ( *current == 2 ) ++current;
    }
}

int main() 
{
    int a[] = { 1, 2, 2, 2, 3, 1, 1, 2, 2, 1, 3 };

    for ( int x : a ) std::cout << x << ' ';
    std::cout << std::endl;

    sort( std::begin( a ), std::end( a ) );

    for ( int x : a ) std::cout << x << ' ';
    std::cout << std::endl;

    return 0;
}

The output is

1 2 2 2 3 1 1 2 2 1 3 
1 1 1 1 2 2 2 2 2 3 3

Upvotes: 1

HelloWorld123456789
HelloWorld123456789

Reputation: 5369

One pass with no extra space:

first pointer: Denotes start of 2 in the array.

last Pointer: Denotes start of 3 in the array.

If you find a 1, swap it with the first pointer.

If you find a 2, keep it there.

If you find a 3, swap it with the last pointer.

Dry run:

{1,2,2,2,3,1,1,2,2,1,3} cur=1, first=1, last=10
{1,2,2,2,3,1,1,2,2,1,3} cur=2, first=2, last=10
{1,2,2,2,3,1,1,2,2,1,3} cur=3, first=2, last=10
{1,2,2,2,3,1,1,2,2,1,3} cur=4, first=2, last=10
{1,2,2,2,3,1,1,2,2,1,3} cur=5, first=2, last=10
{1,2,2,2,1,1,1,2,2,3,3} cur=5, first=2, last=9
{1,1,2,2,2,1,1,2,2,3,3} cur=5, first=3, last=9
{1,1,1,2,2,2,1,2,2,3,3} cur=6, first=4, last=9
{1,1,1,1,2,2,2,2,2,3,3} ...

Time: O(n) (one pass)

Space: O(1)

Upvotes: 6

Elliott Frisch
Elliott Frisch

Reputation: 201447

Yes. With a counting sort,

int array[]={1,2,2,2,3,1,1,2,2,1,3};
int count[]={0,0,0};
int i = 0;
while (array[i] != '\0') {
  count[array[i] - 1]++;
  i++;
}
for (i = 0; i < count[0]; i++) {
  printf("%i", 1);
  printf(",");
}
for (i = 0; i < count[1]; i++) {
  printf("%i", 2);
  printf(",");
}
for (i = 0; i < count[2]; i++) {
  printf("%i", 3);
  if (i + 1 < count[2]) {
    printf(",");
  }
}
printf("\n");

Edit

With no extra space allowed.

Then no. It's not possible.

Upvotes: 0

Alexander Gessler
Alexander Gessler

Reputation: 46617

Yes, use counting sort. Basically, you walk the input array once and count for each of the values how often they occur. Afterwards, you just emit the appropriate number of values for each bucket.

Edit: counting, not bucket sort.

Upvotes: 6

Related Questions