1

I had an algorithm to solve the problem where professor has to sort the students by their class score like 1 for good and 0 for bad. in minimum number of swaps where only adjacent students can be swapped. For Example if Students are given in sequence [0,1,0,1] only one swap is required to do [0,0,1,1] or in case of [0,0,0,0,1,1,1,1] no swap is required.

From the problem description I immediately know that it was a classic min adjacent swap problem or count inversion problem that we can find in merge sort. I tried my own algorithm as well as the one listed here or this site but none passed all the tests.

The most number of test cases were passed when I try to sort the array in reverse order. I also tried to sort the array in the order based on whether the first element of the array is 0 or 1. For example is the first element is 1 then I should sort the array in descending order else in ascending order as the students can be in any grouping, still none worked. Some test cases always failed. The thing was when I sort it in ascending order the one test case that was failing in case of reverse sorting passed along with some others but not all. So I don't know what I was doing wrong.

Dashing Boy
  • 477
  • 2
  • 10
  • 21
  • are all array elements either 0 or 1? No other values? – GPS Apr 05 '19 at 06:52
  • Maybe problem does not fix specific order and you have to choose - 0011 or 1100 would be better? – MBo Apr 05 '19 at 07:07
  • 2
    Please share the tests used in "none passed all the tests" – GPS Apr 05 '19 at 07:19
  • @GPS Yes, all elements are either 0 or 1, no other values .And no I don't have the test cases that were failed. It was hidden from me. It's precisely why I have a hard time finding out what went wrong. – Dashing Boy Apr 05 '19 at 11:03
  • 1
    @MBo both 0011 or 1100 are okay depending on which had the minimum swaps. That's why I tried to sort in in asc/desc order. – Dashing Boy Apr 05 '19 at 11:03
  • Does you method give the same result as straightforward implementation with two loops? – MBo Apr 05 '19 at 11:12
  • I think there is some problem with the code you used. Perhaps you should include your code to shed light on this. It should be irrelevant whether you start sorting from one end or other. – GPS Apr 05 '19 at 11:19
  • @MBo The last algo I used is from geekforgeeks and it still gave me the same results. My apologies for late reply as I wasn't in town. – Dashing Boy Apr 09 '19 at 14:03

2 Answers2

0

It feels to me that term "sorting" is an exaggeration when it comes to an array of 0's and 1's. You can simply count 0's and 1's in O(n) and produce an output.

To address "minimal swaps" part, I constructed a toy example; two ideas came to my mind. So, the example. We're sorting students a...f:

a b c d e f
0 1 0 0 1 1

a c d b e f
0 0 0 1 1 1

As you see, there isn't much of a sorting here. Three 0's, three 1's.

First, I framed this as an edit distance problem. I. e. you need to convert abcdef into acdbef using only "swap" operation. But how does you come up with acdbef in the first place? My hypothesis here is that you merely need to drag 0's and 1's to opposite sides of an array without disturbing their order. E. g.

        A     B     C     D
0 0 ... 0 ... 1 ... 0 ... 1 ... 1 1

0 0 0 0         ...         1 1 1 1
    A C                     B D

I'm not 100% sure if it works and really yields you minimal swaps. But it seems reasonable - why would you spend an additional swap for e. g. A and C?

Regarding if you should place 0's first or last - I don't see an issue with running the same algorithm twice and comparing the amount of swaps.

Regarding how to find the amount of swaps, or even the sequence of swaps - thinking in terms of edit distances can help you with the latter. Finding just numbers of swaps can be a simplified form of edit distance too. Or perhaps something even more simple - e. g. find something (a 0 or 1) that is nearest to its "cluster", and move it. Then repeat until the array is sorted.

u354356007
  • 3,205
  • 15
  • 25
  • Isn't it again pretty much the swaps/inversions in merge sort? I mean based on my understanding of merge sort this is what it does to sort an array. I understand that I only have 0's and 1's but it is still fundamentally sorting. – Dashing Boy Apr 09 '19 at 14:10
  • @DashingBoy Somewhat, yes. I'd say it's more like a bubble sort swaps, rather then merge sort merges though. What I do in the answer is basically exploiting the fact that array values are limited to 0 and 1 in order not to do any kind of sorting and possibly bring the complexity from O(nlogn) to O(n). – u354356007 Apr 10 '19 at 06:10
-1

If we had to sort the zeros before the ones, this would be straightforward inversion counting.

def count(lst):
    total = 0
    ones = 0
    for x in lst:
        if x:
            ones += 1
        else:
            total += ones
    return total

Since sorting the ones before the zeros is also an option, we just need to run this algorithm twice, once interchanging the roles of zeros and ones, and take the minimum.

David Eisenstat
  • 64,237
  • 7
  • 60
  • 120
  • Can you share the logic behind it? It seems it's just counting the ones but doesn't account for minimum swaps. – Dashing Boy Apr 09 '19 at 14:04
  • @DashingBoy Each pair of positions where the first position has 1 and the second has a 0 accounts for one swap. We scan the array, tracking how many ones have been scanned. Every time we hit a zero, we add this number to the total. – David Eisenstat Apr 09 '19 at 14:35
  • I love how tiny this result is. I guess that is it possible to build a bridge between my answer and this algorithm. Several steps are certainly missed, but incrementing `total` by number of ones is pretty much a synonym to "group ones at one end of the array". – u354356007 Apr 10 '19 at 06:16
  • There's a problem with the algo. It works for [0,0,1,1] with 0 swaps but return 4 when the sequence is [1,1,0,0] while it should return 0 for both cases as no swaps are required. – Dashing Boy Apr 16 '19 at 09:01
  • @DashingBoy Edited my answer. We have to run it twice, once as is, once with the branches of the if swapped, and take the min. – David Eisenstat Apr 16 '19 at 11:30