How to convert the following non-stable sorting algorithm to stable?

Question

Consider n cards that are marked either red or blue

            i=1;
            j=n;                 
            while(i<n)
            {
              if(a[i]==RED)
                i++;
              if(a[j]==BLUE)
                j--;
              swap(a[i],a[j]);
            }

How to make this in-place algorithm stable I could get a O(n^2) solution to problem could anyone suggest a O(n) solution?

if a array holds only card colours why won't you just count them and then recreate the array by filling it with appropriate values? — rostok
– rostok, Commented Sep 1, 2014 at 16:06
@rostok That would no longer be in place, as OP has suggested. — Sergey Kalinichenko
– Sergey Kalinichenko, Commented Sep 1, 2014 at 16:17
Does this help? csjobinterview.wordpress.com/2012/03/30/array-stable-partition — Abhishek Bansal
– Abhishek Bansal, Commented Sep 1, 2014 at 16:55
The simplest known solutions are rather ugly, and the O(n log n)-time divide-and-conquer algorithm is likely to be faster on current hardware anyway. — David Eisenstat
– David Eisenstat, Commented Sep 1, 2014 at 20:11

nevets · Accepted Answer · 2014-09-01 19:10:54Z

1

If we are allowed to use extra memory, simply do a 2 pass scan:

First pass:

count = 0
foreach a[i] == RED
    b[count ++] = a[i]
    i ++

Second pass:

foreach a[i] == BLUE
    b[count ++] = a[i]
    i ++

Finally copy a = b

In total, the time complexity will be O(3n) = O(n).

answered Sep 1, 2014 at 19:10

nevets

4,87826 silver badges42 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

BatScream · Accepted Answer · 2014-09-01 16:39:14Z

0

One approach in O(n2):

a) append the indices of each element to the element itself.

{"RED1","RED2","BLUE3","BLUE4"}

b) The swap function should take into account the last character, the index indicator, when you try to swap two REDs or two BLUEs.

eg,: When you try to swap two REDs -> only swap if the indexOfFirst(RED) > indexOfSecond(RED)

The same way for BLUEs.

Note: You will need to add some extra logic to find if it is a BLUE or a RED.

answered Sep 1, 2014 at 16:39

BatScream

19.7k4 gold badges54 silver badges68 bronze badges

Comments

Sylwekqaz · Accepted Answer · 2014-09-01 17:02:12Z

Counting sort

if you have only blue and red you counting blue elements and red elements

[b1 r1 r2 b2 b3 r3 r4 b4 r5]

and in for loop you count yours elements you have blue: 4 red: 5

then you knew result table is [ r r r r r b b b b] and you can know index range where is reds elements and blue elements (last red element is {red_count}-1 and last blue element is {red_count}+{blue_count}-1 ) you save this values to redIndex and blueIndex

you make second table and in for loop from end you search elements, the last is r5 its red then his index should be 4 and you decrement redIndex

[b1 r1 r2 b2 b3 r3 r4 b4 __] blueIndex:8 
[__ __ __ __ r5 __ __ __ __] redIndex:3

[b1 r1 r2 b2 b3 r3 r4 __ __] blueIndex:7 
[__ __ __ __ r5 __ __ __ b4] redIndex:3

[b1 r1 r2 b2 b3 r3 __ __ __] blueIndex:7 
[__ __ __ r4 r5 __ __ __ b4] redIndex:2

.....

The faster way to sort items O(2n) but with huge memory usage when various data

Collectives™ on Stack Overflow

How to convert the following non-stable sorting algorithm to stable?

3 Answers 3

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related